DataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType > Class Template Reference

An AVLBalancedBinarySearchTree is a binary tree that is always balanced.

#include <DS_BinarySearchTree.h>

Inheritance diagram for DataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >:

List of all members.

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

    {
        this->Clear(_FILE_AND_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 _FILE_AND_LINE_, and DataStructures::BinarySearchTree< BinarySearchTreeType >::Add().

    {
    
        typename BinarySearchTree<BinarySearchTreeType>::node * current = BinarySearchTree<BinarySearchTreeType>::Add ( input, _FILE_AND_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.

References DataStructures::BinarySearchTree< BinarySearchTreeType >::node::item, DataStructures::BinarySearchTree< BinarySearchTreeType >::node::left, and DataStructures::BinarySearchTree< BinarySearchTreeType >::node::right.

    {
        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 _FILE_AND_LINE_, and DataStructures::BinarySearchTree< BinarySearchTreeType >::Del().

    {
        typename BinarySearchTree<BinarySearchTreeType>::node * current = BinarySearchTree<BinarySearchTreeType>::Del( input, _FILE_AND_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, and DataStructures::BinarySearchTree< BinarySearchTreeType >::node::right.

    {
        // 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, and DataStructures::BinarySearchTree< BinarySearchTreeType >::node::right.

    {
        // 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 >::node::left, and DataStructures::BinarySearchTree< BinarySearchTreeType >::node::right.

    {
        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 >::node::left, and DataStructures::BinarySearchTree< BinarySearchTreeType >::node::right.

    {
        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 D, DataStructures::BinarySearchTree< BinarySearchTreeType >::node::item, DataStructures::BinarySearchTree< BinarySearchTreeType >::node::left, and DataStructures::BinarySearchTree< BinarySearchTreeType >::node::right.

    {
        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 D, DataStructures::BinarySearchTree< BinarySearchTreeType >::node::item, DataStructures::BinarySearchTree< BinarySearchTreeType >::node::left, and DataStructures::BinarySearchTree< BinarySearchTreeType >::node::right.

    {
        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