### 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
 ``123`` ``````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.

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243`` ``````#include #include using namespace std; template 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 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
 ``123`` `````` k1->left = k2; k1->right = k3;``````

to
 ``123`` `````` 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.