AVL tree
In computer science, an AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.
You are encouraged to solve this task according to the task description, using any language you may know.
| This page uses content from Wikipedia. The original article was at AVL tree. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance) |
AVL trees are often compared with red-black trees because they support the same set of operations and because red-black trees also take O(log n) time for the basic operations. Because AVL trees are more rigidly balanced, they are faster than red-black trees for lookup-intensive applications. Similar to red-black trees, AVL trees are height-balanced, but in general not weight-balanced nor μ-balanced; that is, sibling nodes can have hugely differing numbers of descendants.
- Task
Implement an AVL tree in the language of choice, and provide at least basic operations.
Agda
This implementation uses the type system to enforce the height invariants, though not the BST invariants <lang agda> module Avl where
-- The Peano naturals data Nat : Set where
z : Nat s : Nat -> Nat
-- An AVL tree's type is indexed by a natural. -- Avl N is the type of AVL trees of depth N. There arj 3 different -- node constructors: -- Left: The left subtree is one level deeper than the right -- Balanced: The subtrees have the same depth -- Right: The right Subtree is one level deeper than the left -- Since the AVL invariant is that the depths of a node's subtrees -- always differ by at most 1, this perfectly encodes the AVL depth invariant. data Avl : Nat -> Set where
Empty : Avl z
Left : {X : Nat} -> Nat -> Avl (s X) -> Avl X -> Avl (s (s X))
Balanced : {X : Nat} -> Nat -> Avl X -> Avl X -> Avl (s X)
Right : {X : Nat} -> Nat -> Avl X -> Avl (s X) -> Avl (s (s X))
-- A wrapper type that hides the AVL tree invariant. This is the interface -- exposed to the user. data Tree : Set where
avl : {N : Nat} -> Avl N -> Tree
-- Comparison result data Ord : Set where
Less : Ord Equal : Ord Greater : Ord
-- Comparison function cmp : Nat -> Nat -> Ord cmp z (s X) = Less cmp z z = Equal cmp (s X) z = Greater cmp (s X) (s Y) = cmp X Y
-- Insertions can either leave the depth the same or -- increase it by one. Encode this in the type. data InsertResult : Nat -> Set where
Same : {X : Nat} -> Avl X -> InsertResult X
Bigger : {X : Nat} -> Avl (s X) -> InsertResult X
-- If the left subtree is 2 levels deeper than the right, rotate to the right. -- balance-left X L R means X is the root, L is the left subtree and R is the right. balance-left : {N : Nat} -> Nat -> Avl (s (s N)) -> Avl N -> InsertResult (s (s N)) balance-left X (Right Y A (Balanced Z B C)) D = Same (Balanced Z (Balanced X A B) (Balanced Y C D)) balance-left X (Right Y A (Left Z B C)) D = Same (Balanced Z (Balanced X A B) (Right Y C D)) balance-left X (Right Y A (Right Z B C)) D = Same (Balanced Z (Left X A B) (Balanced Y C D)) balance-left X (Left Y (Balanced Z A B) C) D = Same (Balanced Z (Balanced X A B) (Balanced Y C D)) balance-left X (Left Y (Left Z A B) C) D = Same (Balanced Z (Left X A B) (Balanced Y C D)) balance-left X (Left Y (Right Z A B) C) D = Same (Balanced Z (Right X A B) (Balanced Y C D)) balance-left X (Balanced Y (Balanced Z A B) C) D = Bigger (Right Z (Balanced X A B) (Left Y C D)) balance-left X (Balanced Y (Left Z A B) C) D = Bigger (Right Z (Left X A B) (Left Y C D)) balance-left X (Balanced Y (Right Z A B) C) D = Bigger (Right Z (Right X A B) (Left Y C D))
-- Symmetric with balance-left balance-right : {N : Nat} -> Nat -> Avl N -> Avl (s (s N)) -> InsertResult (s (s N)) balance-right X A (Left Y (Left Z B C) D) = Same (Balanced Z (Balanced X A B) (Right Y C D)) balance-right X A (Left Y (Balanced Z B C) D) = Same(Balanced Z (Balanced X A B) (Balanced Y C D)) balance-right X A (Left Y (Right Z B C) D) = Same(Balanced Z (Left X A B) (Balanced Y C D)) balance-right X A (Balanced Z B (Left Y C D)) = Bigger(Left Z (Right X A B) (Left Y C D)) balance-right X A (Balanced Z B (Balanced Y C D)) = Bigger (Left Z (Right X A B) (Balanced Y C D)) balance-right X A (Balanced Z B (Right Y C D)) = Bigger (Left Z (Right X A B) (Right Y C D)) balance-right X A (Right Z B (Left Y C D)) = Same (Balanced Z (Balanced X A B) (Left Y C D)) balance-right X A (Right Z B (Balanced Y C D)) = Same (Balanced Z (Balanced X A B) (Balanced Y C D)) balance-right X A (Right Z B (Right Y C D)) = Same (Balanced Z (Balanced X A B) (Right Y C D))
-- insert' T N does all the work of inserting the element N into the tree T. insert' : {N : Nat} -> Avl N -> Nat -> InsertResult N insert' Empty N = Bigger (Balanced N Empty Empty) insert' (Left Y L R) X with cmp X Y insert' (Left Y L R) X | Less with insert' L X insert' (Left Y L R) X | Less | Same L' = Same (Left Y L' R) insert' (Left Y L R) X | Less | Bigger L' = balance-left Y L' R insert' (Left Y L R) X | Equal = Same (Left Y L R) insert' (Left Y L R) X | Greater with insert' R X insert' (Left Y L R) X | Greater | Same R' = Same (Left Y L R') insert' (Left Y L R) X | Greater | Bigger R' = Same (Balanced Y L R') insert' (Balanced Y L R) X with cmp X Y insert' (Balanced Y L R) X | Less with insert' L X insert' (Balanced Y L R) X | Less | Same L' = Same (Balanced Y L' R) insert' (Balanced Y L R) X | Less | Bigger L' = Bigger (Left Y L' R) insert' (Balanced Y L R) X | Equal = Same (Balanced Y L R) insert' (Balanced Y L R) X | Greater with insert' R X insert' (Balanced Y L R) X | Greater | Same R' = Same (Balanced Y L R') insert' (Balanced Y L R) X | Greater | Bigger R' = Bigger (Right Y L R') insert' (Right Y L R) X with cmp X Y insert' (Right Y L R) X | Less with insert' L X insert' (Right Y L R) X | Less | Same L' = Same (Right Y L' R) insert' (Right Y L R) X | Less | Bigger L' = Same (Balanced Y L' R) insert' (Right Y L R) X | Equal = Same (Right Y L R) insert' (Right Y L R) X | Greater with insert' R X insert' (Right Y L R) X | Greater | Same R' = Same (Right Y L R') insert' (Right Y L R) X | Greater | Bigger R' = balance-right Y L R'
-- Wrapper around insert' to use the depth-agnostic type Tree. insert : Tree -> Nat -> Tree insert (avl T) X with insert' T X ... | Same T' = avl T' ... | Bigger T' = avl T' </lang>
C#
See AVL_tree/C_sharp.
C
See AVL tree/C
C++
<lang cpp>
- include <algorithm>
- include <iostream>
/* AVL node */ template <class T> class AVLnode { public:
T key; int balance; AVLnode *left, *right, *parent;
AVLnode(T k, AVLnode *p) : key(k), balance(0), parent(p),
left(NULL), right(NULL) {}
~AVLnode() {
delete left;
delete right;
}
};
/* AVL tree */ template <class T> class AVLtree { public:
AVLtree(void); ~AVLtree(void); bool insert(T key); void deleteKey(const T key); void printBalance();
private:
AVLnode<T> *root;
AVLnode<T>* rotateLeft ( AVLnode<T> *a ); AVLnode<T>* rotateRight ( AVLnode<T> *a ); AVLnode<T>* rotateLeftThenRight ( AVLnode<T> *n ); AVLnode<T>* rotateRightThenLeft ( AVLnode<T> *n ); void rebalance ( AVLnode<T> *n ); int height ( AVLnode<T> *n ); void setBalance ( AVLnode<T> *n ); void printBalance ( AVLnode<T> *n ); void clearNode ( AVLnode<T> *n );
};
/* AVL class definition */ template <class T> void AVLtree<T>::rebalance(AVLnode<T> *n) {
setBalance(n);
if (n->balance == -2) {
if (height(n->left->left) >= height(n->left->right))
n = rotateRight(n);
else
n = rotateLeftThenRight(n);
}
else if (n->balance == 2) {
if (height(n->right->right) >= height(n->right->left))
n = rotateLeft(n);
else
n = rotateRightThenLeft(n);
}
if (n->parent != NULL) {
rebalance(n->parent);
}
else {
root = n;
}
}
template <class T> AVLnode<T>* AVLtree<T>::rotateLeft(AVLnode<T> *a) {
AVLnode<T> *b = a->right; b->parent = a->parent; a->right = b->left;
if (a->right != NULL)
a->right->parent = a;
b->left = a; a->parent = b;
if (b->parent != NULL) {
if (b->parent->right == a) {
b->parent->right = b;
}
else {
b->parent->left = b;
}
}
setBalance(a); setBalance(b); return b;
}
template <class T> AVLnode<T>* AVLtree<T>::rotateRight(AVLnode<T> *a) {
AVLnode<T> *b = a->left; b->parent = a->parent; a->left = b->right;
if (a->left != NULL)
a->left->parent = a;
b->right = a; a->parent = b;
if (b->parent != NULL) {
if (b->parent->right == a) {
b->parent->right = b;
}
else {
b->parent->left = b;
}
}
setBalance(a); setBalance(b); return b;
}
template <class T> AVLnode<T>* AVLtree<T>::rotateLeftThenRight(AVLnode<T> *n) {
n->left = rotateLeft(n->left); return rotateRight(n);
}
template <class T> AVLnode<T>* AVLtree<T>::rotateRightThenLeft(AVLnode<T> *n) {
n->right = rotateRight(n->right); return rotateLeft(n);
}
template <class T> int AVLtree<T>::height(AVLnode<T> *n) {
if (n == NULL)
return -1;
return 1 + std::max(height(n->left), height(n->right));
}
template <class T> void AVLtree<T>::setBalance(AVLnode<T> *n) {
n->balance = height(n->right) - height(n->left);
}
template <class T> void AVLtree<T>::printBalance(AVLnode<T> *n) {
if (n != NULL) {
printBalance(n->left);
std::cout << n->balance << " ";
printBalance(n->right);
}
}
template <class T> AVLtree<T>::AVLtree(void) : root(NULL) {}
template <class T> AVLtree<T>::~AVLtree(void) {
delete root;
}
template <class T> bool AVLtree<T>::insert(T key) {
if (root == NULL) {
root = new AVLnode<T>(key, NULL);
}
else {
AVLnode<T>
*n = root,
*parent;
while (true) {
if (n->key == key)
return false;
parent = n;
bool goLeft = n->key > key;
n = goLeft ? n->left : n->right;
if (n == NULL) {
if (goLeft) {
parent->left = new AVLnode<T>(key, parent);
}
else {
parent->right = new AVLnode<T>(key, parent);
}
rebalance(parent);
break;
}
}
}
return true;
}
template <class T> void AVLtree<T>::deleteKey(const T delKey) {
if (root == NULL)
return;
AVLnode<T>
*n = root,
*parent = root,
*delNode = NULL,
*child = root;
while (child != NULL) {
parent = n;
n = child;
child = delKey >= n->key ? n->right : n->left;
if (delKey == n->key)
delNode = n;
}
if (delNode != NULL) {
delNode->key = n->key;
child = n->left != NULL ? n->left : n->right;
if (root->key == delKey) {
root = child;
}
else {
if (parent->left == n) {
parent->left = child;
}
else {
parent->right = child;
}
rebalance(parent);
}
}
}
template <class T> void AVLtree<T>::printBalance() {
printBalance(root); std::cout << std::endl;
}
int main(void) {
AVLtree<int> t;
std::cout << "Inserting integer values 1 to 10" << std::endl;
for (int i = 1; i <= 10; ++i)
t.insert(i);
std::cout << "Printing balance: "; t.printBalance();
} </lang>
- Output:
Inserting integer values 1 to 10 Printing balance: 0 0 0 1 0 0 0 0 1 0
More elaborate version
See AVL_tree/C++
Managed C++
Common Lisp
Provided is an imperative implementation of an AVL tree with a similar interface and documentation to HASH-TABLE. <lang lisp>(defpackage :avl-tree
(:use :cl) (:export :avl-tree :make-avl-tree :avl-tree-count :avl-tree-p :avl-tree-key<= :gettree :remtree :clrtree :dfs-maptree :bfs-maptree))
(in-package :avl-tree)
(defstruct %tree
key value balance left right)
(defstruct (avl-tree (:constructor %make-avl-tree))
key<= tree count)
(defun make-avl-tree (key<=)
"Create a new AVL tree using the given comparison function KEY<=
for emplacing keys into the tree."
(%make-avl-tree :key<= key<= :count 0))
(defun height (tree)
"Calculate the height of a tree, assuming the balances are correct."
(if tree
(1+ (height (if (<= 0 (%tree-balance tree))
(%tree-right tree)
(%tree-left tree))))
0))
(defun calc-balance (tree)
"Calculate the new balance of the tree from the heights of the children."
(setf (%tree-balance tree)
(- (height (%tree-right tree))
(height (%tree-left tree)))))
(defmacro swap (place-a place-b)
"Swap the values of two places."
(let ((tmp (gensym)))
`(let ((,tmp ,place-a))
(setf ,place-a ,place-b)
(setf ,place-b ,tmp))))
(defun swap-kv (tree-a tree-b)
"Swap the keys and values of two trees." (swap (%tree-value tree-a) (%tree-value tree-b)) (swap (%tree-key tree-a) (%tree-key tree-b)))
- We should really use gensyms for the variables in here.
(defmacro slash-rotate (tree right left)
"Rotate nodes in a slash `/` imbalance."
`(let* ((a ,tree)
(b (,right a))
(c (,right b))
(a-left (,left a))
(b-left (,left b)))
(setf (,right a) c)
(setf (,left a) b)
(setf (,left b) a-left)
(setf (,right b) b-left)
(swap-kv a b)
(calc-balance b)
(calc-balance a)))
(defmacro angle-rotate (tree right left)
"Rotate nodes in an angle bracket `<` imbalance."
`(let* ((a ,tree)
(b (,right a))
(c (,left b))
(a-left (,left a))
(c-left (,left c))
(c-right (,right c)))
(setf (,left a) c)
(setf (,left c) a-left)
(setf (,right c) c-left)
(setf (,left b) c-right)
(swap-kv a c)
(calc-balance c)
(calc-balance b)
(calc-balance a)))
(defun right-right-rotate (tree)
(slash-rotate tree %tree-right %tree-left))
(defun left-left-rotate (tree)
(slash-rotate tree %tree-left %tree-right))
(defun right-left-rotate (tree)
(angle-rotate tree %tree-right %tree-left))
(defun left-right-rotate (tree)
(angle-rotate tree %tree-left %tree-right))
(defun rotate (tree)
"Perform a rotation on the given TREE if it is imbalanced."
(calc-balance tree)
(with-slots ((broot balance) left right) tree
(cond ((< 1 broot) ;; Right heavy tree
(if (<= 0 (%tree-balance right))
(right-right-rotate tree)
(right-left-rotate tree)))
((> -1 broot) ;; Left heavy tree
(if (<= 0 (%tree-balance left))
(left-right-rotate tree)
(left-left-rotate tree))))))
(defun gettree (key avl-tree &optional default)
"Finds an entry in AVL-TREE whos key is KEY and returns the
associated value and T as multiple values, or returns DEFAULT and NIL if there was no such entry. Entries can be added using SETF."
(with-slots (key<= tree) avl-tree
(labels
((rec (tree)
(if tree
(with-slots ((t-key key) left right value) tree
(if (funcall key<= t-key key)
(if (funcall key<= key t-key)
(values value t)
(rec right))
(rec left)))
(values default nil))))
(rec tree))))
(defun puttree (value key avl-tree)
"Emplace the the VALUE with the given KEY into the AVL-TREE, or
overwrite the value if the given key already exists."
(let ((node (make-%tree :key key :value value :balance 0)))
(with-slots (key<= tree count) avl-tree
(cond (tree
(labels
((rec (tree)
(with-slots ((t-key key) left right) tree
(if (funcall key<= t-key key)
(if (funcall key<= key t-key)
(setf (%tree-value tree) value)
(cond (right (rec right))
(t (setf right node)
(incf count))))
(cond (left (rec left))
(t (setf left node)
(incf count))))
(rotate tree))))
(rec tree)))
(t (setf tree node)
(incf count))))
value))
(defun (setf gettree) (value key avl-tree &optional default)
(declare (ignore default)) (puttree value key avl-tree))
(defun remtree (key avl-tree)
"Remove the entry in AVL-TREE associated with KEY. Return T if
there was such an entry, or NIL if not."
(with-slots (key<= tree count) avl-tree
(labels
((find-left (tree)
(with-slots ((t-key key) left right) tree
(if left
(find-left left)
tree)))
(rec (tree &optional parent type)
(when tree
(prog1
(with-slots ((t-key key) left right) tree
(if (funcall key<= t-key key)
(cond
((funcall key<= key t-key)
(cond
((and left right)
(let ((sub-left (find-left right)))
(swap-kv sub-left tree)
(rec right tree :right)))
(t
(let ((sub (or left right)))
(case type
(:right (setf (%tree-right parent) sub))
(:left (setf (%tree-left parent) sub))
(nil (setf (avl-tree-tree avl-tree) sub))))
(decf count)))
t)
(t (rec right tree :right)))
(rec left tree :left)))
(when parent (rotate parent))))))
(rec tree))))
(defun clrtree (avl-tree)
"This removes all the entries from AVL-TREE and returns the tree itself." (setf (avl-tree-tree avl-tree) nil) (setf (avl-tree-count avl-tree) 0) avl-tree)
(defun dfs-maptree (function avl-tree)
"For each entry in AVL-TREE call the two-argument FUNCTION on
the key and value of each entry in depth-first order from left to right. Consequences are undefined if AVL-TREE is modified during this call."
(with-slots (key<= tree) avl-tree
(labels
((rec (tree)
(when tree
(with-slots ((t-key key) left right key value) tree
(rec left)
(funcall function key value)
(rec right)))))
(rec tree))))
(defun bfs-maptree (function avl-tree)
"For each entry in AVL-TREE call the two-argument FUNCTION on
the key and value of each entry in breadth-first order from left to right. Consequences are undefined if AVL-TREE is modified during this call."
(with-slots (key<= tree) avl-tree
(let* ((queue (cons nil nil))
(end queue))
(labels ((pushend (value)
(when value
(setf (cdr end) (cons value nil))
(setf end (cdr end))))
(empty-p () (eq nil (cdr queue)))
(popfront ()
(prog1 (pop (cdr queue))
(when (empty-p) (setf end queue)))))
(when tree
(pushend tree)
(loop until (empty-p)
do (let ((current (popfront)))
(with-slots (key value left right) current
(funcall function key value)
(pushend left)
(pushend right)))))))))
(defun test ()
(let ((tree (make-avl-tree #'<=))
(printer (lambda (k v) (print (list k v)))))
(loop for key in '(0 8 6 4 2 3 7 9 1 5 5)
do (setf (gettree key tree) key))
(loop for key in '(0 1 2 3 4 10)
do (print (multiple-value-list (gettree key tree))))
(terpri)
(print tree)
(terpri)
(dfs-maptree printer tree)
(terpri)
(bfs-maptree printer tree)
(terpri)
(loop for key in '(0 1 2 3 10 7)
do (print (remtree key tree)))
(terpri)
(print tree)
(terpri)
(clrtree tree)
(print tree))
(values))</lang>
D
<lang d>import std.stdio, std.algorithm;
class AVLtree {
private Node* root;
private static struct Node {
private int key, balance;
private Node* left, right, parent;
this(in int k, Node* p) pure nothrow @safe @nogc {
key = k;
parent = p;
}
}
public bool insert(in int key) pure nothrow @safe {
if (root is null)
root = new Node(key, null);
else {
Node* n = root;
Node* parent;
while (true) {
if (n.key == key)
return false;
parent = n;
bool goLeft = n.key > key;
n = goLeft ? n.left : n.right;
if (n is null) {
if (goLeft) {
parent.left = new Node(key, parent);
} else {
parent.right = new Node(key, parent);
}
rebalance(parent);
break;
}
}
}
return true;
}
public void deleteKey(in int delKey) pure nothrow @safe @nogc {
if (root is null)
return;
Node* n = root;
Node* parent = root;
Node* delNode = null;
Node* child = root;
while (child !is null) {
parent = n;
n = child;
child = delKey >= n.key ? n.right : n.left;
if (delKey == n.key)
delNode = n;
}
if (delNode !is null) {
delNode.key = n.key;
child = n.left !is null ? n.left : n.right;
if (root.key == delKey) {
root = child;
} else {
if (parent.left is n) {
parent.left = child;
} else {
parent.right = child;
}
rebalance(parent);
}
}
}
private void rebalance(Node* n) pure nothrow @safe @nogc {
setBalance(n);
if (n.balance == -2) {
if (height(n.left.left) >= height(n.left.right))
n = rotateRight(n);
else
n = rotateLeftThenRight(n);
} else if (n.balance == 2) {
if (height(n.right.right) >= height(n.right.left))
n = rotateLeft(n);
else
n = rotateRightThenLeft(n);
}
if (n.parent !is null) {
rebalance(n.parent);
} else {
root = n;
}
}
private Node* rotateLeft(Node* a) pure nothrow @safe @nogc {
Node* b = a.right;
b.parent = a.parent;
a.right = b.left;
if (a.right !is null)
a.right.parent = a;
b.left = a;
a.parent = b;
if (b.parent !is null) {
if (b.parent.right is a) {
b.parent.right = b;
} else {
b.parent.left = b;
}
}
setBalance(a, b);
return b; }
private Node* rotateRight(Node* a) pure nothrow @safe @nogc {
Node* b = a.left;
b.parent = a.parent;
a.left = b.right;
if (a.left !is null)
a.left.parent = a;
b.right = a;
a.parent = b;
if (b.parent !is null) {
if (b.parent.right is a) {
b.parent.right = b;
} else {
b.parent.left = b;
}
}
setBalance(a, b);
return b; }
private Node* rotateLeftThenRight(Node* n) pure nothrow @safe @nogc {
n.left = rotateLeft(n.left);
return rotateRight(n);
}
private Node* rotateRightThenLeft(Node* n) pure nothrow @safe @nogc {
n.right = rotateRight(n.right);
return rotateLeft(n);
}
private int height(in Node* n) const pure nothrow @safe @nogc {
if (n is null)
return -1;
return 1 + max(height(n.left), height(n.right));
}
private void setBalance(Node*[] nodes...) pure nothrow @safe @nogc {
foreach (n; nodes)
n.balance = height(n.right) - height(n.left);
}
public void printBalance() const @safe {
printBalance(root);
}
private void printBalance(in Node* n) const @safe {
if (n !is null) {
printBalance(n.left);
write(n.balance, ' ');
printBalance(n.right);
}
}
}
void main() @safe {
auto tree = new AVLtree();
writeln("Inserting values 1 to 10");
foreach (immutable i; 1 .. 11)
tree.insert(i);
write("Printing balance: ");
tree.printBalance;
}</lang>
- Output:
Inserting values 1 to 10 Printing balance: 0 0 0 1 0 0 0 0 1 0
Go
A package: <lang go>package avl
// AVL tree adapted from Julienne Walker's presentation at // http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx. // This port uses similar indentifier names.
// The Key interface must be supported by data stored in the AVL tree. type Key interface {
Less(Key) bool Eq(Key) bool
}
// Node is a node in an AVL tree. type Node struct {
Data Key // anything comparable with Less and Eq. Balance int // balance factor Link [2]*Node // children, indexed by "direction", 0 or 1.
}
// A little readability function for returning the opposite of a direction, // where a direction is 0 or 1. Go inlines this. // Where JW writes !dir, this code has opp(dir). func opp(dir int) int {
return 1 - dir
}
// single rotation func single(root *Node, dir int) *Node {
save := root.Link[opp(dir)] root.Link[opp(dir)] = save.Link[dir] save.Link[dir] = root return save
}
// double rotation func double(root *Node, dir int) *Node {
save := root.Link[opp(dir)].Link[dir]
root.Link[opp(dir)].Link[dir] = save.Link[opp(dir)] save.Link[opp(dir)] = root.Link[opp(dir)] root.Link[opp(dir)] = save
save = root.Link[opp(dir)] root.Link[opp(dir)] = save.Link[dir] save.Link[dir] = root return save
}
// adjust valance factors after double rotation func adjustBalance(root *Node, dir, bal int) {
n := root.Link[dir]
nn := n.Link[opp(dir)]
switch nn.Balance {
case 0:
root.Balance = 0
n.Balance = 0
case bal:
root.Balance = -bal
n.Balance = 0
default:
root.Balance = 0
n.Balance = bal
}
nn.Balance = 0
}
func insertBalance(root *Node, dir int) *Node {
n := root.Link[dir]
bal := 2*dir - 1
if n.Balance == bal {
root.Balance = 0
n.Balance = 0
return single(root, opp(dir))
}
adjustBalance(root, dir, bal)
return double(root, opp(dir))
}
func insertR(root *Node, data Key) (*Node, bool) {
if root == nil {
return &Node{Data: data}, false
}
dir := 0
if root.Data.Less(data) {
dir = 1
}
var done bool
root.Link[dir], done = insertR(root.Link[dir], data)
if done {
return root, true
}
root.Balance += 2*dir - 1
switch root.Balance {
case 0:
return root, true
case 1, -1:
return root, false
}
return insertBalance(root, dir), true
}
// Insert a node into the AVL tree. // Data is inserted even if other data with the same key already exists. func Insert(tree **Node, data Key) {
*tree, _ = insertR(*tree, data)
}
func removeBalance(root *Node, dir int) (*Node, bool) {
n := root.Link[opp(dir)]
bal := 2*dir - 1
switch n.Balance {
case -bal:
root.Balance = 0
n.Balance = 0
return single(root, dir), false
case bal:
adjustBalance(root, opp(dir), -bal)
return double(root, dir), false
}
root.Balance = -bal
n.Balance = bal
return single(root, dir), true
}
func removeR(root *Node, data Key) (*Node, bool) {
if root == nil {
return nil, false
}
if root.Data.Eq(data) {
switch {
case root.Link[0] == nil:
return root.Link[1], false
case root.Link[1] == nil:
return root.Link[0], false
}
heir := root.Link[0]
for heir.Link[1] != nil {
heir = heir.Link[1]
}
root.Data = heir.Data
data = heir.Data
}
dir := 0
if root.Data.Less(data) {
dir = 1
}
var done bool
root.Link[dir], done = removeR(root.Link[dir], data)
if done {
return root, true
}
root.Balance += 1 - 2*dir
switch root.Balance {
case 1, -1:
return root, true
case 0:
return root, false
}
return removeBalance(root, dir)
}
// Remove a single item from an AVL tree. // If key does not exist, function has no effect. func Remove(tree **Node, data Key) {
*tree, _ = removeR(*tree, data)
}</lang> A demonstration program: <lang go>package main
import (
"encoding/json" "fmt" "log"
"avl"
)
type intKey int
// satisfy avl.Key func (k intKey) Less(k2 avl.Key) bool { return k < k2.(intKey) } func (k intKey) Eq(k2 avl.Key) bool { return k == k2.(intKey) }
// use json for cheap tree visualization func dump(tree *avl.Node) {
b, err := json.MarshalIndent(tree, "", " ")
if err != nil {
log.Fatal(err)
}
fmt.Println(string(b))
}
func main() {
var tree *avl.Node
fmt.Println("Empty tree:")
dump(tree)
fmt.Println("\nInsert test:")
avl.Insert(&tree, intKey(3))
avl.Insert(&tree, intKey(1))
avl.Insert(&tree, intKey(4))
avl.Insert(&tree, intKey(1))
avl.Insert(&tree, intKey(5))
dump(tree)
fmt.Println("\nRemove test:")
avl.Remove(&tree, intKey(3))
avl.Remove(&tree, intKey(1))
dump(tree)
}</lang>
- Output:
Empty tree:
null
Insert test:
{
"Data": 3,
"Balance": 0,
"Link": [
{
"Data": 1,
"Balance": -1,
"Link": [
{
"Data": 1,
"Balance": 0,
"Link": [
null,
null
]
},
null
]
},
{
"Data": 4,
"Balance": 1,
"Link": [
null,
{
"Data": 5,
"Balance": 0,
"Link": [
null,
null
]
}
]
}
]
}
Remove test:
{
"Data": 4,
"Balance": 0,
"Link": [
{
"Data": 1,
"Balance": 0,
"Link": [
null,
null
]
},
{
"Data": 5,
"Balance": 0,
"Link": [
null,
null
]
}
]
}
Haskell
Solution of homework #4 from course http://www.seas.upenn.edu/~cis194/spring13/lectures.html. <lang haskell>data Tree a = Leaf | Node Int (Tree a) a (Tree a)
deriving (Show, Eq)
foldTree :: Ord a => [a] -> Tree a foldTree = foldr insert Leaf
height Leaf = -1 height (Node h _ _ _) = h
depth a b = 1 + (height a `max` height b)
insert :: Ord a => a -> Tree a -> Tree a insert v Leaf = Node 1 Leaf v Leaf insert v t@(Node n left v' right)
| v' < v = rotate $ Node n left v' (insert v right) | v' > v = rotate $ Node n (insert v left) v' right | otherwise = t
max' :: Ord a => Tree a -> Maybe a max' Leaf = Nothing max' (Node _ _ v right) = case right of
Leaf -> Just v
_ -> max' right
delete :: Ord a => a -> Tree a -> Tree a delete _ Leaf = Leaf delete x (Node h left v right)
| x == v = maybe left (\m -> rotate $ Node h left m (delete m right)) (max' right) | x > v = rotate $ Node h left v (delete x right) | x < v = rotate $ Node h (delete x left) v right
rotate :: Tree a -> Tree a rotate Leaf = Leaf -- left left case rotate (Node h (Node lh ll lv lr) v r)
| lh - height r > 1 && height ll - height lr > 0 =
Node lh ll lv (Node (depth r lr) lr v r)
-- right right case rotate (Node h l v (Node rh rl rv rr))
| rh - height l > 1 && height rr - height rl > 0 =
Node rh (Node (depth l rl) l v rl) rv rr
-- left right case rotate (Node h (Node lh ll lv (Node rh rl rv rr)) v r)
| lh - height r > 1 = Node h (Node (rh+1) (Node (lh-1) ll lv rl) rv rr) v r
-- right left case rotate (Node h l v (Node rh (Node lh ll lv lr) rv rr))
| rh - height l > 1 = Node h l v (Node (lh+1) ll lv (Node (rh-1) lr rv rr))
-- re-weighting rotate (Node h l v r) = let (l', r') = (rotate l, rotate r)
in Node (depth l' r') l' v r'
draw :: Show a => Tree a -> String draw t = "\n" ++ draw' t 0 ++ "\n"
where
draw' Leaf _ = []
draw' (Node h l v r) d = draw' r (d+1) ++ node ++ draw' l (d+1)
where
node = padding d ++ show (v, h) ++ "\n"
padding n = replicate (n*4) ' '</lang>
*Main> putStr $ draw $ foldTree [1..15]
(15,0)
(14,1)
(13,0)
(12,2)
(11,0)
(10,1)
(9,0)
(8,3)
(7,0)
(6,1)
(5,0)
(4,2)
(3,0)
(2,1)
(1,0)
Java
This code has been cobbled together from various online examples. It's not easy to find a clear and complete explanation of AVL trees. Textbooks tend to concentrate on red-black trees because of their better efficiency. (AVL trees need to make 2 passes through the tree when inserting and deleting: one down to find the node to operate upon and one up to rebalance the tree.) <lang java>public class AVLtree {
private Node root;
private class Node {
private int key;
private int balance;
private int height;
private Node left, right, parent;
Node(int k, Node p) {
key = k;
parent = p;
}
}
public boolean insert(int key) {
if (root == null)
root = new Node(key, null);
else {
Node n = root;
Node parent;
while (true) {
if (n.key == key)
return false;
parent = n;
boolean goLeft = n.key > key;
n = goLeft ? n.left : n.right;
if (n == null) {
if (goLeft) {
parent.left = new Node(key, parent);
} else {
parent.right = new Node(key, parent);
}
rebalance(parent);
break;
}
}
}
return true;
}
private void delete(Node node){
if(node.left == null && node.right == null){
if(node.parent == null) root = null;
else{
Node parent = node.parent;
if(parent.left == node){
parent.left = null;
}else parent.right = null;
rebalance(parent);
}
return;
}
if(node.left!=null){
Node child = node.left;
while (child.right!=null) child = child.right;
node.key = child.key;
delete(child);
}else{
Node child = node.right;
while (child.left!=null) child = child.left;
node.key = child.key;
delete(child);
}
}
public void delete(int delKey) {
if (root == null)
return;
Node node = root;
Node child = root;
while (child != null) {
node = child;
child = delKey >= node.key ? node.right : node.left;
if (delKey == node.key) {
delete(node);
return;
}
}
}
private void rebalance(Node n) {
setBalance(n);
if (n.balance == -2) {
if (height(n.left.left) >= height(n.left.right))
n = rotateRight(n);
else
n = rotateLeftThenRight(n);
} else if (n.balance == 2) {
if (height(n.right.right) >= height(n.right.left))
n = rotateLeft(n);
else
n = rotateRightThenLeft(n);
}
if (n.parent != null) {
rebalance(n.parent);
} else {
root = n;
}
}
private Node rotateLeft(Node a) {
Node b = a.right;
b.parent = a.parent;
a.right = b.left;
if (a.right != null)
a.right.parent = a;
b.left = a;
a.parent = b;
if (b.parent != null) {
if (b.parent.right == a) {
b.parent.right = b;
} else {
b.parent.left = b;
}
}
setBalance(a, b);
return b; }
private Node rotateRight(Node a) {
Node b = a.left;
b.parent = a.parent;
a.left = b.right;
if (a.left != null)
a.left.parent = a;
b.right = a;
a.parent = b;
if (b.parent != null) {
if (b.parent.right == a) {
b.parent.right = b;
} else {
b.parent.left = b;
}
}
setBalance(a, b);
return b; }
private Node rotateLeftThenRight(Node n) {
n.left = rotateLeft(n.left);
return rotateRight(n);
}
private Node rotateRightThenLeft(Node n) {
n.right = rotateRight(n.right);
return rotateLeft(n);
}
private int height(Node n) {
if (n == null)
return -1;
return n.height;
}
private void setBalance(Node... nodes) {
for (Node n : nodes)
reheight(n);
n.balance = height(n.right) - height(n.left);
}
public void printBalance() {
printBalance(root);
}
private void printBalance(Node n) {
if (n != null) {
printBalance(n.left);
System.out.printf("%s ", n.balance);
printBalance(n.right);
}
}
private void reheight(Node node){
if(node!=null){
node.height=1 + Math.max(height(node.left), height(node.right));
}
}
public static void main(String[] args) {
AVLtree tree = new AVLtree();
System.out.println("Inserting values 1 to 10");
for (int i = 1; i < 10; i++)
tree.insert(i);
System.out.print("Printing balance: ");
tree.printBalance();
}
}</lang>
Inserting values 1 to 10 Printing balance: 0 0 0 1 0 1 0 0 0
More elaborate version
See AVL_tree/Java
Kotlin
<lang scala>// version 1.0.6
class AvlTree {
private var root: Node? = null
private class Node(var key: Int, var parent: Node?) {
var balance: Int = 0
var left : Node? = null
var right: Node? = null
}
fun insert(key: Int): Boolean {
if (root == null)
root = Node(key, null)
else {
var n: Node? = root
var parent: Node
while (true) {
if (n!!.key == key) return false
parent = n
val goLeft = n.key > key
n = if (goLeft) n.left else n.right
if (n == null) {
if (goLeft)
parent.left = Node(key, parent)
else
parent.right = Node(key, parent)
rebalance(parent)
break
}
}
}
return true
}
fun delete(delKey: Int) {
if (root == null) return
var n: Node? = root
var parent: Node? = root
var delNode: Node? = null
var child: Node? = root
while (child != null) {
parent = n
n = child
child = if (delKey >= n.key) n.right else n.left
if (delKey == n.key) delNode = n
}
if (delNode != null) {
delNode.key = n!!.key
child = if (n.left != null) n.left else n.right
if (root!!.key == delKey)
root = child
else {
if (parent!!.left == n)
parent.left = child
else
parent.right = child
rebalance(parent)
}
}
}
private fun rebalance(n: Node) {
setBalance(n)
var nn = n
if (nn.balance == -2)
if (height(nn.left!!.left) >= height(nn.left!!.right))
nn = rotateRight(nn)
else
nn = rotateLeftThenRight(nn)
else if (nn.balance == 2)
if (height(nn.right!!.right) >= height(nn.right!!.left))
nn = rotateLeft(nn)
else
nn = rotateRightThenLeft(nn)
if (nn.parent != null) rebalance(nn.parent!!)
else root = nn
}
private fun rotateLeft(a: Node): Node {
val b: Node? = a.right
b!!.parent = a.parent
a.right = b.left
if (a.right != null) a.right!!.parent = a
b.left = a
a.parent = b
if (b.parent != null) {
if (b.parent!!.right == a)
b.parent!!.right = b
else
b.parent!!.left = b
}
setBalance(a, b)
return b
}
private fun rotateRight(a: Node): Node {
val b: Node? = a.left
b!!.parent = a.parent
a.left = b.right
if (a.left != null) a.left!!.parent = a
b.right = a
a.parent = b
if (b.parent != null) {
if (b.parent!!.right == a)
b.parent!!.right = b
else
b.parent!!.left = b;
}
setBalance(a, b)
return b
}
private fun rotateLeftThenRight(n: Node): Node {
n.left = rotateLeft(n.left!!)
return rotateRight(n)
}
private fun rotateRightThenLeft(n: Node): Node {
n.right = rotateRight(n.right!!)
return rotateLeft(n)
}
private fun height(n: Node?): Int {
if (n == null) return -1
return 1 + Math.max(height(n.left), height(n.right))
}
private fun setBalance(vararg nodes: Node) {
for (n in nodes) n.balance = height(n.right) - height(n.left)
}
public fun printKey() {
printKey(root)
println()
}
private fun printKey(n: Node?) {
if (n != null) {
printKey(n.left)
print("${n.key} ")
printKey(n.right)
}
}
public fun printBalance() {
printBalance(root)
println()
}
private fun printBalance(n: Node?) {
if (n != null) {
printBalance(n.left)
print("${n.balance} ")
printBalance(n.right)
}
}
}
fun main(args: Array<String>) {
val tree = AvlTree()
println("Inserting values 1 to 10")
for (i in 1..10) tree.insert(i)
print("Printing key : ")
tree.printKey()
print("Printing balance : ")
tree.printBalance()
}</lang>
- Output:
Inserting values 1 to 10 Printing key : 1 2 3 4 5 6 7 8 9 10 Printing balance : 0 0 0 1 0 0 0 0 1 0
Objective-C
<lang Objective-C> @implementation AVLTree
-(BOOL)insertWithKey:(NSInteger)key {
if (self.root == nil) {
self.root = [[AVLTreeNode alloc]initWithKey:key andParent:nil];
} else {
AVLTreeNode *n = self.root;
AVLTreeNode *parent;
while (true) {
if (n.key == key) {
return false;
}
parent = n;
BOOL goLeft = n.key > key;
n = goLeft ? n.left : n.right;
if (n == nil) {
if (goLeft) {
parent.left = [[AVLTreeNode alloc]initWithKey:key andParent:parent];
} else {
parent.right = [[AVLTreeNode alloc]initWithKey:key andParent:parent];
}
[self rebalanceStartingAtNode:parent];
break;
}
}
}
return true;
}
-(void)rebalanceStartingAtNode:(AVLTreeNode*)n {
[self setBalance:@[n]];
if (n.balance == -2) {
if ([self height:(n.left.left)] >= [self height:n.left.right]) {
n = [self rotateRight:n];
} else {
n = [self rotateLeftThenRight:n];
}
} else if (n.balance == 2) {
if ([self height:n.right.right] >= [self height:n.right.left]) {
n = [self rotateLeft:n];
} else {
n = [self rotateRightThenLeft:n];
}
}
if (n.parent != nil) {
[self rebalanceStartingAtNode:n.parent];
} else {
self.root = n;
}
}
-(AVLTreeNode*)rotateRight:(AVLTreeNode*)a {
AVLTreeNode *b = a.left;
b.parent = a.parent;
a.left = b.right;
if (a.left != nil) {
a.left.parent = a;
}
b.right = a;
a.parent = b;
if (b.parent != nil) {
if (b.parent.right == a) {
b.parent.right = b;
} else {
b.parent.left = b;
}
}
[self setBalance:@[a,b]];
return b;
}
-(AVLTreeNode*)rotateLeftThenRight:(AVLTreeNode*)n {
n.left = [self rotateLeft:n.left]; return [self rotateRight:n];
}
-(AVLTreeNode*)rotateRightThenLeft:(AVLTreeNode*)n {
n.right = [self rotateRight:n.right]; return [self rotateLeft:n];
}
-(AVLTreeNode*)rotateLeft:(AVLTreeNode*)a {
//set a's right node as b
AVLTreeNode* b = a.right;
//set b's parent as a's parent (which could be nil)
b.parent = a.parent;
//in case b had a left child transfer it to a
a.right = b.left;
// after changing a's reference to the right child, make sure the parent is set too
if (a.right != nil) {
a.right.parent = a;
}
// switch a over to the left to be b's left child
b.left = a;
a.parent = b;
if (b.parent != nil) {
if (b.parent.right == a) {
b.parent.right = b;
} else {
b.parent.right = b;
}
}
[self setBalance:@[a,b]];
return b;
}
-(void) setBalance:(NSArray*)nodesArray {
for (AVLTreeNode* n in nodesArray) {
n.balance = [self height:n.right] - [self height:n.left];
}
}
-(int)height:(AVLTreeNode*)n {
if (n == nil) {
return -1;
}
return 1 + MAX([self height:n.left], [self height:n.right]);
}
-(void)printKey:(AVLTreeNode*)n {
if (n != nil) {
[self printKey:n.left];
NSLog(@"%ld", n.key);
[self printKey:n.right];
}
}
-(void)printBalance:(AVLTreeNode*)n {
if (n != nil) {
[self printBalance:n.left];
NSLog(@"%ld", n.balance);
[self printBalance:n.right];
}
} @end -- test
int main(int argc, const char * argv[]) {
@autoreleasepool {
AVLTree *tree = [AVLTree new];
NSLog(@"inserting values 1 to 6");
[tree insertWithKey:1];
[tree insertWithKey:2];
[tree insertWithKey:3];
[tree insertWithKey:4];
[tree insertWithKey:5];
[tree insertWithKey:6];
NSLog(@"printing balance: ");
[tree printBalance:tree.root];
NSLog(@"printing key: ");
[tree printKey:tree.root];
}
return 0;
}
</lang>
- Output:
inserting values 1 to 6 printing balance: 0 0 0 0 1 0 printing key: 1 2 3 4 5 6
Phix
Translated from the C version at http://www.geeksforgeeks.org/avl-tree-set-2-deletion
The standard distribution includes demo\rosetta\AVL_tree.exw, which contains a slightly longer but perhaps more readable version,
with a command line equivalent of https://www.cs.usfca.edu/~galles/visualization/AVLtree.html as well as a simple tree structure
display routine and additional verification code (both modelled on the C version found on this page)
<lang Phix>enum KEY = 0,
LEFT,
HEIGHT, -- (NB +/-1 gives LEFT or RIGHT)
RIGHT
sequence tree = {} integer freelist = 0
function newNode(object key) integer node
if freelist=0 then
node = length(tree)+1
tree &= {key,NULL,1,NULL}
else
node = freelist
freelist = tree[freelist]
tree[node+KEY..node+RIGHT] = {key,NULL,1,NULL}
end if
return node
end function
function height(integer node)
return iff(node=NULL?0:tree[node+HEIGHT])
end function
procedure setHeight(integer node)
tree[node+HEIGHT] = max(height(tree[node+LEFT]), height(tree[node+RIGHT]))+1
end procedure
function rotate(integer node, integer direction) integer idirection = LEFT+RIGHT-direction integer pivot = tree[node+idirection]
{tree[pivot+direction],tree[node+idirection]} = {node,tree[pivot+direction]}
setHeight(node)
setHeight(pivot)
return pivot
end function
function getBalance(integer N)
return iff(N==NULL ? 0 : height(tree[N+LEFT])-height(tree[N+RIGHT]))
end function
function insertNode(integer node, object key)
if node==NULL then
return newNode(key)
end if
integer c = compare(key,tree[node+KEY])
if c!=0 then
integer direction = HEIGHT+c -- LEFT or RIGHT
tree[node+direction] = insertNode(tree[node+direction], key)
setHeight(node)
integer balance = trunc(getBalance(node)/2) -- +/-1 (or 0)
if balance then
direction = HEIGHT-balance -- LEFT or RIGHT
c = compare(key,tree[tree[node+direction]+KEY])
if c=balance then
tree[node+direction] = rotate(tree[node+direction],direction)
end if
if c!=0 then
node = rotate(node,LEFT+RIGHT-direction)
end if
end if
end if
return node
end function
function minValueNode(integer node)
while 1 do
integer next = tree[node+LEFT]
if next=NULL then exit end if
node = next
end while
return node
end function
function deleteNode(integer root, object key) integer c
if root=NULL then return root end if
c = compare(key,tree[root+KEY])
if c=-1 then
tree[root+LEFT] = deleteNode(tree[root+LEFT], key)
elsif c=+1 then
tree[root+RIGHT] = deleteNode(tree[root+RIGHT], key)
elsif tree[root+LEFT]==NULL
or tree[root+RIGHT]==NULL then
integer temp = iff(tree[root+LEFT] ? tree[root+LEFT] : tree[root+RIGHT])
if temp==NULL then -- No child case
{temp,root} = {root,NULL}
else -- One child case
tree[root+KEY..root+RIGHT] = tree[temp+KEY..temp+RIGHT]
end if
tree[temp+KEY] = freelist
freelist = temp
else -- Two child case
integer temp = minValueNode(tree[root+RIGHT])
tree[root+KEY] = tree[temp+KEY]
tree[root+RIGHT] = deleteNode(tree[root+RIGHT], tree[temp+KEY])
end if
if root=NULL then return root end if
setHeight(root)
integer balance = trunc(getBalance(root)/2)
if balance then
integer direction = HEIGHT-balance
c = compare(getBalance(tree[root+direction]),0)
if c=-balance then
tree[root+direction] = rotate(tree[root+direction],direction)
end if
root = rotate(root,LEFT+RIGHT-direction)
end if
return root
end function
procedure inOrder(integer node)
if node!=NULL then
inOrder(tree[node+LEFT])
printf(1, "%d ", tree[node+KEY])
inOrder(tree[node+RIGHT])
end if
end procedure
integer root = NULL sequence test = shuffle(tagset(50003))
for i=1 to length(test) do
root = insertNode(root,test[i])
end for
test = shuffle(tagset(50000))
for i=1 to length(test) do
root = deleteNode(root,test[i])
end for
inOrder(root)</lang>
- Output:
50001 50002 50003
Lua
<lang Lua>AVL={balance=0} AVL.__mt={__index = AVL}
function AVL:new(list)
local o={}
setmetatable(o, AVL.__mt)
for _,v in ipairs(list or {}) do
o=o:insert(v)
end
return o
end
function AVL:rebalance()
local rotated=false
if self.balance>1 then
if self.right.balance<0 then
self.right, self.right.left.right, self.right.left = self.right.left, self.right, self.right.left.right
self.right.right.balance=self.right.balance>-1 and 0 or 1
self.right.balance=self.right.balance>0 and 2 or 1
end
self, self.right.left, self.right = self.right, self, self.right.left
self.left.balance=1-self.balance
self.balance=self.balance==0 and -1 or 0
rotated=true
elseif self.balance<-1 then
if self.left.balance>0 then
self.left, self.left.right.left, self.left.right = self.left.right, self.left, self.left.right.left
self.left.left.balance=self.left.balance<1 and 0 or -1
self.left.balance=self.left.balance<0 and -2 or -1
end
self, self.left.right, self.left = self.left, self, self.left.right
self.right.balance=-1-self.balance
self.balance=self.balance==0 and 1 or 0
rotated=true
end
return self,rotated
end
function AVL:insert(v)
if not self.value then self.value=v self.balance=0 return self,1 end local grow if v==self.value then return self,0 elseif v<self.value then if not self.left then self.left=self:new() end self.left,grow=self.left:insert(v) self.balance=self.balance-grow else if not self.right then self.right=self:new() end self.right,grow=self.right:insert(v) self.balance=self.balance+grow end self,rotated=self:rebalance() return self, (rotated or self.balance==0) and 0 or grow
end
function AVL:delete_move(dir,other,mul)
if self[dir] then local sb2,v self[dir], sb2, v=self[dir]:delete_move(dir,other,mul) self.balance=self.balance+sb2*mul self,sb2=self:rebalance() return self,(sb2 or self.balance==0) and -1 or 0,v else return self[other],-1,self.value end
end
function AVL:delete(v,isSubtree)
local grow=0
if v==self.value then
local v
if self.balance>0 then
self.right,grow,v=self.right:delete_move("left","right",-1)
elseif self.left then
self.left,grow,v=self.left:delete_move("right","left",1)
grow=-grow
else
return not isSubtree and AVL:new(),-1
end
self.value=v
self.balance=self.balance+grow
elseif v<self.value and self.left then
self.left,grow=self.left:delete(v,true)
self.balance=self.balance-grow
elseif v>self.value and self.right then
self.right,grow=self.right:delete(v,true)
self.balance=self.balance+grow
else
return self,0
end
self,rotated=self:rebalance()
return self, grow~=0 and (rotated or self.balance==0) and -1 or 0
end
-- output functions
function AVL:toList(list)
if not self.value then return {} end
list=list or {}
if self.left then self.left:toList(list) end
list[#list+1]=self.value
if self.right then self.right:toList(list) end
return list
end
function AVL:dump(depth)
if not self.value then return end
depth=depth or 0
if self.right then self.right:dump(depth+1) end
print(string.rep(" ",depth)..self.value.." ("..self.balance..")")
if self.left then self.left:dump(depth+1) end
end
-- test
local test=AVL:new{1,10,5,15,20,3,5,14,7,13,2,8,3,4,5,10,9,8,7}
test:dump() print("\ninsert 17:") test=test:insert(17) test:dump() print("\ndelete 10:") test=test:delete(10) test:dump() print("\nlist:") print(unpack(test:toList())) </lang>
- Output:
20 (0)
15 (1)
14 (1)
13 (0)
10 (-1)
9 (0)
8 (0)
7 (0)
5 (-1)
4 (0)
3 (1)
2 (1)
1 (0)
insert 17:
20 (0)
17 (0)
15 (0)
14 (1)
13 (0)
10 (-1)
9 (0)
8 (0)
7 (0)
5 (-1)
4 (0)
3 (1)
2 (1)
1 (0)
delete 10:
20 (0)
17 (0)
15 (0)
14 (1)
13 (0)
9 (-1)
8 (-1)
7 (0)
5 (-1)
4 (0)
3 (1)
2 (1)
1 (0)
list:
1 2 3 4 5 7 8 9 13 14 15 17 20
Sidef
<lang ruby>class AVLtree {
has root = nil
struct Node {
Number key,
Number balance = 0,
Node left = nil,
Node right = nil,
Node parent = nil,
}
method insert(key) {
if (root == nil) {
root = Node(key)
return true
}
var n = root
var parent = nil
loop {
if (n.key == key) {
return false
}
parent = n
var goLeft = (n.key > key)
n = (goLeft ? n.left : n.right)
if (n == nil) {
var tn = Node(key, parent: parent)
if (goLeft) {
parent.left = tn
}
else {
parent.right = tn
}
self.rebalance(parent)
break
}
}
return true }
method delete_key(delKey) {
if (root == nil) { return }
var n = root
var parent = root
var delNode = nil
var child = root
while (child != nil) {
parent = n
n = child
child = (delKey >= n.key ? n.right : n.left)
if (delKey == n.key) {
delNode = n
}
}
if (delNode != nil) {
delNode.key = n.key
child = (n.left != nil ? n.left : n.right)
if (root.key == delKey) {
root = child
}
else {
if (parent.left == n) {
parent.left = child
}
else {
parent.right = child
}
self.rebalance(parent)
}
}
}
method rebalance(n) {
if (n == nil) { return }
self.setBalance(n)
given (n.balance) {
when (-2) {
if (self.height(n.left.left) >= self.height(n.left.right)) {
n = self.rotate(n, :right)
}
else {
n = self.rotate_twice(n, :left, :right)
}
}
when (2) {
if (self.height(n.right.right) >= self.height(n.right.left)) {
n = self.rotate(n, :left)
}
else {
n = self.rotate_twice(n, :right, :left)
}
}
}
if (n.parent != nil) {
self.rebalance(n.parent)
}
else {
root = n
}
}
method rotate(a, dir) {
var b = (dir == :left ? a.right : a.left)
b.parent = a.parent
(dir == :left) ? (a.right = b.left)
: (a.left = b.right)
if (a.right != nil) {
a.right.parent = a
}
b.$dir = a
a.parent = b
if (b.parent != nil) {
if (b.parent.right == a) {
b.parent.right = b
}
else {
b.parent.left = b
}
}
self.setBalance(a, b)
return b
}
method rotate_twice(n, dir1, dir2) {
n.left = self.rotate(n.left, dir1)
self.rotate(n, dir2)
}
method height(n) {
if (n == nil) { return -1 }
1 + Math.max(self.height(n.left), self.height(n.right))
}
method setBalance(*nodes) {
nodes.each { |n|
n.balance = (self.height(n.right) - self.height(n.left))
}
}
method printBalance {
self.printBalance(root)
}
method printBalance(n) {
if (n != nil) {
self.printBalance(n.left)
print(n.balance, ' ')
self.printBalance(n.right)
}
}
}
var tree = AVLtree()
say "Inserting values 1 to 10" 10.times { |i| tree.insert(i) } print "Printing balance: " tree.printBalance</lang>
- Output:
Inserting values 1 to 10 Printing balance: 0 0 0 1 0 0 0 0 1 0
Simula
<lang simula>CLASS AVL; BEGIN
! AVL TREE ADAPTED FROM JULIENNE WALKER'S PRESENTATION AT ; ! HTTP://ETERNALLYCONFUZZLED.COM/TUTS/DATASTRUCTURES/JSW_TUT_AVL.ASPX. ; ! THIS PORT USES SIMILAR INDENTIFIER NAMES. ; ! THE KEY INTERFACE MUST BE SUPPORTED BY DATA STORED IN THE AVL TREE. ; CLASS KEY; VIRTUAL: PROCEDURE LESS IS BOOLEAN PROCEDURE LESS (K); REF(KEY) K;; PROCEDURE EQUAL IS BOOLEAN PROCEDURE EQUAL(K); REF(KEY) K;; BEGIN END KEY; ! NODE IS A NODE IN AN AVL TREE. ; CLASS NODE(DATA); REF(KEY) DATA; ! ANYTHING COMPARABLE WITH LESS AND EQUAL. ; BEGIN INTEGER BALANCE; ! BALANCE FACTOR ; REF(NODE) ARRAY LINK(0:1); ! CHILDREN, INDEXED BY "DIRECTION", 0 OR 1. ; END NODE; ! A LITTLE READABILITY FUNCTION FOR RETURNING THE OPPOSITE OF A DIRECTION, ; ! WHERE A DIRECTION IS 0 OR 1. GO INLINES THIS. ; ! WHERE JW WRITES !DIR, THIS CODE HAS OPP(DIR). ; INTEGER PROCEDURE OPP(DIR); INTEGER DIR; BEGIN OPP := 1 - DIR; END OPP; ! SINGLE ROTATION ; REF(NODE) PROCEDURE SINGLE(ROOT, DIR); REF(NODE) ROOT; INTEGER DIR; BEGIN REF(NODE) SAVE; SAVE :- ROOT.LINK(OPP(DIR)); ROOT.LINK(OPP(DIR)) :- SAVE.LINK(DIR); SAVE.LINK(DIR) :- ROOT; SINGLE :- SAVE; END SINGLE; ! DOUBLE ROTATION ; REF(NODE) PROCEDURE DOUBLE(ROOT, DIR); REF(NODE) ROOT; INTEGER DIR; BEGIN REF(NODE) SAVE; SAVE :- ROOT.LINK(OPP(DIR)).LINK(DIR); ROOT.LINK(OPP(DIR)).LINK(DIR) :- SAVE.LINK(OPP(DIR)); SAVE.LINK(OPP(DIR)) :- ROOT.LINK(OPP(DIR)); ROOT.LINK(OPP(DIR)) :- SAVE; SAVE :- ROOT.LINK(OPP(DIR)); ROOT.LINK(OPP(DIR)) :- SAVE.LINK(DIR); SAVE.LINK(DIR) :- ROOT; DOUBLE :- SAVE; END DOUBLE; ! ADJUST VALANCE FACTORS AFTER DOUBLE ROTATION ; PROCEDURE ADJUSTBALANCE(ROOT, DIR, BAL); REF(NODE) ROOT; INTEGER DIR, BAL; BEGIN REF(NODE) N, NN; N :- ROOT.LINK(DIR); NN :- N.LINK(OPP(DIR)); IF NN.BALANCE = 0 THEN BEGIN ROOT.BALANCE := 0; N.BALANCE := 0; END ELSE IF NN.BALANCE = BAL THEN BEGIN ROOT.BALANCE := -BAL; N.BALANCE := 0; END ELSE BEGIN ROOT.BALANCE := 0; N.BALANCE := BAL; END; NN.BALANCE := 0; END ADJUSTBALANCE; REF(NODE) PROCEDURE INSERTBALANCE(ROOT, DIR); REF(NODE) ROOT; INTEGER DIR; BEGIN REF(NODE) N; INTEGER BAL; N :- ROOT.LINK(DIR); BAL := 2*DIR - 1; IF N.BALANCE = BAL THEN BEGIN ROOT.BALANCE := 0; N.BALANCE := 0; INSERTBALANCE :- SINGLE(ROOT, OPP(DIR)); END ELSE BEGIN ADJUSTBALANCE(ROOT, DIR, BAL); INSERTBALANCE :- DOUBLE(ROOT, OPP(DIR)); END; END INSERTBALANCE; CLASS TUPLE(N,B); REF(NODE) N; BOOLEAN B;; REF(TUPLE) PROCEDURE INSERTR(ROOT, DATA); REF(NODE) ROOT; REF(KEY) DATA; BEGIN IF ROOT == NONE THEN INSERTR :- NEW TUPLE(NEW NODE(DATA), FALSE) ELSE BEGIN REF(TUPLE) T; BOOLEAN DONE; INTEGER DIR; DIR := 0; IF ROOT.DATA.LESS(DATA) THEN DIR := 1; T :- INSERTR(ROOT.LINK(DIR), DATA); ROOT.LINK(DIR) :- T.N; DONE := T.B; IF DONE THEN INSERTR :- NEW TUPLE(ROOT, TRUE) ELSE BEGIN ROOT.BALANCE := ROOT.BALANCE + 2*DIR - 1; IF ROOT.BALANCE = 0 THEN INSERTR :- NEW TUPLE(ROOT, TRUE) ELSE IF ROOT.BALANCE = 1 OR ROOT.BALANCE = -1 THEN INSERTR :- NEW TUPLE(ROOT, FALSE) ELSE INSERTR :- NEW TUPLE(INSERTBALANCE(ROOT, DIR), TRUE); END; END; END INSERTR; ! INSERT A NODE INTO THE AVL TREE. ; ! DATA IS INSERTED EVEN IF OTHER DATA WITH THE SAME KEY ALREADY EXISTS. ; PROCEDURE INSERT(TREE, DATA); NAME TREE; REF(NODE) TREE; REF(KEY) DATA; BEGIN REF(TUPLE) T; T :- INSERTR(TREE, DATA); TREE :- T.N; END INSERT; REF(TUPLE) PROCEDURE REMOVEBALANCE(ROOT, DIR); REF(NODE) ROOT; INTEGER DIR; BEGIN REF(NODE) N; INTEGER BAL; N :- ROOT.LINK(OPP(DIR)); BAL := 2*DIR - 1; IF N.BALANCE = -BAL THEN BEGIN ROOT.BALANCE := 0; N.BALANCE := 0; REMOVEBALANCE :- NEW TUPLE(SINGLE(ROOT, DIR), FALSE); END ELSE IF N.BALANCE = BAL THEN BEGIN ADJUSTBALANCE(ROOT, OPP(DIR), -BAL); REMOVEBALANCE :- NEW TUPLE(DOUBLE(ROOT, DIR), FALSE); END ELSE BEGIN ROOT.BALANCE := -BAL; N.BALANCE := BAL; REMOVEBALANCE :- NEW TUPLE(SINGLE(ROOT, DIR), TRUE); END END REMOVEBALANCE; REF(TUPLE) PROCEDURE REMOVER(ROOT, DATA); REF(NODE) ROOT; REF(KEY) DATA; BEGIN INTEGER DIR; BOOLEAN DONE; REF(TUPLE) T;
IF ROOT == NONE THEN
REMOVER :- NEW TUPLE(NONE, FALSE)
ELSE
IF ROOT.DATA.EQUAL(DATA) THEN
BEGIN
IF ROOT.LINK(0) == NONE THEN
BEGIN
REMOVER :- NEW TUPLE(ROOT.LINK(1), FALSE);
GOTO L;
END
ELSE IF ROOT.LINK(1) == NONE THEN
BEGIN
REMOVER :- NEW TUPLE(ROOT.LINK(0), FALSE);
GOTO L;
END
ELSE
BEGIN REF(NODE) HEIR;
HEIR :- ROOT.LINK(0);
WHILE HEIR.LINK(1) =/= NONE DO
HEIR :- HEIR.LINK(1);
ROOT.DATA :- HEIR.DATA;
DATA :- HEIR.DATA;
END;
END;
DIR := 0;
IF ROOT.DATA.LESS(DATA) THEN
DIR := 1;
T :- REMOVER(ROOT.LINK(DIR), DATA); ROOT.LINK(DIR) :- T.N; DONE := T.B;
IF DONE THEN
BEGIN
REMOVER :- NEW TUPLE(ROOT, TRUE);
GOTO L;
END;
ROOT.BALANCE := ROOT.BALANCE + 1 - 2*DIR;
IF ROOT.BALANCE = 1 OR ROOT.BALANCE = -1 THEN
REMOVER :- NEW TUPLE(ROOT, TRUE)
ELSE IF ROOT.BALANCE = 0 THEN
REMOVER :- NEW TUPLE(ROOT, FALSE)
ELSE
REMOVER :- REMOVEBALANCE(ROOT, DIR);
L:
END REMOVER;
! REMOVE A SINGLE ITEM FROM AN AVL TREE. ;
! IF KEY DOES NOT EXIST, FUNCTION HAS NO EFFECT. ;
PROCEDURE REMOVE(TREE, DATA); NAME TREE; REF(NODE) TREE; REF(KEY) DATA;
BEGIN REF(TUPLE) T;
T :- REMOVER(TREE, DATA);
TREE :- T.N;
END REMOVEM;
END.</lang> A demonstration program: <lang simula>EXTERNAL CLASS AVL;
AVL BEGIN
KEY CLASS INTEGERKEY(I); INTEGER I;
BEGIN
BOOLEAN PROCEDURE LESS (K); REF(KEY) K; LESS := I < K QUA INTEGERKEY.I;
BOOLEAN PROCEDURE EQUAL(K); REF(KEY) K; EQUAL := I = K QUA INTEGERKEY.I;
END INTEGERKEY;
PROCEDURE DUMP(ROOT); REF(NODE) ROOT;
BEGIN
IF ROOT =/= NONE THEN
BEGIN
DUMP(ROOT.LINK(0));
OUTINT(ROOT.DATA QUA INTEGERKEY.I, 0); OUTTEXT(" ");
DUMP(ROOT.LINK(1));
END
END DUMP;
INTEGER I;
REF(NODE) TREE;
OUTTEXT("Empty tree: "); DUMP(TREE); OUTIMAGE;
FOR I := 3, 1, 4, 1, 5 DO
BEGIN OUTTEXT("Insert "); OUTINT(I, 0); OUTTEXT(": ");
INSERT(TREE, NEW INTEGERKEY(I)); DUMP(TREE); OUTIMAGE;
END;
FOR I := 3, 1 DO
BEGIN OUTTEXT("Remove "); OUTINT(I, 0); OUTTEXT(": ");
REMOVE(TREE, NEW INTEGERKEY(I)); DUMP(TREE); OUTIMAGE;
END;
END.</lang>
- Output:
Empty tree: Insert 3: 3 Insert 1: 1 3 Insert 4: 1 3 4 Insert 1: 1 1 3 4 Insert 5: 1 1 3 4 5 Remove 3: 1 1 4 5 Remove 1: 1 4 5
Tcl
Note that in general, you would not normally write a tree directly in Tcl when writing code that required an = map, but would rather use either an array variable or a dictionary value (which are internally implemented using a high-performance hash table engine).
<lang tcl>package require TclOO
namespace eval AVL {
# Class for the overall tree; manages real public API
oo::class create Tree {
variable root nil class constructor Template:NodeClass AVL::Node { set class [oo::class create Node [list superclass $nodeClass]]
# Create a nil instance to act as a leaf sentinel set nil [my NewNode ""] set root [$nil ref]
# Make nil be special oo::objdefine $nil { method height {} {return 0} method key {} {error "no key possible"} method value {} {error "no value possible"} method destroy {} { # Do nothing (doesn't prohibit destruction entirely) } method print {indent increment} { # Do nothing } } }
# How to actually manufacture a new node method NewNode {key} { if {![info exists nil]} {set nil ""} $class new $key $nil [list [namespace current]::my NewNode] }
# Create a new node in the tree and return it method insert {key} { set node [my NewNode $key] if {$root eq $nil} { set root $node } else { $root insert $node } return $node }
# Find the node for a particular key method lookup {key} { for {set node $root} {$node ne $nil} {} { if {[$node key] == $key} { return $node } elseif {[$node key] > $key} { set node [$node left] } else { set node [$node right] } } error "no such node" }
# Print a tree out, one node per line method print {{indent 0} {increment 1}} { $root print $indent $increment return }
}
# Class of an individual node; may be subclassed
oo::class create Node {
variable key value left right 0 refcount newNode constructor {n nil instanceFactory} { set newNode $instanceFactory set 0 [expr {$nil eq "" ? [self] : $nil}] set key $n set value {} set left [set right $0] set refcount 0 } method ref {} { incr refcount return [self] } method destroy {} { if {[incr refcount -1] < 1} next } method New {key value} { set n [{*}$newNode $key] $n setValue $value return $n }
# Getters method key {} {return $key} method value {} {return $value} method left {} {return $left} method right {args} {return $right}
# Setters method setValue {newValue} { set value $newValue } method setLeft {node} { # Non-trivial because of reference management $node ref $left destroy set left $node return } method setRight {node} { # Non-trivial because of reference management $node ref $right destroy set right $node return }
# Print a node and its descendents method print {indent increment} { puts [format "%s%s => %s" [string repeat " " $indent] $key $value] incr indent $increment $left print $indent $increment $right print $indent $increment }
method height {} { return [expr {max([$left height], [$right height]) + 1}] } method balanceFactor {} { expr {[$left height] - [$right height]} }
method insert {node} { # Simple insertion if {$key > [$node key]} { if {$left eq $0} { my setLeft $node } else { $left insert $node } } else { if {$right eq $0} { my setRight $node } else { $right insert $node } }
# Rebalance this node if {[my balanceFactor] > 1} { if {[$left balanceFactor] < 0} { $left rotateLeft } my rotateRight } elseif {[my balanceFactor] < -1} { if {[$right balanceFactor] > 0} { $right rotateRight } my rotateLeft } }
# AVL Rotations method rotateLeft {} { set new [my New $key $value] set key [$right key] set value [$right value] $new setLeft $left $new setRight [$right left] my setLeft $new my setRight [$right right] }
method rotateRight {} { set new [my New $key $value] set key [$left key] set value [$left value] $new setLeft [$left right] $new setRight $right my setLeft [$left left] my setRight $new }
}
}</lang> Demonstrating: <lang tcl># Create an AVL tree AVL::Tree create tree
- Populate it with some semi-random data
for {set i 33} {$i < 127} {incr i} {
[tree insert $i] setValue \
[string repeat [format %c $i] [expr {1+int(rand()*5)}]] }
- Print it out
tree print
- Look up a few values in the tree
for {set i 0} {$i < 10} {incr i} {
set k [expr {33+int((127-33)*rand())}]
puts $k=>[[tree lookup $k] value]
}
- Destroy the tree and all its nodes
tree destroy</lang>
- Output:
64 => @@@
48 => 000
40 => (((((
36 => $
34 => """
33 => !!
35 => #####
38 => &&&
37 => %
39 => ''''
44 => ,
42 => **
41 => )))
43 => +++++
46 => .
45 => --
47 => ////
56 => 888
52 => 444
50 => 22222
49 => 1111
51 => 333
54 => 6
53 => 555
55 => 77
60 => <<<<
58 => ::::
57 => 99999
59 => ;
62 => >>>
61 => ===
63 => ??
96 => ``
80 => PPPPP
72 => HHHH
68 => DDD
66 => BBBB
65 => A
67 => CCC
70 => FFF
69 => EEEE
71 => GGG
76 => LL
74 => JJ
73 => III
75 => KKKK
78 => N
77 => MMMMM
79 => OOOOO
88 => XXX
84 => TTTT
82 => R
81 => QQQQ
83 => SSSS
86 => V
85 => UUU
87 => WWW
92 => \\\
90 => Z
89 => YYYYY
91 => [
94 => ^^^^^
93 => ]]]]
95 => _____
112 => pppp
104 => hh
100 => d
98 => bb
97 => aaa
99 => cccc
102 => ff
101 => eeee
103 => gggg
108 => lll
106 => j
105 => iii
107 => kkkkk
110 => nn
109 => m
111 => o
120 => x
116 => ttt
114 => rrrrr
113 => qqqqq
115 => s
118 => vvv
117 => uuuu
119 => wwww
124 => ||||
122 => zzzz
121 => y
123 => {{{
125 => }}}}
126 => ~~~~
53=>555
55=>77
60=><<<<
100=>d
99=>cccc
93=>]]]]
57=>99999
56=>888
47=>////
39=>''''
TypeScript
For use within a project, consider adding "export default" to AVLtree class declaration. <lang JavaScript>/** A single node in an AVL tree */ class AVLnode <T> {
balance: number left: AVLnode<T> right: AVLnode<T>
constructor(public key: T, public parent: AVLnode<T> = null) {
this.balance = 0
this.left = null
this.right = null
}
}
/** The balanced AVL tree */ class AVLtree <T> {
// public members organized here
constructor() {
this.root = null
}
insert(key: T): boolean {
if (this.root === null) {
this.root = new AVLnode<T>(key)
} else {
let n: AVLnode<T> = this.root,
parent: AVLnode<T> = null
while (true) {
if(n.key === key) {
return false
}
parent = n
let goLeft: boolean = n.key > key
n = goLeft ? n.left : n.right
if (n === null) {
if (goLeft) {
parent.left = new AVLnode<T>(key, parent)
} else {
parent.right = new AVLnode<T>(key, parent)
}
this.rebalance(parent)
break
}
}
}
return true }
deleteKey(delKey: T): void {
if (this.root === null) {
return
}
let n: AVLnode<T> = this.root,
parent: AVLnode<T> = this.root,
delNode: AVLnode<T> = null,
child: AVLnode<T> = this.root
while (child !== null) {
parent = n
n = child
child = delKey >= n.key ? n.right : n.left
if (delKey === n.key) {
delNode = n
}
}
if (delNode !== null) {
delNode.key = n.key
child = n.left !== null ? n.left : n.right
if (this.root.key === delKey) {
this.root = child
} else {
if (parent.left === n) {
parent.left = child
} else {
parent.right = child
}
this.rebalance(parent)
}
}
}
treeBalanceString(n: AVLnode<T> = this.root): string {
if (n !== null) {
return `${this.treeBalanceString(n.left)} ${n.balance} ${this.treeBalanceString(n.right)}`
}
return ""
}
toString(n: AVLnode<T> = this.root): string {
if (n !== null) {
return `${this.toString(n.left)} ${n.key} ${this.toString(n.right)}`
}
return ""
}
// private members organized here private root: AVLnode<T>
private rotateLeft(a: AVLnode<T>): AVLnode<T> {
let b: AVLnode<T> = a.right
b.parent = a.parent
a.right = b.left
if (a.right !== null) {
a.right.parent = a
}
b.left = a
a.parent = b
if (b.parent !== null) {
if (b.parent.right === a) {
b.parent.right = b
} else {
b.parent.left = b
}
}
this.setBalance(a)
this.setBalance(b)
return b }
private rotateRight(a: AVLnode<T>): AVLnode<T> {
let b: AVLnode<T> = a.left
b.parent = a.parent
a.left = b.right
if (a.left !== null) {
a.left.parent = a
}
b.right = a
a.parent = b
if (b.parent !== null) {
if (b.parent.right === a) {
b.parent.right = b
} else {
b.parent.left = b
}
}
this.setBalance(a)
this.setBalance(b)
return b }
private rotateLeftThenRight(n: AVLnode<T>): AVLnode<T> {
n.left = this.rotateLeft(n.left)
return this.rotateRight(n)
}
private rotateRightThenLeft(n: AVLnode<T>): AVLnode<T> {
n.right = this.rotateRight(n.right)
return this.rotateLeft(n)
}
private rebalance(n: AVLnode<T>): void {
this.setBalance(n)
if (n.balance === -2) {
if(this.height(n.left.left) >= this.height(n.left.right)) {
n = this.rotateRight(n)
} else {
n = this.rotateLeftThenRight(n)
}
} else if (n.balance === 2) {
if(this.height(n.right.right) >= this.height(n.right.left)) {
n = this.rotateLeft(n)
} else {
n = this.rotateRightThenLeft(n)
}
}
if (n.parent !== null) {
this.rebalance(n.parent)
} else {
this.root = n
}
}
private height(n: AVLnode<T>): number {
if (n === null) {
return -1
}
return 1 + Math.max(this.height(n.left), this.height(n.right))
}
private setBalance(n: AVLnode<T>): void {
n.balance = this.height(n.right) - this.height(n.left)
}
public showNodeBalance(n: AVLnode<T>): string {
if (n !== null) {
return `${this.showNodeBalance(n.left)} ${n.balance} ${this.showNodeBalance(n.right)}`
}
return ""
}
} </lang>