Red-black or AVL tree
John Potter
AVL tree. It stated that AVL trees were of theoretical interest only
and that all real applications used RB trees.
Knowing that the theory says that an AVL tree should be better balanced
than an RB tree, I decided to make some tests. I started with egcs-1.1
stl_tree.h. Since both are binary search trees, the only change needed
was in the two rebalance algorithms. Minor changes elsewhere to set
the correct starting balance for new nodes. Yes, color changed from
bool to int, but I didn't bother to change the name. :)
One test was of course the classic sieve using set<int>. This tests
insert in order and erase at random with many failures. For N = 100K,
rb 111
avl 97
The second test inserted the range of rand (1-32767) and performed
1M finds of rand. This tests find with a few failures at 0.
rb 276
avl 270
The third test involved counting ajacent letter strings in a text file
using a map<string, int>. Operator[] and erase were used. The length
of the string was set at 1-3. A second parameter forced deletion when
the count reached a limit. The limit was set at 0 (infinity) 9 and 2.
For example "hello world" contains for length:
1 h e l l o w o r l d
2 he el ll lo wo or rl ld
3 hel ell llo wor orl rld
As the length of the string increases, the size of the tree increases
while the number of strings in the file decreases. With limit 0,
there are no deletions. With limit 9, there are about 10% deletions
and the size of the tree averages 90%. With limit 2 every string
causes either an insertion or a deletion and the size of the tree is
about 50%. (This one is a great special case bugger for collections :)
0 9 2
rb 1 87 100 144
2 90 98 136
3 78 85 116
avl 1 83 97 143
2 86 94 134
3 78 85 115
In all tests, the AVL tree performed insignificantly better than the
RB tree.
Neither the RB tree which is usually forward balanced nor the AVL
tree which is usually recursively balanced are used in their textbook
versions in the STL. With parent pointers required for iterators,
both trees perform better than usual. A little space time tradeoff.
These tests hardly exhaust the use of the BST in the associative
containers. Is there some other test which shows the superiority
of the RB tree? Is there any excuse for the statement that AVL
trees are only of theoretical interest while RB trees are practical?
John
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
[ about comp.lang.c++.moderated. First time posters: do this! ]
JKB
slightly better balanced. They're both balanced binary trees, so the
height of a tree with N nodes is O(lg N) regardless. But the constant
factors are different, a little:
AVL h=1.44*lg(N-2)
R/B h = 2*lg(N+1)
The extra space in RB trees roughly corresponds to sequences of black
nodes, where the 'every red node has a black parent' rule prevents
sequences of red nodes.
Both data structures implement the methods 'Min', 'Member', 'Insert', and
'Delete' in O(lg N) time, so I don't see much theoretical difference one
way or another. I did see a note that AVL trees require O(lg N) rotations
to perform insert/delete, while R/B trees require at most three rotations
no matter the size of the tree.
And the insert/delete code is fairly horrible either way; the rebalancing
systems are just full of special cases.
-- jkb
John Potter wrote:
> theory says that an AVL tree should be better balanced than an RB
> tree....
> Is there any excuse for the statement that AVL trees are only of
> theoretical interest while RB trees are practical?
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
John Potter
: A quick textbook check (Cormen&Leiserson)
The HP->SGI->GNU documentation
| Red-black tree class, designed for use in implementing STL
| associative containers (set, multiset, map, and multimap). The
| insertion and deletion algorithms are based on those in Cormen,
| Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990),
: confirms that AVL trees are
: slightly better balanced. They're both balanced binary trees, so the
: height of a tree with N nodes is O(lg N) regardless. But the constant
: factors are different, a little:
: AVL h=1.44*lg(N-2)
: R/B h = 2*lg(N+1)
Yes. The average heights are not as different.
: I did see a note that AVL trees require O(lg N) rotations
: to perform insert/delete, while R/B trees require at most three
: rotations no matter the size of the tree.
At most one fix of one or two rotations for insert in an AVL tree.
Delete can do lgN fixes. In both trees, ascending to the root may
be required to complete balancing. I still do not see any great
difference.
: And the insert/delete code is fairly horrible either way; the rebalancing
: systems are just full of special cases.
Not really. Delete has four cases to force the deleted node to be a
leaf, while insert is always a leaf. Rebalancing an AVL has the
left and right cases with either fixed, continue, or rotate. The
rotate has two cases. The RB has more cases due to the four types
of pseudonode. For AVL, the rebanance code was 24 lines for insert
and 36 lines for erase. Basically 12 lines of code reused five times.
Rotate was 15 lines each, 13 pointer games plus 2 to set the balances.
I don't find any of it "horrible".
Unless someone comes up with something, I am concluding that RB was
simply a choice between two fairly equal structures.
John