AVL-Tree

KO | EN

gitlite — search

#javascript #hacktoberfest #ai #typescript #llm #go #rust #linux #macos #nodejs #kubernetes #vue #awesome-list #open-source

(★ 35)

AVL Tree Implementation in C++

AVL-Tree Latest Version Download

Download Latest Version (.zip)

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# AVL Tree Implementation in C++

AVL Tree is a **self-balancing** binary search tree which guarantees O(logN) time complexity for insertion, deletion, and look-up operations.

This version is implemented in C++ language, and allows multiple elements with same values. It means the tree can be used as **multiset**.

#### How to use it:

The tree can store any type of data which has **greater than** (>) operator. Build-in types such as `int`, `long long`, and `std::string` are well-tested, however user-defined structures, even has > operator, may cause some exceptions.

| Function | Definition | Time Complexity |
| --- | --- | --- |
| `AVLTree<class T> tree;` | declaration of tree object | constant |
| `insert(T value)` | insert an element to tree | O(logN) |
| `erase(T value)` | removes one match-up from tree | O(logN) |
| `find(T value)` | return index of element if exists, otherwise -1 | O(logN) |
| `operator[](int idx)` | access element at position idx in tree | O(logN) |
| `lower_bound(T value)` | return the position of the first element which does not compare less than value | O(logN) |
| `upper_bound(T value)` | return the position of the first element which does not compare greater than value | O(logN) |
| `size()` | return tree size | constant |
| `empty()` | test if tree is empty | constant |
| `clear()` | clear tree | O(N) |
| `display()` | display tree (*good for debugging*) | O(N) |

#### How to compile and run the program:

For competitive programmers, **onefile.cpp** contains all functions in one.

g++ kod.cpp AVLTree.cpp AVLTreeNode.cpp -o kod -std=c++11
    ./kod

or

g++ onefile.cpp -o kod -std=c++11
    ./kod

#### Performance Test: AVL Tree vs std::multiset

As we know that std::multiset in standard template library (STL) is based on Red Black Trees (**RB Trees**) and both RB Trees and AVL Trees support insertion, deletion and look-up in guaranteed O(logN) time. However, AVL Trees are more rigidly balanced, it means that AVL Trees need more rotations in insertion and deletion, but provide faster look-up. So you are strongly recommended to use AVL Trees for **look-up** intensive tasks, otherwise RB Trees (also std::multiset) are more convenient.

| Task | Amount | Container | Time Elapsed (ms) |
| --- | :--- | :---: | :---: |
| `insertion` | 100.000 | AVL Tree std::multiset | 150 **19** |
| `insertion` | 1.000.000 | AVL Tree std::multiset | 1596 **230** |
| `deletion` | 100.000 | AVL Tree std::multiset | 122 **16** |
| `deletion` | 1.000.000 | AVL Tree std::multiset | 1214 **145** |
| `look-up` | 100.000 | AVL Tree std::multiset | 6 **4** |
| `look-up` | 1.000.000 | AVL Tree std::multiset | 70 **60** |
| `look-up` | 10.000.000 | AVL Tree std::multiset | **398** 1554 |
| `look-up` | 100.000.000 | AVL Tree std::multiset | **3536** 19238 |

> In look-up and deletion operations, containers have 100.000 elements.

AVL-Tree

AVL-Tree Latest Version Download

Today's picks

Was this content helpful?

Recent Feedback

AVL-Tree

AVL-Tree Latest Version Download

Today's picks

Was this content helpful?

Recent Feedback

Download README