How do I change a root after a double rotation?

[vaderboi]

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

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.

#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 

[lastchance]

@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

		k1->left = k2;

		k1->right = k3;

to

                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

[vaderboi]

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).