AVL Trees
AVL Tree Definition
- AVL trees are balanced.
- An AVL Tree is a binary search tree such that for every internal node v of T, the heights of the children of v can differ by at most 1.
Height of an AVL Tree
- Fact: The height of an AVL tree storing n keys is O(log n).
- Proof: Let us bound n(h): the minimum number of internal nodes of an AVL tree of height h.
- We easily see that n(1) = 1 and n(2) = 2
- For n > 2, an AVL tree of height h contains the root node, one AVL subtree of height n-1 and another of height n-2.
- That is, n(h) = 1 + n(h-1) + n(h-2)
- Knowing n(h-1) > n(h-2), we get n(h) > 2n(h-2). So n(h) > 2n(h-2), n(h) > 4n(h-4), n(h) > 8n(n-6), … (by induction), n(h) > 2in(h-2i)
- Solving the base case we get: n(h) > 2^(h/2-1)
- Taking logarithms: h < 2log n(h) +2
- Thus the height of an AVL tree is O(log n)
Insertion
- Insertion is as in a binary search tree
- Always done by expanding an external node.
- Afterwards Restructuring
![BST_Insertion](Images/BST_Insertion.PNG)
Trinode Restructuring
- let (a,b,c) be an inorder listing of x, y, z
- perform the rotations needed to make b the topmost node of the three
![BST_Insertion](Images/AVL_Restructuring.PNG)
Removal
- Removal begins as in a binary search tree, which means the node removed will become an empty external node. Its parent, w, may cause an imbalance.
*
Rebalancing after a Removal
- Let z be the first unbalanced node encountered while travelling up the tree from w. Also, let y be the child of z with the larger height, and let x be the child of y with the larger height.
- We perform restructure(x) to restore balance at z.
- As this restructuring may upset the balance of another node higher in the tree, we must continue checking for balance until the root of T is reached
![BST_Insertion](Images/AVL_Rebalancing_after_removal.PNG)
Running Times
- a single restructure is O(1) using a linked-structure binary tree
- find is O(log n) height of tree is O(log n), no restructures needed
- insert is O(log n)
- initial find is O(log n)
- Restructuring up the tree, maintaining heights is O(log n)
- remove is O(log n)
- initial find is O(log n)
- Restructuring up the tree, maintaining heights is O(log n)
Code
package examples;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Map;
import java.util.Random;
import java.util.TreeMap;
import com.sun.javafx.css.CascadingStyle;
public class MyAVLTree<K extends Comparable<? super K>, E> implements
OrderedDictionary<K, E> {
class AVLNode implements Locator<K, E>{
AVLNode parent,left,right;
Object creator = MyAVLTree.this;
E elem;
K key;
int height;
@Override
public E element() {
return elem;
}
@Override
public K key() {
return key;
}
boolean isExternal(){
return left==null;
}
boolean isLeftChild(){
return parent != null && parent.left==this;
}
boolean isRightChild(){
return parent != null && parent.right==this;
}
void expand(K key,E elem){
this.elem = elem;
this.key = key;
left = new AVLNode();
right = new AVLNode();
left.parent = this;
right.parent = this;
height = 1;
}
}
private AVLNode root = new AVLNode();
private int size;
private AVLNode checkAndCast(Locator<K,E> p){
try {
AVLNode n = (AVLNode) p;
if (n.creator == null) throw new RuntimeException(" allready removed locator!");
if (n.creator != this) throw new RuntimeException(" locator belongs to another AVLTree instance");
return n;
} catch (ClassCastException e) {
throw new RuntimeException(" locator belongs to another container-type ");
}
}
@Override
public int size() {
return size;
}
@Override
public Locator<K, E> find(K key) {
AVLNode n = root;
AVLNode found = null;
while ( ! n.isExternal()){
int comp = key.compareTo(n.key);
if (comp < 0) n = n.left;
else if (comp > 0) n=n.right;
else {
found = n;
n=n.left;
}
}
return found;
}
@Override
public Locator<K, E>[] findAll(K key) {
AVLNode n = (AVLNode)find(key);
if (n==null) return (Locator<K,E>[]) new Locator[0];
List<AVLNode> list = new MyLinkedList<>();
while(n!=null && n.key.equals(key)) {
list.insertLast(n);
n= (AVLNode ) next(n);
}
Iterator<AVLNode> it = list.elements();
Locator[] ret = new Locator[list.size()];
for(int i=0;i<ret.length;i++) ret[i]=it.next();
return ret;
}
@Override
public Locator<K, E> insert(K key, E o) {
AVLNode n = root;
while ( ! n.isExternal()){
if (key.compareTo(n.key) < 0){
n=n.left;
}
else n = n.right;
}
n.expand(key,o);
size++;
adjustHeightAboveAndRebalance(n);
return n;
}
private void adjustHeightAboveAndRebalance(AVLNode n) {
n = n.parent;
while (n != null ){
int newHeight = Math.max(n.left.height,n.right.height)+1;
boolean balanced = Math.abs(n.left.height-n.right.height)<2;
if (balanced && newHeight == n.height) break;
n.height = newHeight;
if ( ! balanced) n = restructure(n);
n = n.parent;
}
}
@Override
public void remove(Locator<K, E> loc) {
AVLNode n = checkAndCast(loc);
AVLNode w;
if (! n.left.isExternal() && ! n.right.isExternal()) {
AVLNode r;
if (n.right.height > n.left.height){
r = n.right;
while ( ! r.left.isExternal()) r = r.left;
}
else {
r=n.left;
while ( ! r.right.isExternal()) r = r.right;
}
w = removeAboveExternal(r);
r.parent = n.parent;
if (n==root) root = r;
else {
if (n.isLeftChild()) n.parent.left = r;
else n.parent.right = r;
}
r.height = n.height;
r.left = n.left;
r.right = n.right;
r.right.parent = r;
r.left.parent = r;
}
else w = removeAboveExternal(n);
n.creator = null;
size--;
adjustHeightAboveAndRebalance(w);
}
private AVLNode removeAboveExternal(AVLNode n) {
AVLNode w;
if (n.left.isExternal()){
w = n.right;
w.parent = n.parent;
if (n.isLeftChild()) w.parent.left = w;
else if (n.isRightChild()) w.parent.right = w;
else root = w;
}
else {
w = n.left;
w.parent = n.parent;
if (n.isLeftChild()) w.parent.left = w;
else if (n.isRightChild()) w.parent.right = w;
else root = w;
}
return w;
}
private AVLNode restructure(AVLNode n) {
AVLNode p=n.parent,z=n,x=null,y=null,
a=null,b=null,c=null, t1=null,t2=null;
if (z.left.height > z.right.height){
c=z;
y=z.left;
if (y.left.height >=y.right.height){
x=y.left;
t1=x.right;
t2=y.right;
b=y;
a=x;
}
else {
x=y.right;
t1=x.left;
t2=x.right;
a=y;
b=x;
}
}
else{
a=z;
y=z.right;
if (y.right.height >= y.left.height){
x=y.right;
b=y;
c=x;
t1=y.left;
t2=x.left;
}
else {
x=y.left;
b=x;
c=y;
t1=x.left;
t2=x.right;
}
}
b.parent = p;
if (p != null){
if (p.left == z) {
p.left=b;
}
else p.right=b;
}
else {
root=b;
}
b.right = c;
b.left = a;
a.parent = b;
c.parent = b;
a.right = t1;
t1.parent = a;
c.left = t2;
t2.parent = c;
a.height = Math.max(a.left.height, a.right.height)+1;
c.height = Math.max(c.left.height, c.right.height)+1;
b.height = Math.max(b.left.height, b.right.height)+1;
return b;
}
@Override
public Locator<K, E> closestBefore(K key) {
if (size==0) return null;
AVLNode n = root;
AVLNode found = null;
while ( ! n.isExternal()){
int comp = key.compareTo(n.key);
if (comp < 0) n = n.left;
else if (comp > 0) n=n.right;
else {
found = n;
n=n.left;
}
}
if (found != null) return previous(found);
if (n.isRightChild()) return n.parent;
return previous(n.parent);
}
@Override
public Locator<K, E> closestAfter(K key) {
if (size==0) return null;
AVLNode n = root;
AVLNode found = null;
while ( ! n.isExternal()){
int comp = key.compareTo(n.key);
if (comp > 0) n = n.right;
else if (comp < 0) n=n.left;
else {
found = n;
n=n.right;
}
}
if (found != null) return next(found);
if (n.isLeftChild()) return n.parent;
return next(n.parent);
}
@Override
public Locator<K, E> next(Locator<K, E> loc) {
AVLNode n = checkAndCast(loc);
if (n.right.isExternal()){
while(n.isRightChild()) n=n.parent;
n=n.parent;
}
else {
n=n.right;
while (! n.left.isExternal()) n=n.left;
}
return n;
}
@Override
public Locator<K, E> previous(Locator<K, E> loc) {
AVLNode n = checkAndCast(loc);
if (n.left.isExternal()){
while(n.isLeftChild()) n=n.parent;
n=n.parent;
}
else {
n=n.left;
while (! n.right.isExternal()) n=n.right;
}
return n;
}
@Override
public Locator<K, E> min() {
if (size == 0) return null;
AVLNode n = root;
while (! n.left.isExternal()) n=n.left;
return n;
}
@Override
public Locator<K, E> max() {
if (size == 0) return null;
AVLNode n = root;
while (! n.right.isExternal()) n=n.right;
return n;
}
@Override
public Iterator<Locator<K, E>> sortedLocators() {
return new Iterator<Locator<K,E>>() {
AVLNode current = (AVLNode)min();
@Override
public boolean hasNext() {
return current == null;
}
@Override
public Locator<K, E> next() {
AVLNode ret = current;
if (current.right.isExternal()){
while(current.isRightChild()) current=current.parent;
current=current.parent;
}
else {
current=current.right;
while (! current.left.isExternal()) current=current.left;
}
return ret;
}
};
}
public void print(){
if (size>0) prittyPrint(root,"");
}
private void print(AVLNode n,String in) {
if (n.isExternal()) return;
print(n.right,in+".");
System.out.println(in+n.key);
print(n.left,in+".");
}
private void prittyPrint(AVLNode r, String in) {
if (r.isExternal()) return;
int sLen = in.length();
String inNeu = in;
if (r.isRightChild()) inNeu = in.substring(0,sLen-2)+" ";
prittyPrint(r.right,inNeu+" |");
String inN = in;
if (sLen>0) inN = in.substring(0,sLen-1)+"+-";
else inN = in+"-";
if ( ! r.right.isExternal()) System.out.println(inNeu+" |");
else System.out.println(inNeu);
System.out.println(inN+r.key()+"(h="+r.height+")"+":"+r.elem+")");
inNeu = in;
if (r.isLeftChild()){
inNeu = in.substring(0,sLen-2)+" ";
}
prittyPrint(r.left,inNeu+" |");
}
public void test(){
if (root.parent != null) throw new RuntimeException("root has a parent: "+root.parent.key);
test(root);
}
private void test(AVLNode n) {
if (n.isExternal()) return;
test(n.left);
test(n.right);
if (n.left.parent != n) throw new RuntimeException("chaining incorrect"+n.key);
if (n.right.parent != n) throw new RuntimeException("chaining incorrec"+n.key);
if (Math.max(n.left.height,n.right.height)+1!=n.height)
throw new RuntimeException("Height wrong"+n.key);
if (n.left.key !=null && n.left.key.compareTo(n.key)>0) throw new RuntimeException("order wrong "+n.key);
if (n.right.key !=null && n.right.key.compareTo(n.key)<0) throw new RuntimeException("order wrong "+n.key);
if (Math.abs(n.left.height-n.right.height)> 1) throw new RuntimeException("unbalanced "+n.key);
if (n.creator != this) throw new RuntimeException("invalid node: "+n.key);
}
public static void main(String[] argv){
MyAVLTree<Integer, String> t = new MyAVLTree<>();
Random rand = new Random();
t.insert(6, "e 6.1");
t.insert(10, "e 10");
t.insert(7, "e 7");
t.insert(7, "e 7.2");
t.insert(6, "e 6.2 ");
t.insert(3, "e 3");
Locator loc = t.insert(1, "e 1");
t.insert(6, "e 6.3 ");
t.insert(4, "e 4");
t.insert(11, "e 11");
t.print();
System.out.println(t.previous(t.closestBefore(2)));
}
}