Red Black tree vs AVL
Angry man
I have a question regarding red-black trees.
Most textbooks I read seem to say that a 'data' node in a red black tree can
only reside on a leaf. Is it right to say all nodes except the leaves (IE,
bottom row!) are 'dummy' nodes in all RB trees? Hence the height of a
perfectly balanced RB tree will be +1 over a perfectly balanced AVL tree
given the same number of data nodes?
I am working in a very memory constrained environment, and wasting 12 bytes
on dummy/reference nodes is generally not acceptable. Now, an AVL tree
seems to use each node for data, so I'm now thinking this is what I require.
What advantages do RB trees have over AVL except
Easier to implement
Faster insertions
Can anyone please advise? I really don't fancy doing an AVL tree right now,
and would much rather stick to RB. Seems though every implementation I see
will only allow an insertion on a leaf, and leaves a lot of memory wasted.
UNLESS I have the wrong end of the stick....
Thanks
bob
Ben Pfaff
> Most textbooks I read seem to say that a 'data' node in a red black tree can
> only reside on a leaf.
That's wrong. Internal nodes are the only nodes in red-black
trees that store data. Leaves are just null pointers.
> I am working in a very memory constrained environment, and wasting 12 bytes
> on dummy/reference nodes is generally not acceptable. Now, an AVL tree
> seems to use each node for data, so I'm now thinking this is what I require.
AVL trees and red-black trees store their data in the same way.
Both store data in internal nodes.
> What advantages do RB trees have over AVL except
> Easier to implement
> Faster insertions
Neither of those is an advantage of RB trees over AVL trees. AVL
trees are actually easier to implement than RB trees because
there are fewer cases. And AVL trees require O(1) rotations on
an insertion, whereas red-black trees require O(lg n).
In practice, the speed of AVL trees versus red-black trees will
depend on the data that you're inserting. If your data is well
distributed, so that an unbalanced binary tree would generally be
acceptable (i.e. roughly in random order), but you want to handle
bad cases anyway, then red-black trees will be faster because
they do less unnecessary rebalancing of already acceptable data.
On the other hand, if a pathological insertion order
(e.g. increasing order of key) is common, then AVL trees will be
faster, because the stricter balancing rule will reduce the
tree's height.
This is what actually happens in practice. I have written a
(currently unpublished) paper on the topic.
Splay trees might be even faster than either RB or AVL trees,
depending on your data access distribution. And if you can use a
hash instead of a tree, then that'll be fastest of all.
> Can anyone please advise? I really don't fancy doing an AVL tree right now,
> and would much rather stick to RB. Seems though every implementation I see
> will only allow an insertion on a leaf, and leaves a lot of memory wasted.
I really don't know what you're thinking of, unless you're
thinking of the way that insertions always add a new node to the
periphery of the tree, as opposed to adding a node somewhere in
the middle of the tree.
You can look at my sample RB and AVL implementations on my
website at adtinfo.org.
--
"Then, I came to my senses, and slunk away, hoping no one overheard my
thinking."
--Steve McAndrewSmith in the Monastery
Gordon Airport
> Hi all,
>
> I have a question regarding red-black trees.
>
> Most textbooks I read seem to say that a 'data' node in a red black tree can
> only reside on a leaf. Is it right to say all nodes except the leaves (IE,
> bottom row!) are 'dummy' nodes in all RB trees? Hence the height of a
> perfectly balanced RB tree will be +1 over a perfectly balanced AVL tree
> given the same number of data nodes?
>
Perhaps your're thinking of a B-Tree rather than an RB-Tree. B-Trees are
used to deal with high latency access situations like disks, iirc.