An AVLBalancedBinarySearchTree is a binary tree that is always balanced.

#include <DS_BinarySearchTree.h>

Inheritance diagram for DataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >:

Public Member Functions
void	Add (const BinarySearchTreeType &input)
	AVLBalancedBinarySearchTree ()
void	Del (const BinarySearchTreeType &input)
BinarySearchTree < BinarySearchTreeType > &	operator= (BinarySearchTree< BinarySearchTreeType > &original_copy)
virtual	~AVLBalancedBinarySearchTree ()
Private Member Functions
void	BalanceTree (typename BinarySearchTree< BinarySearchTreeType >::node *current, bool rotateOnce)
void	DoubleRotateLeft (typename BinarySearchTree< BinarySearchTreeType >::node *A)
void	DoubleRotateRight (typename BinarySearchTree< BinarySearchTreeType >::node *A)
bool	LeftHigher (typename BinarySearchTree< BinarySearchTreeType >::node *A)
bool	RightHigher (typename BinarySearchTree< BinarySearchTreeType >::node *A)
void	RotateLeft (typename BinarySearchTree< BinarySearchTreeType >::node *C)
void	RotateRight (typename BinarySearchTree< BinarySearchTreeType >::node *C)

Detailed Description

template<class BinarySearchTreeType>
class DataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >

Definition at line 136 of file DS_BinarySearchTree.h.

Constructor & Destructor Documentation

template<class BinarySearchTreeType>

DataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::AVLBalancedBinarySearchTree ( ) [inline]

Definition at line 140 of file DS_BinarySearchTree.h.

{}

template<class BinarySearchTreeType >

DataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::~AVLBalancedBinarySearchTree ( ) [virtual]

Definition at line 370 of file DS_BinarySearchTree.h.

References DataStructures::BinarySearchTree< BinarySearchTreeType >::Clear().

    {
        this->Clear(__FILE__,__LINE__);
    }

Member Function Documentation

template<class BinarySearchTreeType>

void DataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::Add ( const BinarySearchTreeType & input )

Definition at line 208 of file DS_BinarySearchTree.h.

References DataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::BalanceTree().

Referenced by NetworkIDObject::GenerateID(), and NetworkIDObject::SetNetworkID().

    {
    
        typename BinarySearchTree<BinarySearchTreeType>::node * current = BinarySearchTree<BinarySearchTreeType>::Add ( input, __FILE__,__LINE__ );
        BalanceTree( current, true );
    }

template<class BinarySearchTreeType>

void DataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::BalanceTree	(	typename BinarySearchTree< BinarySearchTreeType >::node *	current,
		bool	rotateOnce
	)			`[private]`

Definition at line 160 of file DS_BinarySearchTree.h.

Referenced by DataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::Add(), and DataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::Del().

    {
        int left_height, right_height;
        
        while ( current )
        {
            if ( current->left == 0 )
                left_height = 0;
            else
                left_height = Height( current->left );
                
            if ( current->right == 0 )
                right_height = 0;
            else
                right_height = Height( current->right );
                
            if ( right_height - left_height == 2 )
            {
                if ( RightHigher( current->right ) )
                    RotateLeft( current->right );
                else
                    DoubleRotateLeft( current );
                    
                if ( rotateOnce )
                    break;
            }
            
            else
                if ( right_height - left_height == -2 )
                {
                    if ( LeftHigher( current->left ) )
                        RotateRight( current->left );
                    else
                        DoubleRotateRight( current );
                        
                    if ( rotateOnce )
                        break;
                }
                
            if ( current == this->root )
                break;
                
            current = FindParent( *( current->item ) );
            
        }
    }

template<class BinarySearchTreeType>

void DataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::Del ( const BinarySearchTreeType & input )

Definition at line 216 of file DS_BinarySearchTree.h.

References DataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::BalanceTree().

Referenced by NetworkIDObject::SetNetworkID(), and NetworkIDObject::~NetworkIDObject().

    {
        typename BinarySearchTree<BinarySearchTreeType>::node * current = BinarySearchTree<BinarySearchTreeType>::Del( input, __FILE__,__LINE__ );
        BalanceTree( current, false );
        
    }

template<class BinarySearchTreeType>

void DataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::DoubleRotateLeft ( typename BinarySearchTree< BinarySearchTreeType >::node * A ) [private]

Definition at line 362 of file DS_BinarySearchTree.h.

References DataStructures::BinarySearchTree< BinarySearchTreeType >::node::left, DataStructures::BinarySearchTree< BinarySearchTreeType >::node::right, DataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::RotateLeft(), and DataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::RotateRight().

Referenced by DataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::BalanceTree().

    {
        // The left side of the right child must be higher for the tree to balance with a left rotation.  If it isn't, rotate it right before the normal rotation so it is.
        RotateRight( A->right->left );
        RotateLeft( A->right );
    }

template<class BinarySearchTreeType>

void DataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::DoubleRotateRight ( typename BinarySearchTree< BinarySearchTreeType >::node * A ) [private]

Definition at line 298 of file DS_BinarySearchTree.h.

References DataStructures::BinarySearchTree< BinarySearchTreeType >::node::left, DataStructures::BinarySearchTree< BinarySearchTreeType >::node::right, DataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::RotateLeft(), and DataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::RotateRight().

Referenced by DataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::BalanceTree().

    {
        // The left side of the left child must be higher for the tree to balance with a right rotation.  If it isn't, rotate it left before the normal rotation so it is.
        RotateLeft( A->left->right );
        RotateRight( A->left );
    }

template<class BinarySearchTreeType>

bool DataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::LeftHigher ( typename BinarySearchTree< BinarySearchTreeType >::node * A ) [private]

Definition at line 233 of file DS_BinarySearchTree.h.

References DataStructures::BinarySearchTree< BinarySearchTreeType >::Height(), DataStructures::BinarySearchTree< BinarySearchTreeType >::node::left, and DataStructures::BinarySearchTree< BinarySearchTreeType >::node::right.

Referenced by DataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::BalanceTree().

    {
        if ( A == 0 )
            return false;
            
        return Height( A->left ) > Height( A->right );
    }

template<class BinarySearchTreeType>

BinarySearchTree<BinarySearchTreeType>& DataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::operator= ( BinarySearchTree< BinarySearchTreeType > & original_copy ) [inline]

Definition at line 144 of file DS_BinarySearchTree.h.

        {
            return BinarySearchTree<BinarySearchTreeType>::operator= ( original_copy );
        }

template<class BinarySearchTreeType>

bool DataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::RightHigher ( typename BinarySearchTree< BinarySearchTreeType >::node * A ) [private]

Definition at line 224 of file DS_BinarySearchTree.h.

References DataStructures::BinarySearchTree< BinarySearchTreeType >::Height(), DataStructures::BinarySearchTree< BinarySearchTreeType >::node::left, and DataStructures::BinarySearchTree< BinarySearchTreeType >::node::right.

Referenced by DataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::BalanceTree().

    {
        if ( A == 0 )
            return false;
            
        return Height( A->right ) > Height( A->left );
    }

template<class BinarySearchTreeType>

void DataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::RotateLeft ( typename BinarySearchTree< BinarySearchTreeType >::node * C ) [private]

Definition at line 306 of file DS_BinarySearchTree.h.

References DataStructures::BinarySearchTree< BinarySearchTreeType >::direction, DataStructures::BinarySearchTree< BinarySearchTreeType >::FindParent(), DataStructures::BinarySearchTree< BinarySearchTreeType >::node::item, DataStructures::BinarySearchTree< BinarySearchTreeType >::LEFT, DataStructures::BinarySearchTree< BinarySearchTreeType >::node::left, DataStructures::BinarySearchTree< BinarySearchTreeType >::node::right, and DataStructures::BinarySearchTree< BinarySearchTreeType >::root.

Referenced by DataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::BalanceTree(), DataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::DoubleRotateLeft(), and DataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::DoubleRotateRight().

    {
        typename BinarySearchTree<BinarySearchTreeType>::node * A, *B, *D;
        /*
          RIGHT ROTATION
        
          A = parent(b)
          b= parent(c)
          c  = node to rotate around
        
          A
          | // Either direction
          B
          /   \
          C
          /  \
          D
        
          TO
        
          A
          | // Either Direction
          C
          /   \
          B
          /   \
          D
        
        
          <Leave all other branches branches AS-IS whether they point to another node or simply 0>
        
        */
        
        B = FindParent( *( C->item ) );
        A = FindParent( *( B->item ) );
        D = C->left;
        
        if ( A )
        {
            // Direction was set by the last find_parent call
            
            if ( this->direction == this->LEFT )
                A->left = C;
            else
                A->right = C;
        }
        
        else
            this->root = C;  // If B has no parent parent then B must have been the root node
            
        B->right = D;
        
        C->left = B;
    }

template<class BinarySearchTreeType>

void DataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::RotateRight ( typename BinarySearchTree< BinarySearchTreeType >::node * C ) [private]

Definition at line 242 of file DS_BinarySearchTree.h.

References DataStructures::BinarySearchTree< BinarySearchTreeType >::direction, DataStructures::BinarySearchTree< BinarySearchTreeType >::FindParent(), DataStructures::BinarySearchTree< BinarySearchTreeType >::node::item, DataStructures::BinarySearchTree< BinarySearchTreeType >::node::left, DataStructures::BinarySearchTree< BinarySearchTreeType >::LEFT, DataStructures::BinarySearchTree< BinarySearchTreeType >::node::right, and DataStructures::BinarySearchTree< BinarySearchTreeType >::root.

Referenced by DataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::BalanceTree(), DataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::DoubleRotateLeft(), and DataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::DoubleRotateRight().

    {
        typename BinarySearchTree<BinarySearchTreeType>::node * A, *B, *D;
        /*
          RIGHT ROTATION
        
          A = parent(b)
          b= parent(c)
          c  = node to rotate around
        
          A
          | // Either direction
          B
          /   \
          C
          /   \
          D
        
          TO
        
          A
          | // Either Direction
          C
          /   \
          B
          /   \
          D
        
        
          <Leave all other branches branches AS-IS whether they point to another node or simply 0>
        
        */
        
        B = FindParent( *( C->item ) );
        A = FindParent( *( B->item ) );
        D = C->right;
        
        if ( A )
        {
            // Direction was set by the last find_parent call
            
            if ( this->direction == this->LEFT )
                A->left = C;
            else
                A->right = C;
        }
        
        else
            this->root = C;  // If B has no parent parent then B must have been the root node
            
        B->left = D;
        
        C->right = B;
    }

The documentation for this class was generated from the following file:

DS_BinarySearchTree.h

DataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType > Class Template Reference

Public Member Functions

Private Member Functions

Detailed Description

template<class BinarySearchTreeType> class DataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >

Constructor & Destructor Documentation

Member Function Documentation

template<class BinarySearchTreeType>
class DataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >