login

1. Introduction

AvlTree<T> is a self-balancing binary search tree template class. It allows for insertion, search and removal in logarithmic time. Two main applications of AvlTree<T> are dictionaries and sets.

This implementation of AvlTree uses balance information embedded inside parent pointer. This reduces memory usage, but makes tree traversal move CPU intensive. Balance information is stored in the 2 least significant bits of parent pointer. On contemporary computer architectures structures have at least 4-byte alignment, and the last 2 bits of any pointer to structure are not used anyway.

AvlTree<T> is parametrized using data traits class. This class is required to have T::DataT& data() and T::KeyT& key() public or protected methods and DataT and KeyT public or protected typedefs.

T::KeyT has to implement operator<. This operator is called at most max_depth + 1 times on the new element being added to the tree.

2. Files

2.1. Main header file

AvlTree.hpp

3. AvlTree<T> methods

template <class T> AvlTree<T> :: AvlTree();

Default constructor. Creates empty tree.


template <class T> AvlTree<T> :: AvlTree (const AvlTree<T> &src);

Copy-constructor. Physical tree structure of a copy may differ, however iteration over a copy gives the same results as iteration over original tree. If B is a copy of A, then A == B returns true.


template <class T> AvlTree<T>& operator=(const AvlTree<T> &right);

Assignment operator. Assignment A = B: For every (key_a, value_a) from A, if there exists (key_b, value_b) in B such that key_a == key_b, do value_a = value_b. Remove from A all pairs (key, value) from A not belonging to B. Add to A all pairs (key, value) from B not belonging to A. After assingnment, A == B returns true.


template <class T> bool AvlTree<T>::operator==(const AvlTree& right) const;

Two trees A and B are considered eqal when every pair (key, value) from tree A can be found in tree B and every pair (key, value) from tree B can be found in tree A. Structure of the tree is not taken into consideration. It is worth to mention that iteration over equal trees gives the same results regardless structure.


template <class T> bool AvlTree<T>::empty() const;

True when tree is empty. False otherwise.


template <class T> typename T::DataT& AvlTree<T>::operator[] (const typename T::KeyT &key);

This operator allows for more clear syntax when using AvlTree as dictionary. It lets us write dict [key] = value;. If no pair with matching key exists, it is created using T::KeyT(key) and T::DataT() constructors.


template <class T> AvlTree<T>::Iterator
  AvlTree<T>::find(const typename T::KeyT key);

Returns iterator to a pair with key matching the given key, or invalid iterator if the key was not found.


template <class T> AvlTree<T>::Iterator AvlTree<T>::begin();

Returns iterator to the 'beginning' of the tree, which is pair with the smallest key value.


template <class T> AvlTree<T>::ConstIterator AvlTree<T>::begin() const;

Same as above, but returns ConstIterator.


template <class T> void AvlTree<T>::remove(const Iterator& it);

Removes element given by iterator to it. Iterator has to be valid and point to element in this (and not other) tree.


template <class T> void
  AvlTree<T>::dump_rec(std::ostream &out, AvlNode<T> *node = 0, unsigned depth = 0);

Debug mode only. Stores dump of the tree in .dot format in the given stream. This method is recursive on purpose, to work even when parent pointers are broken. Parameters node and depth should be left with default values.


template <class T> int AvlTree<T>::check(AvlNode<T> *node = 0, int depth = 0);

Debug mode only. Checks if the tree is balanced and balance values are set correctly. It returns maximum depth of the tree or throws an exception if tree is not correct.


template <class T> void AvlTree<T>::add(const T& item);

Adds new (key, value) pair to the tree. When using AvlTree as a set, one can write set.add( value);. If given (key, value) pair already exists, the result is unspecified (so don't do that).


template <class T> void
  AvlTree<T>::add(const typename T::KeyT& key, const typename T::DataT& data);

Overloaded, two-argument version of the above method. It simplifies adding elements to dictionaries and doesn't have the overhead of operator[] (which uses potentially expensive default copy constructor). If a pair with matching key already exists, the result is unspecified.

4. Iterators

There are two iterators: Iterator and ConstIterator. ConstIterator doesn't allow for modifying (key, value) pairs it points. Iterators traverse the tree in (left child) -> (node) -> (right child) recursive order. Or in other words, they traverse all the (key, value) pairs in increasing keys order.

Currently both iterators implement prefix and postfix @(i-code)(cpp)(operator++) and @(i-code)(cpp)(operator*).


template <class T> AvlTree<T>::Iterator();

Default constructor. Creates invalid iterator. Sometimes useful.


template <class T> T& AvlTree<T>::Iterator::operator*() const;

Dereferencing operator. Obvious.


template <class T> bool AvlTree<T>::Iterator::valid() const;

Returns true if iterator is valid, and false otherwise. Concept of iterator validity is analogous to the concept of null pointers.


template <class T> AvlTree<T>::Iterator&
  AvlTree<T>::Iterator::operator++();

Prefix incrementation operator.


template <class T> AvlTree<T>::Iterator& AvlTree<T>::Iterator::operator++(int dummy);

Postfix incrementation operator. Slightly more efficient.

ConstIterator is very similar, and its detailed description will be ommited here.

5. KeyKey and DataKey classes

KeyKey<T> template class is provided to simplify creating sets. Example:

AvlTree< KeyKey<std::string> > myAnimals; // A set of my animals.
myAnimals.add("starfish");
myAnimals.add("gecko");

KeyData<T> template class is provided to simplify creating dictionaries. Example:

AvlTree< KeyData<std::string, std::string> > myAnimalNames;

// Single argument. Complicated.
myAnimalNames.add( KeyData<std::string, std::string>("starfish", "Katie") );

myAnimalNames.add("starfish", "Katie"); // Clean and simple.

myAnimalNames["gecko"] = "Bill";        // Now my gecko has a new name.

Custom data traits may also be created. For example:

class Number {
  private:
    int key_;

  protected:
    // These two typedefs are required, and have to be public or protected.
    typedef int KeyT;
    typedef int DataT;
   
    // One also has to implement those two methods.
    const KeyT& key() const {
      return key_;
    }
   
    // This method doesn't generally need to return constant reference.
    // Here it does.
    const DataT& data() const {
      return key_;
    }
   
  public:
    Number(int key) : key_(key) { }
    Number(const std::string& number) : key_(string_to_number(number)) { }

Now we may write:

AvlTree< Number > myNumbers;

myNumbers.add(11); // We can do this thanks to the first constructor.

// We can do this thanks to the second constructor.
myNumbers.add("twenty four");
Copyright © 2009, 2010, 2014 Janusz Kowalski
Powered by KrotCMS 2.0