recategorized by
489 views

1 Answer

0 votes
0 votes

I prepare one greedy algorithm but restriction that balancing the tree is not guaranteed.

note that i used double linkedlist because of left and right childs named it as node.

 

take your input in array A,

int highest_lessthan_of_n; 

int lowest_graterthan_of_n;

int lessthan_updated_index_of_n;

int graterthan_updated_index_of_n;

B ----> is a list which indicates, inserted nodes in BST, list property is nodes added as linked list at the end

for each A[i]

   n=new node with value of A[i];

   if BST is empty

   {

                 insert a node in BST with value of A[i];

                 add node into the list B;

                 return;

    }

    else

    {

         

              highest_lessthan_of_n = + Infinity ;

              lowest_graterthan_of_n = - Infinity ;

              lessthan_updated_index_of_n = -1 ;   ----> -1 indicting not updated

              graterthan_updated_index_of_n = -1 ;

              for each B[i]

              {

                                if( n.value > B[i] ) 

                                {

                                      if  (  highest_lessthan_of_n < B[i] )

                                      {

                                            highest_lessthan_of_n = B[i];

                                             lessthan_updated_index_of_n = i ; 

                                      }

                                }

                                if( n.value < B[i] ) 

                                {

                                      if (  lowest_graterthan_of_n > B[i] )

                                      {

                                            lowest_graterthan_of_n = B[i];    

                                             graterthan_updated_index_of_n = i ; 

                                       }

                                }

              }

              if( lessthan_updated_index_of_n > graterthan_updated_index_of_n ) ----->  lessthan_updated_index_of_n is recently updated

                                add new node as right of the  lessthan_updated_index_of_n;

              if( graterthan_updated_index_of_n > lessthan_updated_index_of_n ) ----->  graterthan_updated_index_of_n is recently updated

                                add new node as left of the  graterthan_updated_index_of_n;

              add node into the list B;

              return ;

     }

    

 

Related questions

0 votes
0 votes
1 answer
1
0 votes
0 votes
1 answer
2