Talk:AVL tree

From Wikipedia, the free encyclopedia

To-do list for AVL tree: edit · history · watch · refresh

Just to make it explicit, here are some things that need to be done on this page:

  • Some new diagrams showing the balance values for each node
  • A detailed description of the insertion and deletion operations, along with diagrams showing the relevent transformations
  • A comparison to other types of self-balancing binary search trees

Derrick Coetzee 22:34, 20 Sep 2004 (UTC)
Priority 5  
This article is within the scope of WikiProject Computer science, which aims to create a comprehensive computer science reference for Wikipedia. Visit the project page for more information and to join in on related discussions.
Start rated as Start-Class on the assessment scale
Mid rated as mid-importance on the assessment scale

Contents

[edit] Question

Question from an amateur: are AVL trees generally considered worse (in terms of performance) than red-black or splay trees? Also, are they easier to implement? I suspect both to be the case. If so, someone should mention that in the article. User:MIT Trekkie 17:44, 2 Dec 2004 (UTC)

AVL Trees will give better search times than Red Black Trees. I believe the Splay Trees give better performance if you're consistently searching for a small subset of all the items in the tree. I'm not sure, but I think that AVL Trees give better search times if you do approximately the same number of searches for each item in the tree, and you do the searches in a random order. I couldn't tell you how the insertion and deletion operations will compare. --Ryan Stone 01:16, 12 Dec 2004 (UTC)
AVL Trees and also Red Black Trees both perform in O(lg n). However, for AVL trees it is < 1.44 lg n, whereas for Red Black Trees it is < 2 lg n, hence AVL trees are faster. However, AVL trees are much more complicated to implemenent. Gulliveig 04:47, 11 June 2006 (UTC)
The various operations need to be considered. AVL tree has quite excellent search, and sometimes poor insert characteristics. To make a statement so general isn't neutral in my opinion. For large database operations on disk, for example, especially for permanent records which are never deleted, AVL outperforms practically all other types of trees. So not only should the performance of various operations be compared, but also the type of application to which the structure will be used. Ste4k 18:25, 2 July 2006 (UTC)
So what would be an example of a time when you should use Red-Black trees then? -- Solberg 03:11, 26 August 2006 (UTC)Solberg
How can anyone claim that Red-Black trees are easier to implement? There's no obvious justification for this argument, and given that they both do the rotation thing (which is the only hard part) I'm having trouble imagining a justification. I'm betting Red-Black trees were merely described in detail in some textbook in whcih AVL trees were summarized. —The preceding unsigned comment was added by 67.169.10.74 (talk • contribs) .

[edit] Note

In the german wikipedia we use some very good pics to explain the balancing. see de:AVL-Baum. The are on the commons, so perhaps they are what youre searching for? -- de:Benutzer:MGla

[edit] Lazy deletion

Quoting from the article:

Deletion from an AVL tree may be carried out by rotating the node to be deleted down into a leaf node, and then pruning off that leaf node directly. Since at most log n nodes are rotated during the rotation into the leaf, and each AVL rotation takes constant time, the deletion process in total takes O(log n) time.
Practically, this is a large overhead and complex to program. Therefore, it's more common to implement a lazy deletion -- leave the deletion target in place, flag it as "deleted", and replace it with an inserted node if they would occupy the same spot.

I assume that the tree will not (usually) be balanced after a lazy deletion, so an implemention which uses lazy deletion is not strictly an AVL tree.--Malcohol 15:53, 28 June 2006 (UTC)

Actually, as long as you "clean out" the tree whenever it falls below a certain percentage full, such as 50%, I think you still get amortized O(log n) operations. In any case, whether or not this is "properly" an AVL tree, it's pretty clearly a very simple variation on one. Deco 11:54, 29 June 2006 (UTC)

While we're on the topic of deletion (operation description missing btw), the text quoted above mentions rotating a node downwards into a leaf. One may also rotate a node downwards until it has only one child, and delete it by replacing it by its only child. Jesselong 18:45, 30 October 2006 (UTC)

[edit] Insert Operation

Quoting from the article:

Insertion into an AVL tree may be carried out by inserting the given value into the tree as if it were an unbalanced binary search tree, and then retracing one's steps toward the root, rotating about any nodes which have become unbalanced during the insertion (see tree rotation). Since at most 1.5 times lg n nodes are retraced on the journey back to the root, and each AVL rotation takes constant time, the insertion process in total takes O(log n) time.

This is correct, but imprecise: After the insert, only one single or double rotation is required. Afterwards, the tree will be balanced, and no more rotations are necessary. However, finding the node that needs to be rotated about requires a recursive ascent, along which one may update the balance factors. See Knuth, Art of Comp. Prog., Vol. 3, Section 6.2.3, p. 454ff (for example, p. 454 "the new trees have height h + 2, which is exactly the height that was present before the insertion; hence the rest of the tree (if any) that was originally above node A always remains balanced", or p. 456f Algorithm A, which executes either A8 or A9 exactly once, or p. 461 Table 1, which gives probabilities when each case occurs etc). marcus

I'm not sure I understand what you're quoting. what does h represent?
Hmm, I don't believe that this is correct. Feel free to grab a sheet of paper or a white board, as I'm not going to be doing the ascii drawings here.
h refers to the height of the rotated subtree, starting at the root of the rootation or double-rotation. Please look up Knuth for more specific details. If you think this is incorrect, you may just as well provide some drawings: If you submit the to Knuth, you can cash in some real money (he rewards bug spotting with cash). marcus

Imagine inserts into a BST in the following order: 3 1 8 2 5 10 4 7 9 11 6. This is now still an AVL tree with no rotations necessary. Then, if a 6 is inserted, it is unbalanced. No single or double rotation at any level, will fix this imbalance. This structure can similarly be represented infinitely up the tree, requiring that each rotation fix the level above it, thus requiring a non-constant number of rotations. I can't prove that it is Log(n) rotations (like it could be log2n or something), but I'm sure it's more than one. In fact, I think that, the simplicity of what the article currently states might not be enough, because I think that actually getting this table into an "AVL" balanced state requires a much more complicated algorithm than just the analyzing the heights of the nodes on the way up the tree. McKay 19:27, 15 August 2006 (UTC)

I believe you mean inserting 6 after "3 1 8 2 5 10 4 7 9 11" (without the trailing 6). After that, the root has 3 with balance factor "+" (right subtree larger than left by 1), and the right subtree starts with 8 and is perfectly balanced (all balance factors 0). Now insert a 6 in the right subtree, then the balance factor of 8 becomes "+" while the tree is now unbalanced at the root (because of the 3 "+"). A single double rotation at the root makes the tree balanced, as it must. The new tree is [5: [3: [1: nil . 2] . 4] . [8: [7: 6. nil] [10: 9 . 11]]]. marcus
Another note: O(Log n) rebalances can be necessary after a delete operation. The worst case example are "Fibonacci-trees". Also, insertion of course remains O(log n), because the place for insertion needs to be looked up and the right parent node for a rotation or double rotation needs to be found, updating balance factors on the way up. marcus

[edit] unsourced?

This appears to be only a POV statement: "While AVL trees are theoretically quite sound, they are not commonly implemented due to their high implementation complexity to keep it balanced..." Ste4k 18:20, 2 July 2006 (UTC)

(also completely false) —The preceding unsigned comment was added by 67.169.10.74 (talk • contribs) .

[edit] Reason for revert.

I reverted quite a bit of work done by User:Toby Douglass. I've got reasons, so I'm writing them here:

  • first edit Not all AVL trees are balanced after every insert. If many operations are going to be performed, sometimes the tree doesn't always meet the requirements. It is possible to have a balance factor off by more than 2. Also, insertions aren't always this simple. Take for example the example I gave above, under "Insert Operation"
I could be wrong, but I think the normal case is to insert or delete and then rebalance; it's not that common for a tree to bear multiple inserts or deletes and then be rebalanced. For sure this happens, and obviously it helps optimise the tree since you don't need to do a slow rebalance so often, but it's a more advanced use and I would say doesn't rightfully belong in an initial explanation of the tree.
I would definitely disagree here. Which is more common? I'm not sure, but if there are several inserts or deletes to be performed it is more efficient to hold the balancing until it's done. I think the article should mention both.
I have no objection to both being present, but for sure, the simple, *pedagogical*, case where a single insert and rebalance should be present. It is this approach which is most useful to someone learning how AVL trees work, since it is the simplest AVL tree. If you wish to document the more sophisticated trees, please do so. I won't be doing that, since the tree I've done rebalances after each insert and so I'm not familar enough with the solution to write it up. Toby Douglass 21:17, 21 December 2006 (UTC)
  • second edit Deletions can't be done that way. What if the deleted node has both left and right children, and the inorder successor has both left and right children. Two children will be lost in the shuffle.
I could definetely be wrong here :-) I'm under the impression that it is impossible for the in-order successor to have both left and right children; if it were so, the in-order successor would actually be the left child of that supposed sucessor (assuming a tree with smaller nodes to the left side). Note also that this is the method used in the AVL applet linked to from the article.
Yes, you are mostly correct in this case. I was mistaken in this fact. The inorder successor (or predecessor) can't have both left and right children. But in my defense, the description you gave did forget to mention what should be done with the successor's children.
  • third edit typo from second edit.
  • fourth edit incorrect assertion, see first edit.
  • fifth edit dependent on changes from second edit.
  • sixth edit not proper usage of Big O. Constants like the 1.44 and the 2 are dropped. Lookups for both are big O identical. O(log n).
This notation is used in one of the links from the AVL page, which goes to a University study by a couple of professors comparing AVL with RB. Also, I think it is normal practise to write order-of to whatever degree of accuracy is appropriate for the point you're making - and here, although it's quite right to say both AVL and RB are log n, AVL is a *better* log n than RB and I assert that is the correct notation to represent that information.
Just because it's used elsewhere, doesn't mean it's right. Saying O(2) is wrong, because you should be using O(1). Smiliarly O(1.44 log n) is also wrong. If you want to talk about the order without using Big O, that might be appropriate for this article.

I'm not saying that the page can't be improved. Far from it. I think it's got a lot of necessary changes that need to be made, but I can't work on it right now. I think this will be my next project though. (this was really me) McKay 14:53, 22 September 2006 (UTC)

Let me know what you think of my rebuttals. Right now I accept your point about multiple inserts, and that should be explained in the text, and I'll point out the algorithm description presumes a single insert/delete; we need to discuss the in-order successor issue and see if delete can be done in that way or not; I disagree that the O() notion is improper. Toby Douglass 16:12, 22 September 2006 (UTC)
Well, I'm pretty sure that it is incorrect. Feel free to read up on Big_O_notation, and tell me where I'm wrong (my argument is the line that says "coefficients become irrelevant as well" and "Big O captures what remains"). One "additional" point of my argument is that you use the tightest Big O possible, and while something may take f(x) = Log2n, The big O is O(g(x)), g(x) = log(x). The definition of Big O says that as long as I can come up with constants to satisfy
for all x > a0, c0g(x) > f(x).
My Big O is satisfied. So in all cases, I can choose a0 = 3, c0 = 3. Now I can say that all are identical from a big O perspective. log x, 2 log x, 1.44 log x. Each can be said to be big O of both of the other two. Coefficients should be ignored in big O. McKay 15:57, 26 September 2006 (UTC)
You're both right. For the purposes of the discussion, it is important to note the constants hidden by the O-notation, but it is technically inappropriate to use O(c*n) for c a constant. Thus, unless exact runtimes are known (up to a scale), the best wording for comparison of algorithms asymptotically equivalent is e.g.: "Both are O(lg n) but the constants hidden by the notation are much smaller in algorithm X." --Quintopia 22:19, 10 November 2006 (UTC)
Very very close. The purpose of big oh, is for order of magnitude differences of the worst case scenario with respect to n. Because of this, constants are necessarily removed for the purpose of Big oh. "Constants hidden by the notation" is a wee bit misleading, because it's actually more precisely "constants hidden by the worst case scenario are much smaller in algorithm X" Big O was chosen to do a purpose, and it does it well (order of magnitude differences of the worst case scenario with respect to the size of the input set), but it need not be used in every case. Saying "constants hidden by the worst case scenario are much smaller in algorithm X" is almost worthless. A much more valuable approach would to probably do a big Theta, or an average case. The problem here is that average case for an AVL tree and for Red Black trees is non-trivial to calculate. So, the better way of comparing algorithms is using the easy Big-O, "Both are O(log n)" talking about the "constants hidden by the [Big-O] notation" is demeaning (for lack of a better word) to the notation, and doesn't really mean much. Who really cares if red black trees are actually 1.333 times worse in the worst case. These worst case scenarios aren't even likely, so the Big-O is sufficent. McKay 08:48, 11 November 2006 (UTC)
Some people care deeply! this is why Oracle uses AVL trees and not red-black trees. Also, if you come to choose a tree, why choose the less efficient tree when you could just as well choose one that is better?
Order-of is usually used in the way largely described here - you deal, as the name implies, with the order of magnitude of the operation. However, I see absolutely no harm and instead, benefit, in also using the notion to express smaller differences when the point of that particular use is simply to indicate that that information is available.
My view in this is that this deep concern to be exactly legal in the use of order-of notation is harmful. It's unimaginative and impedes explaining the concept in hand to the reader. Toby Douglass 21:17, 21 December 2006 (UTC)

[edit] Problem?

In the depicted unbalanced and balanced trees, the balancing of the leftmost 3-element subtree doesn't appear to be able to be done by tree rotations as they are defined on the tree rotations page. When the 9 is rotated out and the 14 in, the twelve will switch to the opposite side, maintaining the imbalance. When this imbalance is "fixed" by another rotation, it will simply be returned to its original state. Thus, this subtree can never be balanced by rotations. Clearly, it is a special case for implementation, and should be noted either on this page or the tree rotations page. I intend to do so if no one objects. --Quintopia 22:13, 10 November 2006 (UTC)

Well, I don't think the article necessarily needs to explain how how to convert an arbitrary binary search tree like that 3-element subtree you mentioned into an AVL tree. But I agree, it would be interesting to state an algorithm how to do it. A simple one might be to create an empty tree, then walk the original unbalanced tree in-order, and insert each node into the new tree, using the AVL-insert. That should take O(n*log n). --Allefant 14:24, 24 November 2006 (UTC)

[edit] Diagrams

There are some diagrams of AVL trees at Commons:Category:AVL-trees that may be helpful. Deco 06:43, 21 February 2007 (UTC)

[edit] Rewrite

the example section got needlessly complex with references to null structures... I did a rewrite of that section, feel free to adjust or rever to a previous version if you like. I also removed the images because rotations aren't covered in this article directly, but in the tree rotation article. McKay 22:32, 14 May 2007 (UTC)

[edit] Explanation

I'm angry. I created a new section, trying to write a *human-readable* explanation of AVL trees (e.g. one which you can read near enough from first principles, without having to already know so much computer science that you probably already know what AVL trees are anyway), did quite a bit of work and the section is a work-in-progress; I've not finished, and I'm currently creating a set of images to explain the flow of explanation.

And you - Mckaysalisbury - have taken out 4kb of what I've written without so much as a by-your-leave.

I'm going to reinstate the material you've taken out and if you don't like it, and you think it should be removed, you can damn well show enough respect to discuss it here first.

Toby Douglass 07:21, 15 May 2007 (UTC)

I did mention it here. One of the wikipedia policies is Be Bold. I was doing just that. I also mentioned that a revert or adjustment was allowed (encouraging you to be bold)
I read that. You wrote the "example section". The section is called the "explanation section". I thought that comment was about a different edit. Moreover, Be Bold doesn't mean you get to Be Rude. When people put time and effort in, wiping it out with a mass removal without prior discussion or mentioning it or even mentioning to them in their talk is *unnecessary*. There is nothing stopping you showing consideration; we're not in a race.
The "Explanation" section was rewritten by Toby Douglass. This is his version. If you like I'll provide a more critical commentary of why I removed the content.
  • It isn't written in the formal tone of an encyclopedia (consistent mentionings of "you", weird phrases like "the tricky bit", ...)
Quite so. Work in progress.
  • It fails to adhere to the WP:MOS (wikilinks were non-existent, as were any formatting, spacing strange)
Quite so. Work in progress.
  • I find it funny that the version I wrote is criticised as requiring so much knowledge of computer science, but the version I removed contained phrases like "NULL pointer" which is strictly a computer science term.
Quite so. Work in progress. Moreover, there are but one or two cases of such usage and such usage is very simple and common; anyone reading it will be in the computing field and will possess basic knowledge. I want to avoid more domain specific knowledge.
  • It contains misleading OR phrases about a "naive first try at doing this" mentioning element counts, which I claim are needlessly complicated for AVL presentation. AVL works off of the height of a subtree, not the element counts. Why needlessly add element counts?
Because it helps explain the AVL concept. AVL is not immediately obvious. I want to lead people into it, showing them that you can keep information to know about rebalancing, and then dealing with the most obvious idea (which most people seem to come across by themselves) of element counts. Understanding why element counts *DON'T* work is almost properly tantamount to understanding why and how AVL trees DO work.
  • The section seems to have poor writing style, in that it leaves the reader hanging
Quite so. Work in progress. It isn't finished. I've spent the last two days enhancing a bitmap API I've written so I can programmatically produce image files for the article. I want to demonstrate how the element count approach fails and then show the AVL tree behaviour.
  • On the other hand. I did like how toby did try to create a section about why AVL trees are better
So, I felt it was best to rewite the section in proper tone, adhering to MOS, remove CS terms, remove OR (though I could source much of this), simplify explanation, while keeping the intent of the author, who, wanted to make the section better. McKay 19:20, 15 May 2007 (UTC)
Second level comments from Toby Douglass 14:20, 16 May 2007 (UTC)
Yes, I understand what you were trying to accomplish, please don't get mad at me for improving a section that you admit to being a work in progress. I liked a few of the things you were trying to accomplish, so I went ahead and improved based on your ideas. I didn't like the specific direction you were taking the content, so I took it in a direction I thought was better.
I'm mad at you for taking about SO much material without a by-your-leave, not for what you were trying to achieve. Your goal does not justify or permit your method. Toby Douglass 17:34, 16 May 2007 (UTC)
I mentioned it on the talk page. You yourself said the material was a work in progress. I felt like the content you added was a blister on the page, and needed to be rectified as soon as possible. The first thing I did was start to clean it up, and then I realized that I objected to the content on the page. So I rewrote it. The content was factually inaccurate due to your OR. McKay 18:12, 16 May 2007 (UTC)
I'm simplifying the concept of NULLs and saying "doesn't have a child". It shows the concept without dealing about implementation specific issues. Threading and other related concepts might use the data and would make it not null but still not have children. Mentioning NULL is inappropriate.
I concur that NULL is inappropriate. Toby Douglass 17:34, 16 May 2007 (UTC)
Your opinion about element counts doesn't belong in wikipedia. Personally I think element counts *do* work, but it's more complicated than your model. Height balancing was chosen because it's simpler than element count, but still produces the requisite O(log(n)) insertions and lookups. In any case, mentioning element counts in terms of AVL is OR and doesn't belong here. AVL is about height balancing, that's what should be explained, I don't think this article should go off in a different direction than what AVL actually is. McKay 15:43, 16 May 2007 (UTC)
Eh, what? my opinion that they're a useful explanatory aid? that opinion doesn't belong in wikipedia? surely the whole of the wikipedia is people's opinions about what explains things? the purpose of an article is to explain what it is about. AVL is not immediately intuitive. There will be MANY ways in which people can be led to understand. In what way *CAN* my choice of explanation be "an opinion which doesn't belong in wikipedia"? Toby Douglass 17:34, 16 May 2007 (UTC)
What is OR is that:
  • AVL is less intuitive than element counts
  • "However, the problem with element counts though is that the number of elements on the left or right of an element doesn't tell you anything about how they are arranged." In fact the entire section where you're talking about number of elements is factually inaccurate. Element count is actually better than Height balancing, but it's harder to implement, and doesn't provide O(Log(n)) insertion times. The entire section from where I just quoted to "what you in fact end up with are linked lists on each side of each element." is factually incorrect, because an element balanced tree is better than a height balanced tree. It needed to be removed as quick as possible. It would have been wrong for me to wait for a "by your leave". WP:BOLD. McKay 18:12, 16 May 2007 (UTC)


[edit] Image

I removed the image again for a couple of reasons:

  • The image doesn't seem to fit anywhere. We don't have a section on rotations, we've deferred most of that concept to the Tree rotation page.
  • The image is inaccurate. I doesn't adequately show how to perform a rotation, specifically, it doesn't show what to do with the other children of the pivot. McKay 15:43, 16 May 2007 (UTC)
Maybe we should add a small section about rotations here? McKay 18:12, 16 May 2007 (UTC)

[edit] Worst case search order

Hi. Accessing the deepest node in the most unbalanced AVL leads to a search time loggolden_ratio n, not 1.44 or 1.5 lg n as specified in the current version. I don't have time to fix this but, whoever wants this article to be accurate should change this. Martlau 13:41, 23 May 2007 (UTC)

  1. Most importantly, can you attribute that?
  2. doing the math, because I'm curious:
    • logphi(n) = lg(n)/lg(phi) ~~ 1.44042009 * lg(n)
    • so your statement is probably correct, and properly represented in the article, Maybe it should be worded that way, but I personally think that use of lg n is best used in this article relating to binary trees McKay 15:08, 23 May 2007 (UTC)

I'm somehow puzzled by those "log"s here. what is lg(n) exactly ? log2(n) ? log10(n) ? ln(n) ? —Preceding unsigned comment added by 139.165.223.18 (talk) 08:08, 8 May 2008 (UTC)

Logarithm. log2(n) is logarithm base 2, log10 is base 10, ln(n) is natural logarithm, base e (mathematical constant) -- intgr [talk] 10:58, 9 May 2008 (UTC)

[edit] Explanation

I've completely replaced the current explanation, which, IMO, totally failed to explain anything, and replaced it with something which I have written to be a human-readable explanation of how an AVL tree works, so that someone who doens't know how AVL trees work can read it and then know. Toby Douglass 12:39, 17 October 2007 (UTC)

I note that User:Mikkalai has completely removed this section, on the basis that this is not a "Data Structures for Dummies". I contest this; if the article does not effectively explain how an AVL tree works, it cannot claim to be an article about AVL trees! Toby Douglass 17:00, 26 October 2007 (UTC)
Wikipedia articles must be written basing on printed books and supplied with references.
Then you'd better delete the rest of the article, because there isn't a single citation in it. Everything that's written is someone's attempt to explain how an AVL tree works.
What you wrote was your interpretation how it works. Please keep in mind that the reason of the efficiency of AVL tree is described in the Self-balancing binary search tree, linked at the very beginning. Please explain what is unclear in the current description.
It utterly fails to explain how an AVL tree functions: you cannot read this article and then implement an AVL tree. By and large, the explanations in the page explain *to someone who already understands* - which is utterly, UTTERLY useless.
The text describes the operations and their computationaal complexity. If you want to clarify something, please follow the current structure of the article, and don't please forget to provide references where your new information came from. `'Míkka 17:09, 26 October 2007 (UTC)
P.S. I've just noticed that I am not the first person who disagrees with your way of writing (looking higher in this talk page). `'Míkka 17:22, 26 October 2007 (UTC)
Yes, you are not the only person who doesn't see the point of an article actually telling people how to implement an AVL tree. There seems to be a view that the article should almost *clinically* describe the AVL tree, as if that is the purpose and end of the page. What possible use it that? the only people who would find it useful would be those who already understood how the tree works. Everyone else would find it incredibly hard going to try and figure out the principle underlying the tree. Toby Douglass 23:22, 2 November 2007 (UTC)

I am all for simplifying the language of terse computer science articles, but I find the writing style of this section somewhat lacking. For example, it refers to unbalanced trees as "normal binary trees", while in fact they are quite abnormal in practice (nearly all binary tree implementations in real applications are some sort of balanced trees). Linked lists are described as "a single long line". Second, it uses the grammatical first person which is discouraged (WP:MOS); the paragraphs are too short, phrases like "in fact" are used too often. In general what I find a "non-encyclopedic" writing style. I also agree that it doesn't quite fit into the article's structure. -- intgr [talk] 23:02, 3 November 2007 (UTC)

[edit] Implementations

I reintegrated a selected few of Mikkalai's massive rm of links (as I was looking for one which I thought I had seen once). It is quite accepted with other data structures, that a maximum of one implementation per programming language is linked, as an example for interested students and programmers. However, I collected them under a new title Implementations rather than under the previous External Links. Is this acceptable also for you, Mikkalai? --Gulliveig 02:46, 3 November 2007 (UTC)

External link lists should be collected under the "external links" section. I realize that links to AVL tree source code are very relevant and useful, but I dislike long external link lists because they invite everyone to add their own favourite to the list, so they build up cruft over time and degrade into uselessness again; not to mention the problem with spammers. Coming up with a non-arbitrary criteria for external links is very hard. -- intgr [talk] 22:33, 3 November 2007 (UTC)

[edit] Comparision

To help the beginners understand, I think comparision is very important. For example, comparision between insertion and deletion, comparision with other self-balancing trees, etc. Visame (talk) 19:59, 7 June 2008 (UTC)