In computer science, an AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.
AVL trees are often compared with red-black trees because they support the same set of operations and because red-black trees also take O(log n) time for the basic operations. Because AVL trees are more rigidly balanced, they are faster than red-black trees for lookup-intensive applications. Similar to red-black trees, AVL trees are height-balanced, but in general not weight-balanced nor μ-balanced; that is, sibling nodes can have hugely differing numbers of descendants.
Task: Implement an AVL tree in the language of choice and provide at least basic operations.
#include <algorithm> #include <iostream> /* AVL node */ template <class T> class AVLnode { public: T key; int balance; AVLnode *left, *right, *parent; AVLnode(T k, AVLnode *p) : key(k), balance(0), parent(p), left(NULL), right(NULL) {} ~AVLnode() { delete left; delete right; } }; /* AVL tree */ template <class T> class AVLtree { public: AVLtree(void); ~AVLtree(void); bool insert(T key); void deleteKey(const T key); void printBalance(); private: AVLnode<T> *root; AVLnode<T>* rotateLeft ( AVLnode<T> *a ); AVLnode<T>* rotateRight ( AVLnode<T> *a ); AVLnode<T>* rotateLeftThenRight ( AVLnode<T> *n ); AVLnode<T>* rotateRightThenLeft ( AVLnode<T> *n ); void rebalance ( AVLnode<T> *n ); int height ( AVLnode<T> *n ); void setBalance ( AVLnode<T> *n ); void printBalance ( AVLnode<T> *n ); void clearNode ( AVLnode<T> *n ); }; /* AVL class definition */ template <class T> void AVLtree<T>::rebalance(AVLnode<T> *n) { setBalance(n); if (n->balance == -2) { if (height(n->left->left) >= height(n->left->right)) n = rotateRight(n); else n = rotateLeftThenRight(n); } else if (n->balance == 2) { if (height(n->right->right) >= height(n->right->left)) n = rotateLeft(n); else n = rotateRightThenLeft(n); } if (n->parent != NULL) { rebalance(n->parent); } else { root = n; } } template <class T> AVLnode<T>* AVLtree<T>::rotateLeft(AVLnode<T> *a) { AVLnode<T> *b = a->right; b->parent = a->parent; a->right = b->left; if (a->right != NULL) a->right->parent = a; b->left = a; a->parent = b; if (b->parent != NULL) { if (b->parent->right == a) { b->parent->right = b; } else { b->parent->left = b; } } setBalance(a); setBalance(b); return b; } template <class T> AVLnode<T>* AVLtree<T>::rotateRight(AVLnode<T> *a) { AVLnode<T> *b = a->left; b->parent = a->parent; a->left = b->right; if (a->left != NULL) a->left->parent = a; b->right = a; a->parent = b; if (b->parent != NULL) { if (b->parent->right == a) { b->parent->right = b; } else { b->parent->left = b; } } setBalance(a); setBalance(b); return b; } template <class T> AVLnode<T>* AVLtree<T>::rotateLeftThenRight(AVLnode<T> *n) { n->left = rotateLeft(n->left); return rotateRight(n); } template <class T> AVLnode<T>* AVLtree<T>::rotateRightThenLeft(AVLnode<T> *n) { n->right = rotateRight(n->right); return rotateLeft(n); } template <class T> int AVLtree<T>::height(AVLnode<T> *n) { if (n == NULL) return -1; return 1 + std::max(height(n->left), height(n->right)); } template <class T> void AVLtree<T>::setBalance(AVLnode<T> *n) { n->balance = height(n->right) - height(n->left); } template <class T> void AVLtree<T>::printBalance(AVLnode<T> *n) { if (n != NULL) { printBalance(n->left); std::cout << n->balance << " "; printBalance(n->right); } } template <class T> AVLtree<T>::AVLtree(void) : root(NULL) {} template <class T> AVLtree<T>::~AVLtree(void) { delete root; } template <class T> bool AVLtree<T>::insert(T key) { if (root == NULL) { root = new AVLnode<T>(key, NULL); } else { AVLnode<T> *n = root, *parent; while (true) { if (n->key == key) return false; parent = n; bool goLeft = n->key > key; n = goLeft ? n->left : n->right; if (n == NULL) { if (goLeft) { parent->left = new AVLnode<T>(key, parent); } else { parent->right = new AVLnode<T>(key, parent); } rebalance(parent); break; } } } return true; } template <class T> void AVLtree<T>::deleteKey(const T delKey) { if (root == NULL) return; AVLnode<T> *n = root, *parent = root, *delNode = NULL, *child = root; while (child != NULL) { parent = n; n = child; child = delKey >= n->key ? n->right : n->left; if (delKey == n->key) delNode = n; } if (delNode != NULL) { delNode->key = n->key; child = n->left != NULL ? n->left : n->right; if (root->key == delKey) { root = child; } else { if (parent->left == n) { parent->left = child; } else { parent->right = child; } rebalance(parent); } } } template <class T> void AVLtree<T>::printBalance() { printBalance(root); std::cout << std::endl; } int main(void) { AVLtree<int> t; std::cout << "Inserting integer values 1 to 10" << std::endl; for (int i = 1; i <= 10; ++i) t.insert(i); std::cout << "Printing balance: "; t.printBalance(); }
- Output:
Inserting integer values 1 to 10 Printing balance: 0 0 0 1 0 0 0 0 1 0
Content is available under GNU Free Documentation License 1.2.
