AVL Trees vs. Red-Black Trees? Hi, I worked through the chapter in Introduction to Algorithms by Cormen et al on red-black trees. One of the problems at the end discusses AVL trees.
Warren Henning
I'm not sure that it'll be much info for you but trees in Java Collections are implemented using red-black trees. Which probably doesn't mean a lot.
Evgeny Goldin
So are std::map and set::set in STL.
Ivan-Assen Ivanov
Creating a tree which balances nodes will tend to improve the search time for any random term within the tree.
Simon Lucy
RB-Trees are, as well as AVL trees, self-balancing. Both of them provide O(log n) lookup and insertion performance.
Alex
It's been a long time since any data structure lectures, but my understanding is that in an AVL tree the difference between the shortest and longest path to from the root to any leaf is at most one. In a red-black tree the difference can be a factor of 2.
Rob Walker
Actually, AVL trees only guarantee that, for each node in the tree, the heights of its subtrees differ by at most one. Since the height is defined by the longest path to a leaf, it makes no guarantees about the ratio between the shortest path to a leaf and the longest. In fact, it is possible to generate a tree with the AVL property whose whose shortest/longest path ratio is arbitrarily bad.
Devil's Advocate
"Since the height is defined by the longest path to a leaf, it makes no guarantees about the ratio between the shortest path to a leaf and the longest. In fact, it is possible to generate a tree with the AVL property whose whose shortest/longest path ratio is arbitrarily bad."
Devil's Advocate
If you require a balanced tree type data structure I recommend taking a look at Splay trees. Splay trees are cool because they are relatively easy to implement, and they don't require storing any additional information at each node.
Peter McKenzie
In fact, we need not compare btw. the longest and the shortest path of a tree to measure its performance. What we need, instead, is the tree's longest path, or height, relative to the number of its elements, say N.
Junghyun Chae
I forgot to add: by definition, every AVL is therefore subsets of Red-Black. One should be able to color any AVL tree, without restructuring or rotation, to transform it into a Red-Black tree.
Junghyun Chae
"Searching for an item, or inserting an item, has the same complexity, O(log N)."
Junghyun Chae
What is the difference between AVL and RB-Trees? It seems as though AVLs use a balance factor and RB-Tree uses color to tell if the child is out of ballance? I don know.
Shack Man
Search time is logarithmic for both. The only possible advantage is that with a red-black tree, there will be a slightly lower amount of rotations needed to maintain balance.
Greg Holl
Just making it clear:
Stephen Howe
The reason it matters that red-black trees require O(1) rebalancing operations (vs. O(log n) for AVL) comes up in the application to persistent data structures (Sleator, Tarjan, et al.) A persistent data structure makes it possible to roll back any algorithm to a previous step. To do so, it must keep a trail of updates. Any persistent data structure based on an AVL tree is going to have to store O(log n) times as many updates as one based on a red-black tree.
Paul Callahan
Fog Creek Home |