AvlTree< KeyType > Class Template Reference

#include <avl.hxx>

Inheritance diagram for AvlTree< KeyType >:

List of all members.

Public Types
typedef int(*	AvlIterFunc )(NodeType *)
Public Member Functions
	AvlTree ()
	~AvlTree ()
void	insert (const KeyType &key)
NodeType *	choose ()
NodeType *	least ()
NodeType *	greatest ()
void	remove (NodeType &node)
NodeType *	lookup (const KeyNodeType &key)
NodeType *	lookup (KeyType key)
NodeType *	lookupGLE (const NodeType &key)
NodeType *	lookupGLE (KeyType key)
void	iterate (AvlIterFunc avlFunc)

---

Detailed Description

template<typename KeyType>
class AvlTree< KeyType >

Definition at line 218 of file avl.hxx.

---

Member Typedef Documentation

template<typename KeyType> typedef int(* AvlTree< KeyType >::AvlIterFunc)(NodeType *)

Reimplemented from BaseAvlTree. Definition at line 306 of file avl.hxx.

---

Constructor & Destructor Documentation

template<typename KeyType> AvlTree< KeyType >::AvlTree (   )  [inline]

Definition at line 222 of file avl.hxx.

template<typename KeyType> AvlTree< KeyType >::~AvlTree (   )  [inline]

Definition at line 226 of file avl.hxx.

---

Member Function Documentation

template<typename KeyType> NodeType* AvlTree< KeyType >::choose (   )  [inline]

Selects an arbitrary node from within the avl tree (if any) and returns it, or NULL if no nodes remain. The returned node remains in the tree. Reimplemented from BaseAvlTree. Definition at line 241 of file avl.hxx.

template<typename KeyType> NodeType* AvlTree< KeyType >::greatest (   )  [inline]

Returns the least node in the avl tree (if any) or NULL. The returned node remains in the tree. Reimplemented from BaseAvlTree. Definition at line 255 of file avl.hxx.

template<typename KeyType> void AvlTree< KeyType >::insert (  const KeyType &  key  )  [inline]

Insert a new node into an existing AVL tree. The lchild/rchild fields of the inserted node will be set to NULL prior to insertion. Definition at line 233 of file avl.hxx.

template<typename KeyType> void AvlTree< KeyType >::iterate (  AvlIterFunc  avlFunc  )  [inline]

Reimplemented from BaseAvlTree. Definition at line 309 of file avl.hxx. References BaseAvlTree::iterate().

template<typename KeyType> NodeType* AvlTree< KeyType >::least (   )  [inline]

Returns the least node in the avl tree (if any) or NULL. The returned node remains in the tree. Reimplemented from BaseAvlTree. Definition at line 248 of file avl.hxx.

template<typename KeyType> NodeType* AvlTree< KeyType >::lookup (  KeyType  key  )  [inline]

Definition at line 285 of file avl.hxx. References AvlTree< KeyType >::lookup().

template<typename KeyType> NodeType* AvlTree< KeyType >::lookup (  const KeyNodeType &  key  )  [inline]

Test whether and existing value exists within an AVL tree. It may seem wasteful that the client must supply an BaseAvlNode rather than some more compact AvlKey structure. In our experience with tree structures it is usually the case that the search key structure is stack allocated. Since the only fields that need to be initialized are the ones consulted by the comparator routine, allocating a full BaseAvlNode actually isn't any more expensive -- it just bumps the stack by a few more words. The advantage of reusing the BaseAvlNode structure for this purpose is that it allows the tree itself to remain completely agnostic about key types and value types. Definition at line 281 of file avl.hxx. Referenced by AvlTree< KeyType >::lookup().

template<typename KeyType> NodeType* AvlTree< KeyType >::lookupGLE (  KeyType  key  )  [inline]

Definition at line 297 of file avl.hxx. References AvlTree< KeyType >::lookupGLE().

template<typename KeyType> NodeType* AvlTree< KeyType >::lookupGLE (  const NodeType &  key  )  [inline]

Similar to avl_lookup(), but returns the BaseAvlNode whose key is the greatest (according to provided comparator) key less than or equal to the search key. Definition at line 293 of file avl.hxx. Referenced by AvlTree< KeyType >::lookupGLE().

template<typename KeyType> void AvlTree< KeyType >::remove (  NodeType &  node  )  [inline]

Remove a node from an AVL tree. On return, the node structure has been freed. Definition at line 263 of file avl.hxx.

---

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

• avl.hxx

---