How do I change a root after a double rotation?

I am writing a program where I am attempting to perform a right-left double rotation on a binary search tree without having to call two single rotation functions. This problem is given in my textbook Data Structures and Algorithm Analysis in C++ (Fourth Edition) by Mark Allen Weiss on page 185, problem 4.26:
Write the functions to perform the double rotation without the inefficiency of doing
two single rotations
Most of the code is copied from the textbook website at https://users.cs.fiu.edu/~weiss/dsaa_c++4/code/ unless otherwise stated.

In main() (line 226), I inserted a series of integers and then printed a visual of the BST tree that was constructed. Where the program broke was when I attempted to insert 13 in to the tree (on line 239). When a node is inserted, the balance() function (line 110) is called and performs a specific rotation based on where the node was inserted. In this case, doubleWithLeftChild() (line 206) is called. The entire program ran fine until I added
1
2
3
k1->left = k2; 
k1->right = k3; 
k3 = k1;

at line 214. When this is added, the command line outputs the correct tree up until 13 is inserted. At that point it infinitely calls makeEmpty(AvlNode * & t) (line 126) which is a function that is recursively called by the destructor until the entire tree has been deleted from memory.

Is there a reason why makeEmpty(AvlNode * & t) is being called infinitely? Why isn't the code I added in doubleWithLeftChild() sufficient to perform a right-left double rotation? Why didn't my root set correctly? Any help is appreciated.

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
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
#include <algorithm>
#include <iostream> 
using namespace std;

template <typename Comparable>
class AvlTree
{
public:
	AvlTree() : root{ nullptr }
	{ }

	~AvlTree()
	{
		makeEmpty();
	}

	/**
	 * Make the tree logically empty.
	 */
	void makeEmpty()
	{
		makeEmpty(root);
	}

	/**
	 * Insert x into the tree; duplicates are ignored.
	 */
	void insert(Comparable && x)
	{
		insert(std::move(x), root);
	}

	/**
	 * Remove x from the tree. Nothing is done if x is not found.
	 */
	void remove(const Comparable & x)
	{
		remove(x, root);
	}

	//MY CODE
	void beginOfPrintTreeVisual()
	{
		printTreeVisual(root, 0);
	}
	//END OF MY CODE

private:
	struct AvlNode
	{
		Comparable element;
		AvlNode   *left;
		AvlNode   *right;
		int       height;
	};

	AvlNode *root;

	/**
	 * Internal method to insert into a subtree.
	 * x is the item to insert.
	 * t is the node that roots the subtree.
	 * Set the new root of the subtree.
	 */
	void insert(Comparable && x, AvlNode * & t)
	{
		if (t == nullptr)
			t = new AvlNode{ std::move(x), nullptr, nullptr };
		else if (x < t->element)
			insert(std::move(x), t->left);
		else if (t->element < x)
			insert(std::move(x), t->right);

		balance(t);
	}

	/**
	 * Internal method to remove from a subtree.
	 * x is the item to remove.
	 * t is the node that roots the subtree.
	 * Set the new root of the subtree.
	 */
	void remove(const Comparable & x, AvlNode * & t)
	{
		if (t == nullptr)
			return;   // Item not found; do nothing

		if (x < t->element)
			remove(x, t->left);
		else if (t->element < x)
			remove(x, t->right);
		else if (t->left != nullptr && t->right != nullptr) // Two children
		{
			t->element = findMin(t->right)->element;
			remove(t->element, t->right);
		}
		else
		{
			AvlNode *oldNode = t;
			t = (t->left != nullptr) ? t->left : t->right;
			delete oldNode;
		}

		balance(t);
	}

	static const int ALLOWED_IMBALANCE = 1;

	// Assume t is balanced or within one of being balanced
	void balance(AvlNode * & t)
	{
		if (t == nullptr)
			return;

		if (height(t->left) - height(t->right) > ALLOWED_IMBALANCE)
		{
			if (height(t->left->left) >= height(t->left->right))
				rotateWithLeftChild(t);
			else
				doubleWithLeftChild(t);
	    }   
	    
		t->height = max(height(t->left), height(t->right)) + 1;
	}

	void makeEmpty(AvlNode * & t)
	{
		std::cout << "Entered makeEmpty( AvlNode * & t) function" << std::endl;
		if (t != nullptr)
		{
			makeEmpty(t->left);
			makeEmpty(t->right);
			delete t;
		}
		t = nullptr;
	}

	void printTreeVisual(AvlNode *currNode, int space) const
	{
		space += 10;

		if (currNode->right)
		{
			printTreeVisual(currNode->right, space);
		}

		std::cout << std::endl;

		for (int i = 0; i < space; ++i)
		{
			std::cout << " ";
		}

		std::cout << currNode->element << std::endl;

		if (currNode->left)
		{
			printTreeVisual(currNode->left, space);
		}
	}

/**
 * Return the height of node t or -1 if nullptr.
 */
	int height(AvlNode *t) const
	{
		return t == nullptr ? -1 : t->height;
	}

	int max(int lhs, int rhs) const
	{
		return lhs > rhs ? lhs : rhs;
	}

	/**
	 * Rotate binary tree node with left child.
	 * For AVL trees, this is a single rotation for case 1.
	 * Update heights, then set new root.
	 */
	void rotateWithLeftChild(AvlNode * & k2)
	{
		AvlNode *k1 = k2->left;
		k2->left = k1->right;
		k1->right = k2;
		k2->height = max(height(k2->left), height(k2->right)) + 1;
		k1->height = max(height(k1->left), k2->height) + 1;
		k2 = k1;
	}

	/**
	 * Rotate binary tree node with right child.
	 * For AVL trees, this is a single rotation for case 4.
	 * Update heights, then set new root.
	 */
	void rotateWithRightChild(AvlNode * & k1)
	{
		AvlNode *k2 = k1->right;
		k1->right = k2->left;
		k2->left = k1;
		k1->height = max(height(k1->left), height(k1->right)) + 1;
		k2->height = max(height(k2->right), k1->height) + 1;
		k1 = k2;
	}

	//MY CODE STARTS HERE
	void doubleWithLeftChild(AvlNode * & k3)
	{
		std::cout << "k3->element: " << k3->element << '\n';
		AvlNode *k2 = k3->left;
		std::cout << "k2->element: " << k2->element << '\n';
		AvlNode *k1 = k3->left->right;
		std::cout << "k1->element: " << k1->element << '\n';

		k1->left = k2;

		k1->right = k3;

		k3 = k1;

	}
        //MY CODE ENDS HERE

};

//MY CODE BEGINS HERE
int main()
{
	AvlTree<int> tree;

	tree.insert(5);
	tree.insert(8);
	tree.insert(19);
	tree.insert(4);
	tree.insert(2);
	tree.insert(11);

	tree.beginOfPrintTreeVisual();

	tree.insert(13);

	return 0;
}
//MY CODE ENDS HERE 
Last edited on
@Vaderboi, before you entered 13, your tree looked like this balanced AVL tree:
     _ 5 _ 
    |     |
  _ 4     8 _ 
 |           |
 2        __ 19 
         |
         11 


Once you entered 13, but BEFORE YOU BALANCED, your tree looked like this. It is not an AVL tree and needs balancing.
     _ 5 _ 
    |     |
  _ 4     8 _ 
 |           |
 2        __ 19 
         |
         11 _
             |
             13


Clearly you are trying to play with that bottom right-hand corner. You first assign nodes that look like this:
  ____ k3=19 
 |
 k2=11 ____
           |
           k1=13


You are trying to rotate it so that your whole tree looks like this AVL tree:
     _ 5 _ 
    |     |
  _ 4     8 _ 
 |           |
 2        __ 13 _ 
         |       |
         11      19 


You have correctly ASSIGNED nodes (as far as I can see) but you have NOT REMOVED THE NOW-REDUNDANT LINKS.

k3=19 had a left pointer that needs to be set to null_ptr ... you didn't do this.
k2=11 had a right pointer that needs to be set to null_ptr ... you didn't do this.

I believe that if you change the lines 214-216, which are
1
2
3
		k1->left = k2;

		k1->right = k3;

to
1
2
3
                k1->left = k2;    k2->right=nullptr;

                k1->right = k3;   k3->left=nullptr;

then your code will get past this particular bottleneck. However, I do not believe that this will solve all problems in the future.

You need to go through your code and check that not only do you correctly point to different nodes but you ALSO DEAL WITH EXISTING OPERATIONAL LINKS that may become redundant. Otherwise, you will be left with circular and/or non-existent connections.

YOU MUST DRAW SOME CAREFUL DIAGRAMS.


BTW - I debugged your code using an only slightly changed visualisation of binary trees that I developed in this thread (I had to increase height by 1, as you appear to be using a different definition).
http://www.cplusplus.com/forum/general/265712/#msg1144246
Last edited on
Thank you so much! Making k2->right and k3->left point to nullptr fixed the issue. I will keep this in mind for the future so that I don't have my nodes pointing either to junk data or to nodes that will then point back to them (thereby creating an infinite loop).
Registered users can post here. Sign in or register to post.