What are AVL trees? What are Red-Black trees? What are the differences between them?

What are AVL trees? What are Red-Black trees? What are the differences between them?

AVL Tree
An AVL Tree is a binary search tree such that for
every internal node v of T, the heights of the children
of v can differ by at most 1.

Red-black trees
This data structure requires an extra onebit color field in each node.
Red-black properties:
1. Every node is either red or black.
2. The root and leaves (NIL's) are black.
3. If a node is red, then its parent is black.
4. All simple paths from any node x to a
descendant leaf have the same number
of black nodes = black-height(x).

For small data:

insert: RB tree & avl tree has constant number of max rotation but RB tree will be faster because on average RB tree use less rotation.

lookup: AVL tree is faster, because AVL tree has less depth.

delete: RB tree has constant number of max rotation but RB tree can have O(log N) times of rotation as worst. and on average RB tree also has less number of rotation thus RB tree is faster.

for large data:

insert: AVL tree is faster. because you need to lookup for a particular node before insertion. as you have more data the time difference on looking up the particular node grows proportional to O(log N). but AVL tree & RB tree still only need constant number of rotation at the worst case. Thus the bottle neck will become the time you lookup for that particular node.

lookup: AVL tree is faster. (same as in small data case)

delete: AVL tree is faster on average, but in worst case RB tree is faster. because you also need to lookup for a very deep node to swap before removal (similar to the reason of insertion). on average both trees has constant number of rotation. but RB tree has a constant upper bound for rotation.

 

 

AVL as well as RedBlack Trees are height-balanced Tree Data Structures. They are pretty similar, and the real difference consists in the number of rotation operation done upon any add/remove operation - higher in the case of AVL, to preserve an overall more homogeneous balancing.

Both implementations scale as a O(lg N), where N is the number of leaves, but in practice a AVL Tree is faster on lookup intensive tasks: taking advantage of the better balancing, the Tree traversals are shorter on average. On the other hand, insertion and deletion wise, an AVL Tree is slower: a higher number of rotations are needed to rebalance properly the Data Structure upon modification.

For general purpose implementations (i.e. a-priori it is not clear if lookups are the predominant of operations), RedBlack Trees are preferred: they are easier to implement, and faster on the common cases - wherever the Data Structure is modified as frequently as searched. An example, TreeMap and TreeSet in Java make use of a backing RedBlack Tree.