C++

Forum

 
Re-pointing pointers

Smac89 (1727)
I have an avl tree data structure which I am working on. The part I need help with is the left_rotate function. After it runs, the tree does not have some of it's information anymore; and this is evident when I use inorder traverse.

If any is familiar with this, what is the best way to do left_rotate/right_rotate so that the tree contains all it's information.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
 
#include <cstdio>
#include <cstdlib>
#include <string>
#include <sstream>
#include <algorithm>
#define BF(A, B) (A-B)

template <typename T>
class Avl_Tree {

/*Variables */
	int level;
	Avl_Tree <T> *left, *right;
	T info;
	bool InfoIntialised;
/*Vairables end */
	
	std::string
	__to_string__(const T& t) {
		std::ostringstream os;
		os << t;
		return os.str();
	}
	
	std::string
	__inorderTraverse__() {
		return
		(left->InfoIntialised ? left->__inorderTraverse__() : "") +
		to_string(info) + " " +
		(right->InfoIntialised ? right->__inorderTraverse__()+" " : "");
	}
	
	void
	setValues ( const T& val ) {
		SetInfo(val);
		level = 0;
		SetLeft(new Avl_Tree(-1));
		SetRight(new Avl_Tree(-1));
	}
	
	void 
	Left_rotate ()  {
		printf("Doing a left rotate %s\n", to_string(info).c_str());
		level = ~-level;
		Avl_Tree <T> *tmp(right->left);
		right->left->SetRight(tmp);
		right->left->SetInfo(info);
		right->left->SetLeft(left);
		SetInfo(right->info);
		SetRight(right->right);
		SetLeft(right->left);
	}
	
	int
	__insert__ (T val) {
		if ( !InfoIntialised ) setValues(val);
		else
		switch ( val < info ) {
			case 1:
				level = -~std::max (left->__insert__(val), right->level);
				if ( BF( left->level, right->level ) < -1 ) Left_rotate (); //Right-heavy
				break;
			case 0:
				level = -~std::max (right->__insert__(val), left->level);
				if ( BF( left->level, right->level ) < -1 ) Left_rotate ();
				break;
		}
		return level;
	}
	

public:	
	
	Avl_Tree( int pos=-1 )
	:level(pos), left(NULL), right(NULL),
	InfoIntialised(false)
	{}
	
	void
	insert( const T& val ) {
		__insert__(val);
		printf("%s\n", inorderTraverse().c_str());
		printf("height left -> %d | heigh right -> %d\n", left->level, right->level);
	}
	
	std::string
	to_string( const T& t ) {
		return __to_string__(t);
	}
	
	std::string
	inorderTraverse() {
		return __inorderTraverse__();
	}
	
	T
	GetInfo() const {
		return info;
	}
	
	Avl_Tree <T>
	*GetRight() const {
		return right;
	}
	
	Avl_Tree <T>
	*GetLeft() const {
		return left;
	}
	
	void
	SetInfo( const T& k ) {
		InfoIntialised = true;
		info = k;
	}
	
	void
	SetRight ( Avl_Tree <T> *r ) {
		right = r;
		right->level = level - 1;
	}
	
	void
	SetLeft ( Avl_Tree <T> *l ) {
		left = l;
		left->level = level - 1;
	}
	
};

int main() {
	Avl_Tree <int> Tree;
//	Tree.insert(1);
//	Tree.insert(4);
//	Tree.insert(3);
//	Tree.insert(5);
//	Tree.insert(6);
//	Tree.insert(2);
//	Tree.insert(0);
	for ( int k = 0; k <= 5; k++ ) Tree.insert(k);
	printf("%s\n", Tree.inorderTraverse().c_str());
	return 0;
}


I guess what I'm asking is in what order should I rotate the tree so that I don't delete some links?
Last edited on
Computergeek01 (5613)
Why all the obfuscation? Did you copy this from somewhere or something?
Smac89 (1727)
Lol nope. I just wanted to make it that way. I plan to use this to implement a hashtable; which is why I am going through all the trouble

OT/
I don't want to have to create a totally new tree in the rotation instead I just want to move the pointers to point at something else. The reason for this is that memory allocation is slow and having to create new trees just to rotate seems to me like a waste.

Here is the new implementation I came up with for left_rotate, this one produces seg fault though:
1
2
3
4
5
6
7
8
9
10
11
12
 
void 
Left_rotate ()  {
	printf("Doing a left rotate %s\n", to_string(info).c_str());
	level = right->level;
	T t_info(info);
	Avl_Tree <T> *&tmp(left), *&tmp2(right->left);
	SetInfo(right->info);
	SetRight(right->right);
	left->SetInfo(t_info);
	left->SetLeft(tmp);
	left->SetRight(tmp2);
}


Not sure why it produces a seg fault. I have drawn out the procedure and I don't see a seg fault anywhere.

BTW using this as a guide: http://pages.cs.wisc.edu/~paton/readings/liblitVersion/AVL-Tree-Rotations.pdf
Last edited on
cire (8284)
I just wanted to make it that way. I plan to use this to implement a hashtable;


You're going to use a tree to implement a hash table? Why?

By the way, identifiers beginning with double underscores are reserved to the implementation in any scope. They're typically used for macros, which means they are not safe to use in your own code, whereas identifiers beginning with only a single underscore are only reserved for global namespace.

Your code is fairly unreadable and the design is horrid. If this were my class, I'd begin debugging by redesigning.

On line 6, what do you think thing using references buys you?
On line 8, what happens to the previous right value?
On line 9, what happens to the the info previously stored in left?
On line 10, what happens to the..?


Last edited on
Smac89 (1727)
You're going to use a tree to implement a hash table? Why?

Used to handle collisions
Smac89 (1727)
Decided to scrap old one. New implementation:

AVL.h
1
2
3
4
5
 
template <typename T> struct avl_tree {
	T data;
	int balance;
	struct avl_tree <T> *Link[2];
};



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
 
#include <new>
#include <iostream>
#include "AVL.h"

/*
template <typename T> avl_tree <T> *insert ( avl_tree <T>*, T );
template <typename T> avl_tree <T> *create ( T );
template <typename T> avl_tree <T> *rotate ( avl_tree <T>*, int );
template <typename T> avl_tree <T> *rotate_double ( avl_tree <T>*, int );
template <typename T> avl_tree <T> *BalanceNeeded ( avl_tree <T>*, int, int );
*/

namespace AVL_TREE {
	
	/***********MACROS**************/
	#define None 0L
	#define height(R) ((R) == None ? -1 : (R)->balance)
	#define avl_max(a,b) (a > b ? a : b)
	/*********MACROS*END************/
	
	
	
	/**********FUNCTIONS************/
	
	template <typename T> 
	avl_tree <T> *rotate ( avl_tree <T> *root, int dir ) {
		/*Rotation here*/
		avl_tree <T> *tmp(root->Link[!dir]);
		root->Link[!dir] = tmp->Link[dir];
		tmp->Link[dir] = root;
						
		/*Calculate new length*/
		int rll(height(root->Link[0])), rrl(height(root->Link[1]));
		root->balance = 1 + avl_max(rll, rrl);
		
		/*Update Balance factor*/
		int lll(height(tmp->Link[!dir])), lrl(root->balance);
		tmp->balance = 1 + avl_max(lll, lrl);
		
		return tmp;
	}
	
	template <typename T> 
	avl_tree <T> *rotate_double ( avl_tree <T> *root, int dir ) {
		root->Link[!dir] = rotate( root->Link[!dir], !dir);	
		return rotate (root, dir);
	}
	
	template <typename T>
	avl_tree <T> *create ( T info ) {
		avl_tree <T> *Tree = new (std::nothrow) avl_tree <T>;
		if ( Tree ) {
			Tree->data = info;
			Tree->Link[0] = Tree->Link[1] = None;
		}
		return Tree;		
	}
	
	template <typename T> 
	avl_tree <T> *BalanceNeeded ( avl_tree <T> *root, int dir, int bal ) {
		if ( bal > 1 || bal < -1 ) {
		//Only rotate if one side has length of 2 more than other side
			avl_tree <T> *a(root->Link[dir]->Link[dir]), *b(root->Link[dir]->Link[!dir]);
			if ( height(a) >= height(b) ) root = rotate(root, !dir); //Avoid zig-zag growth!
			else root = rotate_double (root, !dir);
			//!dir means to rotate in the opposite direction tree is growing
		}
		return root;
	}
	
	template <typename T>
	avl_tree <T> *insert ( avl_tree <T>* root, T info ) {
		int w, lh, rh;
		switch ( root == None ) {
			case 1:
				root = create(info);
				root->balance = 0;
				break;
			case 0:
				w = (root->data <= info); //True means we go right otherwise left
				root->Link[w] = insert( root->Link[w], info );
				lh = height( root->Link[w] ); //Update left height
				rh = height( root->Link[!w] );//Update right height
				root->balance = 1 + avl_max( rh, lh ); //Set new height to max of left and right
				root = BalanceNeeded( root, w, lh-rh );			
				break;
		}
		return root;
	}
	
	/*********FUNCTIONS*END*********/
	
}

int main() {
	avl_tree <int> *tree;
	for ( int t = 0; t <= 7; ++t ) {
		tree = AVL_TREE::insert( tree, t );
		std::cout << tree->balance << std::endl;
	}
	return 0;
}



Still need to add delete method, but it is a work in progress
Last edited on
Smac89 (1727)
Delete is probably the most complicated

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
 
#include <new>
#include "AVL.h"
#include <iostream>

/*
template <typename T> avl_tree <T> *insert ( avl_tree <T>*, const T& );
template <typename T> avl_tree <T> *create ( const T& );
template <typename T> avl_tree <T> *rotate ( avl_tree <T>*, int );
template <typename T> avl_tree <T> *rotate_double ( avl_tree <T>*, int );
template <typename T> avl_tree <T> *BalanceNeeded ( avl_tree <T>*, int, int );
template <typename T> avl_tree <T> *remove ( avl_tree <T>*, const T& );
*/

namespace AVL_TREE {
	
	/***********MACROS**************/
	#define None 0L
	#define height(R) ((R) == None ? -1 : (R)->balance)
	#define avl_max(a,b) (a > b ? a : b)
	/*********MACROS*END************/

	
	/**********FUNCTIONS************/
	
	template <typename T> 
	avl_tree <T> *rotate ( avl_tree <T> *root, int dir ) {
		/*Rotation here*/
		avl_tree <T> *tmp(root->Link[!dir]);
		root->Link[!dir] = tmp->Link[dir];
		tmp->Link[dir] = root;
						
		/*Calculate new length*/
		int rll(height(root->Link[0])), rrl(height(root->Link[1]));
		root->balance = 1 + avl_max(rll, rrl);
		
		/*Update Balance factor*/
		int lll(height(tmp->Link[!dir])), lrl(root->balance);
		tmp->balance = 1 + avl_max(lll, lrl);			
		
		return tmp;
	}
	
	template <typename T> 
	avl_tree <T> *rotate_double ( avl_tree <T> *root, int dir ) {
		root->Link[!dir] = rotate( root->Link[!dir], !dir);	
		return rotate (root, dir);
	}
	
	//Creates and returns a new tree with info
	template <typename T>
	avl_tree <T> *create ( const T& info ) {
		avl_tree <T> *Tree = new (std::nothrow) avl_tree <T>;
		if ( Tree ) {
			Tree->data = info;
			Tree->Link[0] = Tree->Link[1] = None;
		}
		return Tree;		
	}
	
	//Called after every insertion to determine if tree needs rotation
	template <typename T> 
	avl_tree <T> *BalanceNeeded ( avl_tree <T> *root, int dir, int bal ) {
		if ( bal > 1 || bal < -1 ) {
		//Only rotate if one side has length of 2 more than other side
			avl_tree <T> *a(root->Link[dir]->Link[dir]), *b(root->Link[dir]->Link[!dir]);
			if ( height(a) >= height(b) ) root = rotate(root, !dir);
			else root = rotate_double (root, !dir);//zig-zag is a pain!
			//!dir means to rotate in the opposite direction tree is growing
		}
		return root;
	}
	
	//Insert function
	template <typename T>
	avl_tree <T> *insert ( avl_tree <T>* root, const T& info ) {
		int w, lh, rh;
		switch ( root == None ) {
			case 1:
				root = create(info);
				root->balance = 0;
				break;
			case 0:
				w = (root->data <= info); //True means we go right otherwise left
				root->Link[w] = insert( root->Link[w], info );
				lh = height( root->Link[w] ); //Update left height
				rh = height( root->Link[!w] );//Update right height
				root->balance = 1 + avl_max( rh, lh ); //Set new height to max of left and right
				root = BalanceNeeded( root, w, lh-rh );			
				break;
		}
		return root;
	}
	
	
	//A delete function
	template <typename T>
	avl_tree <T> *remove ( avl_tree <T>* root, const T& info )  {
	
		#ifdef DEBUG
			std::cout << "Current height of the tree is " << root->balance << std::endl;
			std::cout << "Info to delete " << info << std::endl;
		#endif
		
		int m, inc[root->balance + 1], n(0), lh, rh;
		avl_tree <T> *tmp(root), *crawler[root->balance + 1];
		while ( root != None ) {
			if ( root->data == info ) break;
			m = (root->data < info);
			inc[n] = m;
			crawler[n++] = root;
			root = root->Link[m];
		}
		if ( root == None ) return tmp; //Information not found :(
		
		//if deleted tree has 1 or 0 branches
		if ( root->Link[1] == None || root->Link[0] == None ) {
			//Link deleted node's child to current link
			int dir = root->Link[0] == None;
			crawler[n-1]->Link[inc[n-1]] = root->Link[dir];
		}
		else {
			//Tree to delete has 2 children, here we go...
			crawler[n] = root; //Save the Node to be "deleted"
			inc[n++] = 1; 
			avl_tree <T> *crown = root->Link[1]; //Go to the right subtree
			
			//Travel as left as we can to crown new king
			while ( crown->Link[0] != None ) {
				crawler[n] = crown;
				inc[n++] = 0;
				crown = crown->Link[0];
			}
			//Found new king, simply swap info
			root->data = crown->data;
			
			//Create a link to the new tree
			crawler[n-1]->Link[crawler[n-1] == root] = crown->Link[1];
			//crawler[n-1] == root
			//if the above while loop did not run once, this means the right
			//child of the node to delete did not have a left child
			
			//Can choose to delete the unsable tree or save it for later use
		}
		
		//Walk back up the tree and rebalance as needed
		
		#ifdef DEBUG
			std::cout << "Moonwalk...\n";
		#endif //DEBUG
		
		while ( --n >= 0 ) {
			lh = height(crawler[n]->Link[inc[n]]);
			rh = height(crawler[n]->Link[!inc[n]]);
			crawler[n]->balance = 1 + avl_max(lh, rh);
			crawler[n] = BalanceNeeded( crawler[n], lh > rh ? inc[n] : !inc[n], lh-rh );
			if (n) crawler[n-1]->Link[inc[n-1]] = crawler[n];
		}
		
		#ifdef DEBUG
			std::cout << "Tree balance is " << crawler[0]->balance
			<< ". Tree data is " << crawler[0]->data << std::endl;
		#endif		
		return crawler[0];
	}
	
	/*********FUNCTIONS*END*********/
	
}

int main() {
	avl_tree <int> *tree(0);
	for ( int r = 0; r < 1000000; ++r ) {
		tree = AVL_TREE::insert( tree, r );
		if ( r % 100000 == 0 ) {
			for ( int f = r; f > 0; f >>= 4 )
				tree = AVL_TREE::remove(tree, f);
		}
		
	}
	delete [] tree;
	return 0;
}
Topic archived. No new replies allowed.