Main Page | Modules | Namespace List | Class Hierarchy | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

BasicDataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType > Class Template Reference

#include <BinarySearchTree.h>

Inheritance diagram for BasicDataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >:

BasicDataStructures::BinarySearchTree< BinarySearchTreeType > List of all members.

Public Member Functions

 AVLBalancedBinarySearchTree ()
virtual ~AVLBalancedBinarySearchTree ()
void add (const BinarySearchTreeType &input)
void del (const BinarySearchTreeType &input)
BinarySearchTree< BinarySearchTreeType > & operator= (BinarySearchTree< BinarySearchTreeType > &original_copy)

Private Member Functions

void balance_tree (typename BinarySearchTree< BinarySearchTreeType >::node *current, bool rotateOnce)
void rotate_right (typename BinarySearchTree< BinarySearchTreeType >::node *C)
void rotate_left (typename BinarySearchTree< BinarySearchTreeType >::node *C)
void double_rotate_right (typename BinarySearchTree< BinarySearchTreeType >::node *A)
void double_rotate_left (typename BinarySearchTree< BinarySearchTreeType >::node *A)
bool right_higher (typename BinarySearchTree< BinarySearchTreeType >::node *A)
bool left_higher (typename BinarySearchTree< BinarySearchTreeType >::node *A)

Detailed Description

template<class BinarySearchTreeType>
class BasicDataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >

This class is similar to the BinarySearchTree one in its interface. However it provided Balanced Tree. The tree storing values has a minimum height at all time. Searching a value in such a tree is more efficient than in standard BinarySearchTree. .

Note:
for more information consult the base class documentation.


Constructor & Destructor Documentation

template<class BinarySearchTreeType>
BasicDataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::AVLBalancedBinarySearchTree  )  [inline]
 

Default constructor

template<class BinarySearchTreeType>
BasicDataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::~AVLBalancedBinarySearchTree  )  [virtual]
 

Destructor


Member Function Documentation

template<class BinarySearchTreeType>
void BasicDataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::add const BinarySearchTreeType &  input  ) 
 

Add an element to the tree and balanced the tree.

Parameters:
input the new element

Reimplemented from BasicDataStructures::BinarySearchTree< BinarySearchTreeType >.

template<class BinarySearchTreeType>
void BasicDataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::balance_tree typename BinarySearchTree< BinarySearchTreeType >::node *  current,
bool  rotateOnce
[private]
 

template<class BinarySearchTreeType>
void BasicDataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::del const BinarySearchTreeType &  input  ) 
 

Remove an element of the tree and balanced the tree.

Parameters:
input the element to remove

Reimplemented from BasicDataStructures::BinarySearchTree< BinarySearchTreeType >.

template<class BinarySearchTreeType>
void BasicDataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::double_rotate_left typename BinarySearchTree< BinarySearchTreeType >::node *  A  )  [private]
 

template<class BinarySearchTreeType>
void BasicDataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::double_rotate_right typename BinarySearchTree< BinarySearchTreeType >::node *  A  )  [private]
 

template<class BinarySearchTreeType>
bool BasicDataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::left_higher typename BinarySearchTree< BinarySearchTreeType >::node *  A  )  [private]
 

template<class BinarySearchTreeType>
BinarySearchTree<BinarySearchTreeType>& BasicDataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::operator= BinarySearchTree< BinarySearchTreeType > &  original_copy  )  [inline]
 

Assignement operator

Parameters:
original_copy The tree to copy
Returns:
a reference to the current object.

template<class BinarySearchTreeType>
bool BasicDataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::right_higher typename BinarySearchTree< BinarySearchTreeType >::node *  A  )  [private]
 

template<class BinarySearchTreeType>
void BasicDataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::rotate_left typename BinarySearchTree< BinarySearchTreeType >::node *  C  )  [private]
 

template<class BinarySearchTreeType>
void BasicDataStructures::AVLBalancedBinarySearchTree< BinarySearchTreeType >::rotate_right typename BinarySearchTree< BinarySearchTreeType >::node *  C  )  [private]
 


The documentation for this class was generated from the following file:
Generated on Mon May 30 17:45:43 2005 for raknet by  doxygen 1.4.2