AVL Tree

A self-balancing binary search tree where the difference between heights of left and right subtrees is at most one. Ensures fast lookups, insertions, and deletions.

AVL Tree Visualization

LentoRápido
🔊 Sound
ProntoÁrvore AVL vazia. Insira um valor.
● Caminho de busca● Encontrado BF = 0 |BF| = 1● |BF| > 1 (raro)
árvore vazia — insira um valor

Complexity

Time Complexity: O(log n)
Space Complexity: O(n)

Pseudocode

function insert(node, key):
  if node is null:
    return new Node(key)
  if key < node.key:
    node.left = insert(node.left, key)
  else:
    node.right = insert(node.right, key)
  update height(node)
  balance = getBalance(node)
  if balance > 1 and key < node.left.key:
    return rotateRight(node)
  if balance < -1 and key > node.right.key:
    return rotateLeft(node)
  if balance > 1 and key > node.left.key:
    node.left = rotateLeft(node.left)
    return rotateRight(node)
  if balance < -1 and key < node.right.key:
    node.right = rotateRight(node.right)
    return rotateLeft(node)
  return node

Related Algorithms

Binary Search Tree

A Binary Search Tree (BST) is a binary tree where each node has at most two children, and the left subtree contains values less than the node, while the right subtree contains values greater than the node.

Time: O(log n) average, O(n) worst for search/insert/delete | Space: O(n)

Red-Black Tree

A self-balancing binary search tree with color properties that ensure the tree remains approximately balanced. Guarantees logarithmic time operations.

Time: O(log n) | Space: O(n)