NetNews Usenet Archive 1992 #19/NN_1992_19.iso/spool/comp/programm/2494

Internet Message Format | 1992-08-27 | 1.8 KB

Path: sparky!uunet!mcsun!sunic!dkuug!daimi!protonen
From: [e-mail] (Lars J|dal)
Newsgroups: comp.programming
Subject: Re: Why Are Red-Black Trees Obscure?
Message-ID: <[e-mail]>
Date: 27 Aug 92 11:55:51 GMT
References: <[e-mail]>
Sender: [e-mail]
Organization: DAIMI: Computer Science Department, Aarhus University, Denmark
Lines: 27

[e-mail] (P. Hawthorne) writes:

>Sedgewick, for the chapter on balanced trees in his book "Algorithms," uses
>the red-black tree. As a data structure, the red-black tree seems simple
>and well balanced. He convincingly suggests that they are better than AVL
>trees and yet, I've never seen them mentioned by anyone else. Why not?

>Theus ([e-mail])

Probably because the AVL trees are easier to implement. I'm no expert in
the field, but I have seen the source code for at program using AVL trees.
The balancing was farely simple, something like "if I have put a new
element in the biggest part of the current (sub)tree then I should
rearrange my two subtrees a bit."
Balancing the red-black trees, on the other hand, involves recognizing
the near pattern of the tree, including going up the tree and down another
branch. This means you need a more complicated datastructure (e.g. a list
of pointers to some nodes above the current), and you need code for
recognition of all the different patterns. Although the number of such
patterns is farely small it is bigger than the number of possibilities
in an AVL tree, and the code needed for each possibility is smaller in
an AVL tree.
So, although the red-black tree may seem simple on paper, it is not as
simple to program. This is probably because humans are much better than
computers at pattern recognition.

Lars ([e-mail])