Differences between current version and predecessor to the previous major change of AVLTree.
Other diffs: Previous Revision, Previous Author, or view the Annotated Edit History
| Newer page: | version 3 | Last edited on Tuesday, September 2, 2003 1:33:01 am | by AristotlePagaltzis | |
| Older page: | version 1 | Last edited on Monday, September 1, 2003 9:22:28 am | by GreigMcGill | Revert |
@@ -1 +1,5 @@
-A balanced binary search tree where the height of the two subtrees (children) of a node differs by at most one. Look-up, insertion, and deletion are O( log n), where n is the number of nodes in the tree.
+A balanced binary search tree where the height of the two subtrees (children) of a node differs by at most one. Look-up, insertion, and deletion are ''
O(log n)'' (see [BigONotation]
), where ''
n''
is the number of nodes in the tree.
+
+This is done by keeping a value in each node of the tree which is equal to it's height. (ie: for leaf nodes it's , for nodes above them it's 1, nodes above them 2 and so on).
+
+When you insert a new node, you see if this makes one subtree off an internal node longer than the other and if so do a rotate so that they are equal again
.
