From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,abc7dd97bf9a7dc7 X-Google-Attributes: gid103376,public From: "Joel VanLaven" Subject: Re: Help with Deletion (not lazy) from AVL Trees Date: 1999/03/12 Message-ID: #1/1 X-Deja-AN: 454082529 References: <7c2g6c$5e1$1@camel25.mindspring.com> <7c3v0o$48$1@camel0.mindspring.com> <7c7co9$nvt$3@plug.news.pipex.net> X-MimeOLE: Produced By Microsoft MimeOLE V4.72.3110.3 X-Trace: news6.ispnews.com 921216686 206.161.15.42 (Fri, 12 Mar 1999 00:31:26 EDT) NNTP-Posting-Date: Fri, 12 Mar 1999 00:31:26 EDT Newsgroups: comp.lang.ada Date: 1999-03-12T00:00:00+00:00 List-Id: Nick Roberts wrote in message <7c7co9$nvt$3@plug.news.pipex.net>... >Two things occur to me: it's funny how the same algorithm >can be expressed in so many (largely cosmetically) different ways, even in >the same language; most people use red-black trees rather than AVL trees >these days (often as a matter of fashion, I reckon), since (allegedly) RBTs >generally have better (search?) performance. Hmm. It is my impression that the two common balanced binary tree algorithms (well, the two I have run into) are AVL trees and 2-3-4 trees. Both can be implemented as red-black trees. Assuming the red-black implementation of each, I believe that 2-3-4 trees are simpler and can be optimized for faster insertion (and deletion ?) Whereas AVL trees have a better worst-case height (and hence in theory seach speed) but have more complicated insertion. In fact, I worked it out once and the worst case height of an AVL tree is related to the Fibonnaci (why can't I spell that) sequence and through it the golden ratio for about > log base (1+sqrt(5))/2 (n) height where n is the number of nodes On the other hand, red-black 2-3-4 trees are something like 2*log base 2 (n) or rather log base sqrt(2) (n) What is more, I belive that most 2-3-4 implementations will yield the worst case in normal situations like sorted-order insertion whereas AVL trees will not, it is a "wacky" order insertion that yields the worst case. I'm not positive of that though. -- Joel VanLaven