AVL double rotation without doing two single rotations

[vaderboi]

I am writing a program that inserts nodes in to a tree and then attempts to balance whatever subtree has a depth more than 1 larger than the subtree next to it. I am trying to make sure that when a double rotation has to occur that it can be done without having to call two single rotation functions.

My program runs fine until I try to insert 13. Inserting a node calls the balance() (at line 130) function which, in this case, calls the doubleWithLeftChild() function (at line 194). After the balancing, the destructor (line 17) is called when main() returns. The destructor calls makeEmpty() (line 22) which calls makeEmpty( AvlNode *& t) (line 150).

In makeEmpty(AvlNode *& t), I put a print statement to see how many times it was called. Whenever I run the program, makeEmpty(AvlNode *& t) is called infinitely. This started occurring after I inserted k1->left = k2 and the code that followed it in doubleWithLeftChild(). But it probably has to do with the line k3 = k1 since if the subtree had been properly balanced then the makeEmpty(AvlNode *& t) function wouldn't be trying to access invalid memory over and over.

Does anyone know how to accomplish a double rotation without doing two single rotations without creating this segmentation fault?

Note: I know there is no doubleWithRightChild() function. I am just trying to get doubleWithLeftChild() to work before I bother with it.


problem26.cpp

#include "my_avl_tree.h"

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_avl_tree.h

#ifndef MY_AVL_TREE_H
#define MY_AVL_TREE_H

#include "dsexceptions.h"
#include <algorithm>
#include <iostream> 
using namespace std;

template <typename Comparable>
class AvlTree
{
  public:
    AvlTree( ) : root{ nullptr }
      { }
    
    ~AvlTree( )
    {
        makeEmpty( );
    }
    
    void makeEmpty( )
    {
        makeEmpty( root );
    }


    /**
     * Print the tree contents in sorted order.
     */
    void printTree( ) const
    {
        if( isEmpty( ) )
            cout << "Empty tree" << endl;
        else
            printTree( root );
    }

    /**
     * Insert x into the tree; duplicates are ignored.
     */
    void insert( const Comparable & x )
    {
        insert( x, 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( const Comparable & ele, AvlNode *lt, AvlNode *rt, int h = 0 )
          : element{ ele }, left{ lt }, right{ rt }, height{ h } { }
        
        AvlNode( Comparable && ele, AvlNode *lt, AvlNode *rt, int h = 0 )
          : element{ std::move( ele ) }, left{ lt }, right{ rt }, height{ h } { }
    };

    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( const Comparable & x, AvlNode * & t )
    {
        if( t == nullptr )
            t = new AvlNode{ x, nullptr, nullptr };
        else if( x < t->element )
            insert( x, t->left );
        else if( t->element < x )
            insert( x, t->right );
        
        balance( t );
    }

    /**
     * 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 );
    }
    
    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 );
        else
        if( height( t->right ) - height( t->left ) > ALLOWED_IMBALANCE )
            if( height( t->right->right ) >= height( t->right->left ) )
                rotateWithRightChild( t );
            else
                doubleWithRightChild( t );
                
        t->height = max( height( t->left ), height( t->right ) ) + 1;
    }

    /**
     * Internal method to make subtree empty.
     */
    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;
    }

        // Avl manipulations

    /**
     * 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 = 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 = k2;
    }

   //MY CODE BEGINS HERE
   void doubleWithLeftChild( AvlNode * & k3 )
    {
		AvlNode *k2 = k3->left;
		AvlNode *k1 = k3->left->right;
		
		k1->left = k2;
		k1->right = k3;
		k3 = k1;	

    }
    //MY CODE ENDS HERE

};

#endif 

[MikeyBoy]

Duplicate of http://www.cplusplus.com/forum/general/265793/

[lastchance]

@vaderboi,
I don't profess to understanding much of this code, and there is no means of testing it, but there are some elements of it that could well cause problems. That is where you have multiple levels of pointing (e.g. k3->left->right;) and you haven't checked that the intermediate level isn't null_ptr.

For example, take the first few non-trivial lines of doubleWithLeftChild():

    void doubleWithLeftChild( AvlNode * & k3 )
    {
		AvlNode *k2 = k3->left;
		AvlNode *k1 = k3->left->right;

After this you are presumably looking at something like

    k3
   /
 k2
/  \
    k1

Now, presumably k3 isn't nullptr, or you wouldn't have called the routine. However, how do you know that its left branch, k2 isn't nullptr? In which case it would be impossible to set k1.

But then you do

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

So what happened to the parts of the tree that k1->left and k1->right were originally pointing to (marked A and B in the diagram below). As far as I can see, they will now be disconnected from the tree.

    k3
   /
 k2
/  \
    k1
   /  \
  A    B 

Similar problems seem to arise in void balance()
if( height( t->left->left ) >= height( t->left->right ) )
How do you know that both those "double-pointed" nodes exist?


Could you give us some references or diagrams as to what you are trying to do. Also, could you cut your code down to a bare minimum, together with a driver routine, so that we could actually try running it?

[vaderboi]

Yes. I will pare it down and post the driver function sometime today. Sorry about the code vomit. I am always unsure whether people want all of the code from all relevant files or just the actual functions, classes, and variables being utilized.

[vaderboi]

Okay edited it. Hope that helps you to understand it better, @lastchance. Let me know if you have any questions.

[lastchance]

@vaderboi,
Please provide RUNNABLE code (and provide it BELOW this post).

You are failing to provide a whole mass of functions necessary to compile and debug this code, so it is very difficult to do anything with it.

Please:
(1) Post BELOW, not edit the original post.

(2) REMOVE all that is UNNECESSARY (especially those alternative versions of insert with moves in).

(3) Include all routines that are called - especially height(), printTree(), remove(), makeEmpty() etc. Actually, you can leave out all the removing and emptying routines completely and try to build a tree first.

(4) Put everything in one file for now - cpp.sh doesn't allow for separate compilation. You can go back to your separate original files later.

(5) Test your code to confirm that it will work WITHOUT balancing the tree first. There is no purpose to the balancing routines if the more fundamental bits don't work.

(6) If you are working from an (accessible) reference then please provide a link to that reference.

The two references I came up with in a hurry are
https://www.geeksforgeeks.org/avl-tree-set-1-insertion/
https://en.wikipedia.org/wiki/AVL_tree

[vaderboi]

Thanks for the help.