Balancing a Binary Tree

[whitehatmiracle]

Hello
I have written a program for a binary tree. On compiling one has to
first chose option 1 and then delete or search. Im having some trouble
with the balancing function. It seems to be going into an infinite
loop, i think im messing up with the pointers.

Heres the code.

//press 1, first, Do not press it a second time!!!

#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>


const int size = 15;
int a[size] =
{800,400,600,300,500,350,450,550,700,650,750,730,900,720,740};
//int a[size] = {800, 700, 750,720,770};
int counter1, counter2; //for traverse
//int a[size];

// "node" is a struct for a binary tree.
struct node{
int number;
char direction;
struct node *left, *right, *parent;
};


node *tmp =NULL;
// node pointers
node *p, *root; //p = current node (temp node)

void make_tree(node *p, int num);
void search_tree();
node* search_pos(node* p ,int num); //search tree looks for the return
//void add_element();
void delete_node(node *current);
void delet();
void balance_tree(node *tmp);
void print_tree( node *tmp, int w, int z, int t);
int get_choice();
void add2tree();
int left_trav(node *p);
int right_trav(node *p);

int x, y;
int w=32,z=2, t=32; //t responsible for offset (spread)
int del_element=0;

//int choice;


int main()
{
int choice;
/*
for (int k=0; k < size; k++)
a[k] = random(1000);
*/
while(1) {
choice = get_choice();
switch(choice){
case 1: add2tree(); break;
case 2: clrscr(); print_tree(root, w, z, t);delet();break;
case 3: search_tree();break;
case 4: balance_tree(root); break;
case 5: clrscr(); print_tree(root, w, z, t); getch(); break;
case 6: break;
default: break;
} // switch
if (choice == 6) break;
} // while
// getch();
return 0;
} // main

int get_choice() {
int choice;
clrscr();
gotoxy(15,5);
cout<<"\n1. Add to Tree";
cout<<"\n2. Delete from Tree";
cout<<"\n3. Search the Tree";
cout<<"\n4. Balance the Tree";
cout<<"\n5. Print the Tree";
cout<<"\n6. Quit ";
cout<<"Enter your choice ( 1 - 6) : ";
int x= wherex();
int y = wherey();
while(1) {
gotoxy(x,y);
clreol();
cin >> choice;
if ( ( choice >0 ) && ( choice <=6 ) )
return choice;
putch(7);
}
}

void add2tree() {
int num;
for ( int i =0; i < size; i++) {
num = a;
node *p = new node;
if ( p == NULL ) {
cout << "cannot assign memory" << endl;
exit(1);
}
p -> number = num;
p -> right = NULL;
p -> left = NULL;
p -> parent = NULL;
make_tree(p, num);
} //for

getch();

}

void print_tree(node *temp, int w, int z, int t){
t=t/2; // t =32 is the offset
if (temp!= NULL) {
print_tree(temp->left, w-t, z+3, t);
// getch();
gotoxy(w,z);
cout<<temp->number;
print_tree(temp->right, w+t, z+3, t);

}
}

void search_tree() {
int num;
node *current;
node *tmp = root; // Tmp scans list
clrscr();
if (root == NULL) {
cout << "THE TREE IS EMPTY ...";
getch();
}
else {
while (1) {
clrscr();
print_tree(root,w,z,t);
gotoxy(15,25);
cout << "Enter the element you want to search for (-1
to quit): ";
cin >> num;
if (num == -1)
break;

current = search_pos(tmp, num); ////
if (current == NULL)
cout << endl<<num << " was not found in the
tree...";
getch();
}

// if (current == NULL)
// cout << endl<<num << " was not found in the
tree...";
getch();
} // while
} // else

void make_tree(node *p, int num)
{
node *temp = root;
if ( root == NULL ) { //root =current
root = p;
root -> direction = 'o';
}
else { // if root exists
while(1) {

/////////////////////////////////left side of tree ///////////

if ( num < temp -> number ) { // left branch of tree
if ( temp -> left != NULL ) {
temp = temp -> left;
continue; //goes back to the while(1) above
}
else {
temp -> left = p;
p -> direction = 'l';
p -> parent = temp;
} // else
break;
} // end left side

/////////////////////// right side of tree///////////////

if( num > temp -> number ) { // right link
if ( temp -> right != NULL ) { // if right
sidecontains a val
temp = temp -> right; // right link becomes temp
continue;
}
else { // if a right link does not exist
temp -> right = p;
p -> parent = temp;
p->direction = 'r';
} // else
break;
}

if ( temp != p )
continue;
} // while(1)

} // else (if root exists)
}

void delete_node(node* current) {
// node is a leaf
if ( (current->left ==NULL) && (current->right==NULL) ){
if (current ==root)
root = NULL;
if (current->direction =='l')
current->parent->left= NULL;
if (current -> direction=='r')
current->parent->right = NULL;

}

// left node is empty, chk right node
if (current->direction ==NULL){
if (current->direction == 'o'){
current->right-> direction = 'o';
current -> right -> parent = NULL;
root = current ->right;
}
else
if ( current -> direction == 'l' ) {
current -> right -> direction = 'l';
current -> right -> parent = current -> parent;
current -> parent -> left = current -> right ;
}
else { // if ( current -> direction== 'r' )
current -> parent -> right = current -> right;
current -> right -> parent = current -> parent;
}
}
/////////if the right tree is not empty

if (current->right == NULL) { // right tree is empty, left tree not
empty
if ( current -> direction == 'o' ) { // but left is not
empty
current -> left -> direction = 'o';
current -> left -> parent = NULL;
root = current -> left;
}
else
if ( current -> direction == 'l' ) {
current -> parent -> left = current -> left;
current -> left -> parent = current -> parent;
}
else { // if ( current -> direction == 'r' )
current -> left -> direction = 'r';
current -> left -> parent = current -> parent;
current -> parent -> right = current -> left;
}
}

else {
////////// // case if both subtrees exist

node *previous = current -> right;
if ( current -> direction == 'o' ) {
root = previous;
current -> right -> direction = 'o';
current -> right -> parent = NULL;
while ( previous -> left != NULL ) {
previous = previous -> left;
//
////////
}
current -> left -> parent = previous;
previous -> left = current -> left;
} //if

else
if ( current -> direction == 'l' ) {
current -> right -> direction= 'l';
previous -> parent = current -> parent;
current-> parent -> left = previous;
while ( previous -> left != NULL ) {
previous = previous -> left;
////////

}
current -> left -> parent = previous;
previous -> left = current -> left;
}
else {
// current-> direction== 'r'
previous -> parent = current-> parent;
current -> parent -> right = previous;
while ( previous -> left != NULL ) {
previous = previous -> left;
continue;
}
current-> left -> parent = previous;
previous -> left = current-> left;
}
}

{}
{}

delete current;
}

void delet(){
while(1) {
if ( !root) {
cout << "empty tree\n";
getch();
break;
}
clrscr();
print_tree(root, w, z, t);

gotoxy(25,25);
cout<<"\nEnter the element you want to delete( -1 to quit): ";
cin>>del_element;
if (del_element == -1 )
break;
node *current = search_pos(root, del_element);
delete_node(current);
getch();
} // while
}

void balance_tree(node *tmp){

node *predecessor, *mid_node=root;
int left_nodes, right_nodes, diff, tmp_root; //
// int counter1 = 0, counter2 = 0;
while (1) {
// int counter1 = 0, counter2 = 0;

//count the number of nodes on both side of root
left_nodes = left_trav(mid_node->left);
right_nodes = right_trav(mid_node->right);
//if the |diff| <= 1,=>root node is root
diff = left_nodes - right_nodes;
if ( abs( diff) <= 1 )
break;
// left tree > right tree then predecessor is rightmost of 1st left
node
if ( diff > 0 ) {
predecessor = mid_node -> left ;

while ( predecessor -> right != NULL )
predecessor = predecessor -> right;

node *tempo;
tempo = predecessor -> left;
if ( predecessor != mid_node -> left ) {
if ( tempo != NULL ) {
while ( tempo != NULL && tempo -> left != NULL ) {
tempo = tempo -> left;
}
} // if tempo != NULL
mid_node -> left -> parent = tempo; ////// problem
tempo -> left = mid_node -> left;
predecessor -> parent -> right = NULL;
} // predecessor != mid_node -> left

mid_node -> direction = 'r';
predecessor -> parent = mid_node -> parent;
if ( predecessor -> direction == 'l' )
predecessor -> parent -> left = predecessor;

if ( predecessor -> direction == 'r' )
predecessor -> parent -> right = predecessor; // problem 2

mid_node -> parent = predecessor;
mid_node -> left = NULL;
predecessor -> right = mid_node;
if ( mid_node == root ) {
predecessor -> direction = 'o';
root = predecessor;
}
else
predecessor -> direction = 'l';

clrscr();
print_tree(root, w, z, t);
getch();

mid_node = predecessor;

} // if left tree > right tree then predecessor is rightmost
....
// if right tree > left tree, then predecessor is leftmost of 1st
right node
else { // right tree > left tree
predecessor = mid_node -> right;
while ( predecessor -> left != NULL )
predecessor = predecessor -> left;

node *tempo2;
tempo2 = predecessor -> right;
if ( predecessor != mid_node -> right ) {
if ( tempo2 != NULL ) {
while ( tempo2 != NULL && tempo2 -> right != NULL )
{
tempo2 = tempo2 -> right;
}
}
mid_node -> right -> parent = tempo2;
tempo2 -> right = mid_node -> right;
predecessor -> parent -> left = NULL;
}
mid_node -> direction = 'l';
predecessor -> parent = mid_node -> parent;
if ( predecessor -> direction == 'r' )
predecessor -> parent -> right = predecessor;

if ( predecessor -> direction == 'l' )
predecessor -> parent -> left = predecessor;

mid_node -> parent = predecessor;
mid_node -> right = NULL;
predecessor -> left = mid_node;
if ( mid_node == root ) {
predecessor -> direction = 'o';
root = predecessor;
}
else
predecessor -> direction = 'r';

clrscr();
print_tree(root, w, z, t);
getch();
mid_node = predecessor;
} // else right tree > left tree
gotoxy(2,23);
cout << "end of one interation";
getch();
counter1=0;counter2=0;
} // while

//count the sub trees

if ( mid_node -> right != NULL )
balance_tree( mid_node -> right);

if ( mid_node -> left != NULL )
balance_tree( mid_node -> left );


}

node* search_pos(node* tmp, int num){
// node *tmp=root;
if (tmp!= NULL) {
if (tmp->number==num)
return tmp;
if (num < tmp->number)
search_pos(tmp->left, num);
else
if (num > tmp->number)
search_pos(tmp->right, num);
}
else
return NULL;
}

int left_trav(node *p){
int lcounter;
if (p != NULL )
counter1++;
else
return counter1;
lcounter = left_trav(p->left);
lcounter = left_trav(p->right);
}

int right_trav(node *p){
int rcounter;
if (p != NULL )
counter2++;
else
return counter2;
rcounter = right_trav(p->left);
rcounter = right_trav(p->right);

}

 

[Ben Pfaff]

I have written a program for a binary tree. On compiling one has to
first chose option 1 and then delete or search. Im having some trouble
with the balancing function. It seems to be going into an infinite
loop, i think im messing up with the pointers.

I wouldn't bother to implement that balancing algorithm. It's
both slower and harder to implement than more efficient
approaches. Try the one described here:
http://adtinfo.org/libavl.html/Balancing-a-BST.html
(This is my webpage.)

 

[Beej]

Try the one described here:

A red-black tree is another good form of balanced BST.

-Beej

 

[Richard Heathfield]

[Off-topic in comp.lang.c - crossposted to comp.programming and
followups set.]

Ben Pfaff said:

I wouldn't bother to implement that balancing algorithm. It's
both slower and harder to implement than more efficient
approaches.

I couldn't decode his code sufficiently to tell whether your advice to
him would also constitute advice to me, so I'd appreciate feedback.

My technique is this: each node keeps counts of its left children and
right children. (Housekeeping is done when nodes are promoted and when
nodes are deleted.) To balance a tree, I use the child-counts to dodge
left or right until I've found the ideal root node (the one which will
have equally populated subtrees, +/- 1 of course), and I rotate that
node to the root. Then I recurse into the subtrees. It works well and
I'm happy with the performance. Shouldn't I be?

 

[Jeffrey Stedfast]

I wouldn't bother to implement that balancing algorithm. It's
both slower and harder to implement than more efficient
approaches. Try the one described here:
http://adtinfo.org/libavl.html/Balancing-a-BST.html
(This is my webpage.)

Thought I knew your name from somewhere... ;-)

Jeff