This patch implements the WAVL tree data structure introduced in this paper.
It also includes a set of 27 tests.
Time complexity in Big-O notation:
| Function | Average | Worst-Case |
| Search | O(log(n)) | O(log(n)) |
| Insertion | O(log(n)) | O(log(n)) |
| Deletion | O(log(n)) | O(log(n)) |
| Access Min | O(1)* | O(1)* |
| Access Max | O(1)* | O(1)* |
| Access Predecessor | O(1)* | O(1)* |
| Access Successor | O(1)* | O(1)* |
*For every insertion and deletion, we can update the min, max, predecessor and successor of the given node. This allows us to look up these nodes (access of O(1)) but adds +O(1) to every insertion and deletion (it's basically an insertion/deletion into/from a double linked list).
Explanation as to why this is needed:
The red and black tree implementation is fine. But it's missing some things that I needed: Deletion of a node, accessing successor and predecessor in O(1) and having tests. Because doing a new implementation would take me as long as to add to the current implementation, I decided to do it this way. Additionally WAVL trees combine some of the better properties of both red and black trees and AVL trees. Namely a constant number of tree rotations for deleting and inserting a node and the fact that they are more balanced on average than red and black trees.