AVL Tree

Space	Time
	Access	Lookup	Insertion	Deletion
O(n)	O(log n)	O(log n)	O(log n)	O(log n)

Definition

Short

AVL Tree is a self-balancing binary search tree that ensures the heights of its 2 child subtrees differ by at most one.

Simplified

Binary AVL Tree is like a special bookshelf. It organizes data (like books) in a way that you can quickly find, add, or remove items. Each item can have 2 others next to it, one smaller and one bigger. The shelf stays balanced by ensuring the difference in the number of items on either side of any item is not more than one.

Detailed

AVL Tree named after inventors Adelson-Velsky and Landis, the first self-balancing binary search tree in computer science, ensures that the heights of 2 child subtrees of any node differ by at most one. If they differ by more than one, the tree is rebalanced. Operations like lookup, insertion, and deletion take O(log n) time, where n is the pre-operation node count. Tree rotations may be needed to rebalance after insertions or deletions.

Practice

Practice

Aspect	Pseudo Code
Insertion	insert(node, key): if node == ø: return createNewNode(key) if key < node.key: node.left = insert(node.left, key) else if key > node.key: node.right = insert(node.right, key) else: return node // Duplicate keys are not allowed node.height = 1 + max(height(node.left), height(node.right)) // Update height return rebalance(node) // Perform rotations to maintain balance
Rebalance	rebalance(node): balance = get_balance(node) if balance > 1: // Left Heavy if get_balance(node.left) < 0: // Left-Right Case node.left = left_rotate(node.left) return right_rotate(node) if balance < -1: // Right Heavy if get_balance(node.right) > 0: // Right-Left Case node.right = right_rotate(node.right) return left_rotate(node) return node left_rotate(y): x = y.right T2 = x.left x.left = y y.right = T2 y.height = 1 + max(height(y.left), height(y.right)) x.height = 1 + max(height(x.left), height(x.right)) return x right_rotate(x): y = x.left T2 = y.right y.right = x x.left = T2 x.height = 1 + max(height(x.left), height(x.right)) y.height = 1 + max(height(y.left), height(y.right)) return y
Height	height(node): if node == ø: return 0 return node.height
Get Balance	get_balance(node): if node == ø: return 0 return height(node.left) - height(node.right)
Search	search(node, key): if node == ø or key == node.key: return node if key < node.key: return search(node.left, key) return search(node.right, key)
Find MIN	find_min(node): while node.left != ø: node = node.left return node
Find MAX	find_max(node): while node.right != ø: node = node.right return node

Solution

package main

import (
	"math"
)

type AVLNode struct {
	Key    int
	Left   *AVLNode
	Right  *AVLNode
	Height int
}

type AVLTree struct {
	Root *AVLNode
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func height(node *AVLNode) int {
	if node == nil {
		return 0
	}
	return node.Height
}

func (tree *AVLTree) insert(node *AVLNode, key int) *AVLNode {
	if node == nil {
		return &AVLNode{Key: key}
	}

	if key < node.Key {
		node.Left = tree.insert(node.Left, key)
	} else if key > node.Key {
		node.Right = tree.insert(node.Right, key)
	}

	node.Height = 1 + max(height(node.Left), height(node.Right))

	return tree.rebalance(node)
}

func (tree *AVLTree) rebalance(node *AVLNode) *AVLNode {
	balance := tree.getBalance(node)

	if balance > 1 {
		if tree.getBalance(node.Left) < 0 {
			node.Left = tree.leftRotate(node.Left)
		}
		return tree.rightRotate(node)
	}

	if balance < -1 {
		if tree.getBalance(node.Right) > 0 {
			node.Right = tree.rightRotate(node.Right)
		}
		return tree.leftRotate(node)
	}

	return node
}

func (tree *AVLTree) leftRotate(y *AVLNode) *AVLNode {
	x := y.Right
	T2 := x.Left

	x.Left = y
	y.Right = T2

	y.Height = 1 + max(height(y.Left), height(y.Right))
	x.Height = 1 + max(height(x.Left), height(x.Right))

	return x
}

func (tree *AVLTree) rightRotate(x *AVLNode) *AVLNode {
	y := x.Left
	T2 := y.Right

	y.Right = x
	x.Left = T2

	x.Height = 1 + max(height(x.Left), height(x.Right))
	y.Height = 1 + max(height(y.Left), height(y.Right))

	return y
}

func (tree *AVLTree) height(node *AVLNode) int {
	if node == nil {
		return 0
	}
	return node.Height
}

func (tree *AVLTree) getBalance(node *AVLNode) int {
	return tree.height(node.Left) - tree.height(node.Right)
}

func (tree *AVLTree) search(node *AVLNode, key int) *AVLNode {
	if node == nil || key == node.Key {
		return node
	}
	if key < node.Key {
		return tree.search(node.Left, key)
	}
	return tree.search(node.Right, key)
}

func (tree *AVLTree) findMin(node *AVLNode) *AVLNode {
	current := node
	for current.Left != nil {
		current = current.Left
	}
	return current
}

func (tree *AVLTree) findMax(node *AVLNode) *AVLNode {
	current := node
	for current.Right != nil {
		current = current.Right
	}
	return current
}

func inorderTraversal(node *AVLNode) {
	if node != nil {
		inorderTraversal(node.Left)
		fmt.Print(node.Key, " ")
		inorderTraversal(node.Right)
	}
}

public class AVLTree {

  private AVLNode root;

  public AVLNode insert(AVLNode node, int key) {
    if (node == null) {
      return new AVLNode(key);
    }

    if (key < node.key) {
      node.left = insert(node.left, key);
    } else if (key > node.key) {
      node.right = insert(node.right, key);
    }

    node.height = 1 + Math.max(height(node.left), height(node.right));

    return rebalance(node);
  }

  private AVLNode rebalance(AVLNode node) {
    int balance = getBalance(node);

    if (balance > 1) {
      if (getBalance(node.left) < 0) {
        node.left = leftRotate(node.left);
      }
      return rightRotate(node);
    }

    if (balance < -1) {
      if (getBalance(node.right) > 0) {
        node.right = rightRotate(node.right);
      }
      return leftRotate(node);
    }

    return node;
  }

  private AVLNode leftRotate(AVLNode y) {
    AVLNode x = y.right;
    AVLNode T2 = x.left;

    x.left = y;
    y.right = T2;

    y.height = 1 + Math.max(height(y.left), height(y.right));
    x.height = 1 + Math.max(height(x.left), height(x.right));

    return x;
  }

  private AVLNode rightRotate(AVLNode x) {
    AVLNode y = x.left;
    AVLNode T2 = y.right;

    y.right = x;
    x.left = T2;

    x.height = 1 + Math.max(height(x.left), height(x.right));
    y.height = 1 + Math.max(height(y.left), height(y.right));

    return y;
  }

  private int height(AVLNode node) {
    return (node != null) ? node.height : 0;
  }

  private int getBalance(AVLNode node) {
    return (node != null) ? height(node.left) - height(node.right) : 0;
  }

  public AVLNode search(AVLNode node, int key) {
    if (node == null || key == node.key) {
      return node;
    }
    return (key < node.key) ? search(node.left, key) : search(node.right, key);
  }

  public AVLNode findMin(AVLNode node) {
    AVLNode current = node;
    while (current != null && current.left != null) {
      current = current.left;
    }
    return current;
  }

  public AVLNode findMax(AVLNode node) {
    AVLNode current = node;
    while (current != null && current.right != null) {
      current = current.right;
    }
    return current;
  }

  public static class AVLNode {

    public int key;
    public AVLNode left;
    public AVLNode right;
    public int height;

    public AVLNode(int key) {
      this.key = key;
      this.height = 1;
    }
  }
}

class AVLTree {
  static AVLNode = class {
    constructor(key, left = null, right = null, height = 1) {
      this.key = key;
      this.left = left;
      this.right = right;
      this.height = height;
    }
  };

  constructor() {
    this.root = null;
  }

  insert(node, key) {
    if (node === null) {
      return new AVLTree.AVLNode(key);
    }

    if (key < node.key) {
      node.left = this.insert(node.left, key);
    } else if (key > node.key) {
      node.right = this.insert(node.right, key);
    }

    node.height = 1 + this.max(this.height(node.left), this.height(node.right));

    return this.rebalance(node);
  }

  rebalance(node) {
    const balance = this.getBalance(node);

    if (balance > 1) {
      if (this.getBalance(node.left) < 0) {
        node.left = this.leftRotate(node.left);
      }
      return this.rightRotate(node);
    }

    if (balance < -1) {
      if (this.getBalance(node.right) > 0) {
        node.right = this.rightRotate(node.right);
      }
      return this.leftRotate(node);
    }

    return node || new AVLTree.AVLNode(0);
  }

  leftRotate(y) {
    const x = y.right;
    const T2 = x.left;

    x.left = y;
    y.right = T2;

    y.height = 1 + this.max(this.height(y.left), this.height(y.right));
    x.height = 1 + this.max(this.height(x.left), this.height(x.right));

    return x;
  }

  rightRotate(x) {
    const y = x.left;
    const T2 = y.right;

    y.right = x;
    x.left = T2;

    x.height = 1 + this.max(this.height(x.left), this.height(x.right));
    y.height = 1 + this.max(this.height(y.left), this.height(y.right));

    return y;
  }

  height(node) {
    return node ? node.height : 0;
  }

  getBalance(node) {
    return node ? this.height(node.left) - this.height(node.right) : 0;
  }

  search(node, key) {
    if (!node || key === node.key) {
      return node;
    }
    return key < node.key
      ? this.search(node.left, key)
      : this.search(node.right, key);
  }

  findMin(node) {
    let current = node;
    while (current && current.left) {
      current = current.left;
    }
    return current;
  }

  findMax(node) {
    let current = node;
    while (current && current.right) {
      current = current.right;
    }
    return current;
  }

  max(a, b) {
    return a > b ? a : b;
  }
}

class AVLTree {
    data class AVLNode(var key: Int, var left: AVLNode? = null, var right: AVLNode? = null, var height: Int = 1)

    var root: AVLNode? = null

    fun insert(node: AVLNode?, key: Int): AVLNode {
        if (node == null) {
            return AVLNode(key)
        }

        if (key < node.key) {
            node.left = insert(node.left, key)
        } else if (key > node.key) {
            node.right = insert(node.right, key)
        } else {
        }

        node.height = 1 + max(height(node.left), height(node.right))

        return rebalance(node)
    }

    private fun rebalance(node: AVLNode?): AVLNode {
        val balance = getBalance(node)

        if (balance > 1) {
            if (getBalance(node?.left) < 0) {
                node?.left = leftRotate(node?.left)
            }
            return rightRotate(node)
        }

        if (balance < -1) {
            if (getBalance(node?.right) > 0) {
                node?.right = rightRotate(node?.right)
            }
            return leftRotate(node)
        }

        return node ?: AVLNode(0)
    }

    private fun leftRotate(y: AVLNode?): AVLNode? {
        val x = y?.right
        val T2 = x?.left

        x?.left = y
        y?.right = T2

        y?.height = 1 + max(height(y?.left), height(y?.right))
        x?.height = 1 + max(height(x?.left), height(x?.right))

        return x
    }

    private fun rightRotate(x: AVLNode?): AVLNode? {
        val y = x?.left
        val T2 = y?.right

        y?.right = x
        x?.left = T2

        x?.height = 1 + max(height(x?.left), height(x?.right))
        y?.height = 1 + max(height(y?.left), height(y?.right))

        return y
    }

    private fun height(node: AVLNode?): Int {
        return node?.height ?: 0
    }

    private fun getBalance(node: AVLNode?): Int {
        return height(node?.left) - height(node?.right)
    }

    fun search(node: AVLNode?, key: Int): AVLNode? {
        if (node == null || key == node.key) {
            return node
        }
        return if (key < node.key) {
            search(node.left, key)
        } else {
            search(node.right, key)
        }
    }

    fun findMin(node: AVLNode?): AVLNode? {
        var current = node
        while (current?.left != null) {
            current = current.left
        }
        return current
    }

    fun findMax(node: AVLNode?): AVLNode? {
        var current = node
        while (current?.right != null) {
            current = current.right
        }
        return current
    }
}

class AVLTree:
    class AVLNode:
        def __init__(self, key, left=None, right=None, height=1):
            self.key = key
            self.left = left
            self.right = right
            self.height = height

    def __init__(self):
        self.root = None

    def insert(self, node, key):
        if node is None:
            return self.AVLNode(key)

        if key < node.key:
            node.left = self.insert(node.left, key)
        elif key > node.key:
            node.right = self.insert(node.right, key)

        node.height = 1 + max(self.height(node.left), self.height(node.right))

        return self.rebalance(node)

    def rebalance(self, node):
        balance = self.get_balance(node)

        if balance > 1:
            if self.get_balance(node.left) < 0:
                node.left = self.left_rotate(node.left)
            return self.right_rotate(node)

        if balance < -1:
            if self.get_balance(node.right) > 0:
                node.right = self.right_rotate(node.right)
            return self.left_rotate(node)

        return node or self.AVLNode(0)

    def left_rotate(self, y):
        x = y.right
        T2 = x.left

        x.left = y
        y.right = T2

        y.height = 1 + max(self.height(y.left), self.height(y.right))
        x.height = 1 + max(self.height(x.left), self.height(x.right))

        return x

    def right_rotate(self, x):
        y = x.left
        T2 = y.right

        y.right = x
        x.left = T2

        x.height = 1 + max(self.height(x.left), self.height(x.right))
        y.height = 1 + max(self.height(y.left), self.height(y.right))

        return y

    def height(self, node):
        return node.height if node else 0

    def get_balance(self, node):
        return self.height(node.left) - self.height(node.right) if node else 0

    def search(self, node, key):
        if not node or key == node.key:
            return node
        return self.search(node.left, key) if key < node.key else self.search(node.right, key)

    def find_min(self, node):
        current = node
        while current and current.left:
            current = current.left
        return current

    def find_max(self, node):
        current = node
        while current and current.right:
            current = current.right
        return current

use std::cmp::max;
use std::mem;

#[derive(Debug)]
struct AVLNode {
    key: i32,
    left: Option<Box<AVLNode>>,
    right: Option<Box<AVLNode>>,
    height: i32,
}

impl AVLNode {
    fn new(key: i32) -> Self {
        AVLNode {
            key,
            left: None,
            right: None,
            height: 1,
        }
    }
}

#[derive(Debug)]
pub struct AVLTree {
    root: Option<Box<AVLNode>>,
}

impl AVLTree {
    pub fn new() -> Self {
        AVLTree { root: None }
    }

    pub fn insert(&mut self, node: Option<Box<AVLNode>>, key: i32) -> Option<Box<AVLNode>> {
        let mut new_node = node.unwrap_or_else(|| Box::new(AVLNode::new(key)));

        if key < new_node.key {
            new_node.left = self.insert(mem::replace(&mut new_node.left, None), key);
        } else if key > new_node.key {
            new_node.right = self.insert(mem::replace(&mut new_node.right, None), key);
        }

        new_node.height = 1 + max(Self::height(&new_node.left), Self::height(&new_node.right));

        Some(Box::new(self.rebalance(new_node)))
    }

    fn rebalance(&self, mut node: AVLNode) -> AVLNode {
        let balance = Self::get_balance(&node);

        if balance > 1 {
            if Self::get_balance(&node.left) < 0 {
                node.left = Some(Box::new(self.left_rotate(node.left.take().unwrap())));
            }
            return self.right_rotate(node);
        }

        if balance < -1 {
            if Self::get_balance(&node.right) > 0 {
                node.right = Some(Box::new(self.right_rotate(node.right.take().unwrap())));
            }
            return self.left_rotate(node);
        }

        node
    }

    fn left_rotate(&self, mut y: AVLNode) -> AVLNode {
        let x = y.right.take().unwrap();
        let t2 = x.left.take();

        y.right = Some(x);
        x.left = Some(Box::new(y));

        y.height = 1 + max(Self::height(&y.left), Self::height(&y.right));
        x.height = 1 + max(Self::height(&x.left), Self::height(&x.right));

        x.into_inner()
    }

    fn right_rotate(&self, mut x: AVLNode) -> AVLNode {
        let y = x.left.take().unwrap();
        let t2 = y.right.take();

        x.left = Some(y);
        y.right = Some(Box::new(x));

        x.height = 1 + max(Self::height(&x.left), Self::height(&x.right));
        y.height = 1 + max(Self::height(&y.left), Self::height(&y.right));

        y.into_inner()
    }

    fn height(node: &Option<Box<AVLNode>>) -> i32 {
        node.as_ref().map_or(0, |n| n.height)
    }

    fn get_balance(node: &Option<Box<AVLNode>>) -> i32 {
        Self::height(&node.as_ref().map(|n| n.left.clone())) - Self::height(&node.as_ref().map(|n| n.right.clone()))
    }

    pub fn search(&self, node: &Option<Box<AVLNode>>, key: i32) -> Option<Box<AVLNode>> {
        match node {
            Some(n) if key == n.key => Some(n.clone()),
            Some(n) if key < n.key => self.search(&n.left, key),
            Some(n) => self.search(&n.right, key),
            _ => None,
        }
    }

    pub fn find_min(&self, node: &Option<Box<AVLNode>>) -> Option<Box<AVLNode>> {
        let mut current = node.as_ref().map(|n| n.clone());

        while let Some(n) = current {
            current = n.left.as_ref().map(|n| n.clone());
        }

        current
    }

    pub fn find_max(&self, node: &Option<Box<AVLNode>>) -> Option<Box<AVLNode>> {
        let mut current = node.as_ref().map(|n| n.clone());

        while let Some(n) = current {
            current = n.right.as_ref().map(|n| n.clone());
        }

        current
    }
}

class AVLTree {
  data class AVLNode {
    key: number;
    left?: AVLNode;
    right?: AVLNode;
    height: number;

    constructor(key: number, left?: AVLNode, right?: AVLNode, height: number = 1) {
      this.key = key;
      this.left = left;
      this.right = right;
      this.height = height;
    }
  }

  root: AVLNode | undefined;

  insert(node: AVLNode | undefined, key: number): AVLNode {
    if (!node) {
      return new AVLNode(key);
    }

    if (key < node.key) {
      node.left = this.insert(node.left, key);
    } else if (key > node.key) {
      node.right = this.insert(node.right, key);
    }

    node.height = 1 + Math.max(this.height(node.left), this.height(node.right));

    return this.rebalance(node);
  }

  private rebalance(node: AVLNode | undefined): AVLNode {
    const balance = this.getBalance(node);

    if (balance > 1) {
      if (this.getBalance(node?.left) < 0) {
        node?.left = this.leftRotate(node?.left);
      }
      return this.rightRotate(node!);
    }

    if (balance < -1) {
      if (this.getBalance(node?.right) > 0) {
        node?.right = this.rightRotate(node?.right);
      }
      return this.leftRotate(node!);
    }

    return node || new AVLNode(0);
  }

  private leftRotate(y: AVLNode): AVLNode {
    const x = y.right!;
    const T2 = x.left;

    x.left = y;
    y.right = T2;

    y.height = 1 + Math.max(this.height(y.left), this.height(y.right));
    x.height = 1 + Math.max(this.height(x.left), this.height(x.right));

    return x;
  }

  private rightRotate(x: AVLNode): AVLNode {
    const y = x.left!;
    const T2 = y.right;

    y.right = x;
    x.left = T2;

    x.height = 1 + Math.max(this.height(x.left), this.height(x.right));
    y.height = 1 + Math.max(this.height(y.left), this.height(y.right));

    return y;
  }

  private height(node: AVLNode | undefined): number {
    return node ? node.height : 0;
  }

  private getBalance(node: AVLNode | undefined): number {
    return this.height(node?.left) - this.height(node?.right);
  }

  search(node: AVLNode | undefined, key: number): AVLNode | undefined {
    if (!node || key === node.key) {
      return node;
    }
    return key < node.key ? this.search(node.left, key) : this.search(node.right, key);
  }

  findMin(node: AVLNode | undefined): AVLNode | undefined {
    let current = node;
    while (current?.left) {
      current = current.left;
    }
    return current;
  }

  findMax(node: AVLNode | undefined): AVLNode | undefined {
    let current = node;
    while (current?.right) {
      current = current.right;
    }
    return current;
  }
}