473,221 Members | 1,836 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,221 software developers and data experts.

Balancing a Binary Tree

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,9 00,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[i];
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);

}

Feb 13 '07 #1
4 10972
wh*************@gmail.com writes:
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.)
--
Ben Pfaff
bl*@cs.stanford.edu
http://benpfaff.org
Feb 13 '07 #2
On Feb 12, 5:13 pm, Ben Pfaff <b...@cs.stanford.eduwrote:
Try the one described here:
A red-black tree is another good form of balanced BST.

-Beej

Feb 13 '07 #3
[Off-topic in comp.lang.c - crossposted to comp.programming and
followups set.]

Ben Pfaff said:
wh*************@gmail.com writes:
>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.
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?

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.
Feb 13 '07 #4
Ben Pfaff wrote:
wh*************@gmail.com writes:
>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.)

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

Jeff
Feb 14 '07 #5

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

1
by: Jerry Khoo | last post by:
hello, everybody, i am kinda new here, nice to meet u all. Now, i am > cs students and are now facing difficult problems in understanding > what a binary tree is, how it works, and the algorithm...
8
by: Jerry Khoo | last post by:
hello, everybody, i am kinda new here, nice to meet u all. Now, i am cs students and are now facing difficult problems in understanding what a binary tree is, how it works, and the algorithm to...
11
by: jova | last post by:
Is there a difference between a Binary Tree and a Binary Search Tree? If so can someone please explain. Thank You.
4
by: Tarique Jawed | last post by:
Alright I needed some help regarding a removal of a binary search tree. Yes its for a class, and yes I have tried working on it on my own, so no patronizing please. I have most of the code working,...
5
by: pembed2003 | last post by:
Hi, I have a question about how to walk a binary tree. Suppose that I have this binary tree: 8 / \ 5 16 / \ / \ 3 7 9 22 / \ / \ / \
15
by: Foodbank | last post by:
Hi all, I'm trying to do a binary search and collect some stats from a text file in order to compare the processing times of this program (binary searching) versus an old program using linked...
5
by: scbauer | last post by:
Im working on an AVL tree that consists of balancing the tree everytime you add an object. Im not quite grasping the concept on how to do this with python. I have seen a few topics on the web about...
1
by: hn.ft.pris | last post by:
I have the following code: Tree.h defines a simple binary search tree node structure ########## FILE Tree.h ################ #ifndef TREE_H #define TREE_H //using namespace std; template...
7
by: Vinodh | last post by:
Started reading about Binary Trees and got the following questions in mind. Please help. Definition of a Binary Tree from "Data Structures using C and C++ by Tanenbaum" goes like this, "A...
0
by: veera ravala | last post by:
ServiceNow is a powerful cloud-based platform that offers a wide range of services to help organizations manage their workflows, operations, and IT services more efficiently. At its core, ServiceNow...
0
by: mar23 | last post by:
Here's the situation. I have a form called frmDiceInventory with subform called subfrmDice. The subform's control source is linked to a query called qryDiceInventory. I've been trying to pick up the...
0
by: abbasky | last post by:
### Vandf component communication method one: data sharing ​ Vandf components can achieve data exchange through data sharing, state sharing, events, and other methods. Vandf's data exchange method...
2
by: jimatqsi | last post by:
The boss wants the word "CONFIDENTIAL" overlaying certain reports. He wants it large, slanted across the page, on every page, very light gray, outlined letters, not block letters. I thought Word Art...
2
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 7 Feb 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:30 (7.30PM). In this month's session, the creator of the excellent VBE...
0
by: fareedcanada | last post by:
Hello I am trying to split number on their count. suppose i have 121314151617 (12cnt) then number should be split like 12,13,14,15,16,17 and if 11314151617 (11cnt) then should be split like...
0
by: stefan129 | last post by:
Hey forum members, I'm exploring options for SSL certificates for multiple domains. Has anyone had experience with multi-domain SSL certificates? Any recommendations on reliable providers or specific...
1
by: davi5007 | last post by:
Hi, Basically, I am trying to automate a field named TraceabilityNo into a web page from an access form. I've got the serial held in the variable strSearchString. How can I get this into the...
0
by: MeoLessi9 | last post by:
I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.