I have a big problem - I have to write the function that converts a one-time list into a double search tree that is balanced.

[goshko2]

My problem is that I do not fully understand how to apply the rotation functions - more precisely when I take a list item and add it to the tree I do not know how to actually check which function I have to call - for right,for left,for right left or for left-right rotation.

In the following code I will not write my rewriting features to a tree item because I'm ashamed of them: - / - Only the list and tree-building functions to help if someone decides to help me use them.

 
#include<iostream>
using namespace std;
struct elem           //structure for the list
{
      int key;
      elem *next;
}*start=NULL;

void add(int n)     //function to add an item to the home of the list
{
      elem *p=start;
      start=new elem;
      start->key=n;
      start->next=p;
}

struct tree           //structure for balanced binary tree
{
      int key;
      int bal;
      tree *left;
      tree *right;
}*root=NULL;

void R_root(tree *&p)         //function for right rotation
{
      tree *q;

      if(p->bal==-1)
      {
            q=p->left;

            if(q->bal==-1)
            {
                  p->left=q->right;
                  q->right=p;
                  p->bal=0;
                  p=q;
            }
      }
}

void L_root(tree *&p)      //function for left rotation
{
      tree *q;

      if(p->bal==1)
      {
            q=p->right;

            if(q->bal==1)
            {
                  p->right=q->left;
                  q->left=p;
                  p->bal=0;
                  p=q;
            }
      }
}

void LR_root(tree *&p)  //function for left-right rotation
{
      tree *q,*s;

      if(p->bal==-1)
      {
            q=p->left;

            if(q->bal==1)
            {
                  s=q->right;
                  q->right=s->left;
                  s->left=q;
                  p->left=s->right;
                  s->right=p;

                  if(s->bal==-1)
                  {
                        q->bal=1;
                  }
                  else
                  {
                        p->bal=0;
                  }

                  if(s->bal==1)
                  {
                        q->bal=-1;
                  }
                  else
                  {
                        q->bal=0;
                  }

                  p=s;
            }
      }
}

void RL_root(tree *&p)     //function for right-left rotation
{
      tree *q,*s;

      if(p->bal==1)
      {
            q=p->right;

            if(q->bal==-1)
            {
                  s=q->left;
                  q->left=s->right;
                  s->right=q;
                  p->right=s->left;
                  s->left=p;

                  if(s->bal==1)
                  {
                        q->bal=1;
                  }
                  else
                  {
                        p->bal=0;
                  }

                  if(s->bal==-1)
                  {
                        q->bal=1;
                  }
                  else
                  {
                        q->bal=0;
                  }

                  p=s;
            }
      }
}

int hight(tree *t)     //function for finding the hight of the tree
{
      if(t==NULL)
      {
            return 1;
      }

      int u=hight(t->left);
      int v=hight(t->right);

      if(u>v)
      {
            return u+1;
      }
      else
      {
            return v+1;
      }
}

void printnode(int n,int h)      //function for print node
{
      for(int i=0;i<h;i++)
      {
            cout<<" ";
      }
      cout<<n<<endl;
}

void show(tree *t,int h)   //function for showing the tree
{
      if(t==NULL)
      {
            printnode(0,h);
            return;
      }
      show(t->right,h+1);
      printnode(t->key,h);
      show(t->left,h+1);
}

void record();       //function for the declaration of the listing element feature in the binary tree


int menu()                    //function menu 
{
      int n;

      do
      {
            cout<<"**********************************************"<<endl;
            cout<<"*               MENU                         *"<<endl;
            cout<<"*                                            *"<<endl;
            cout<<"*   1.Enter elements in the list.            *"<<endl;
            cout<<"*   2.Enter the list's elements in the tree. *"<<endl;
            cout<<"*   3.Show list elements.                    *"<<endl;
            cout<<"*   4.Exit the programme.                    *"<<endl;
            cout<<"*                                            *"<<endl;
            cout<<"**********************************************"<<endl;
            cin>>n;
      }while(n<1&&n>4);

      return n;
}



int main()        //main function
{
      int n;

      do
      {
            n=menu();

            switch(n)
            {
                  case 1:      {int n;
                                    cout<<"Enter elements in the list:"<<endl;
                                    do
                                    {
                                          cin>>n;
                                          add(n);
                                    }while(n!=0);
                                    break;
                                    }
                  case 2:record();break;
                  case 3:show(root,hight(root));break;
                  case 4:cout<<"End of the program"<<endl;break;
            }
      }while(n!=4);

      return 0;
}

[jonnin]

I don't fully understand the question. but this may help you...
the BST is usually coded less left, greater right (equal arbitrary). So the root is typically the median value for balance, and the next nodes are the left and right halves' medians, and so on.. its the binary search!
so if you had 1-10 as a list...
pick 5 as the root. now you have 1234 and 6789 10 as a pair of lists.
now pick the center of those... then you have 4 lists pick the center of those (begs recursion, if you see the pattern.. but since its powers of 2 you can also cook up the correct index to pull from the list each time... esp if that list were instead a vector to begin with)

   5
  2   8
1 3  6 9

if I did that right, it looks something like that, picking the rounded down side of the center element each time …


so, if you just insert using the less left/ greater right idea, and peel off from the list using this modified binary search element choosing, it will produce a balanced tree. And all you had to do is 'insert in order' to produce it on the tree side, because the work was done by sorting and picking from the list side.

Its been forever since I used a tree but from what I recall, rebuilding the tree into a new one as a one time copy is a more efficient balance than trying to balance in place. Maybe someone here knows if I am remembering that right or not. (copying pointers, not the data, of course).