Annotated edit history of
AVLTree version 3 showing authors affecting page license.
View with all changes included.
| Rev |
Author |
# |
Line |
| 1 |
GreigMcGill |
1 |
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. |
| 2 |
PerryLorier |
2 |
|
| |
|
3 |
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 0, for nodes above them it's 1, nodes above them 2 and so on). |
| |
|
4 |
|
| |
|
5 |
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. |
