Binary Search Trees & Balanced Trees

Definition

A binary search tree is a tree data structure in the form of a binary tree, defined as follows:

1. An empty tree is a binary search tree.

2. If the left subtree of a binary search tree is nonempty, the additional weight of every point in its left subtree is less than the value of its root.

3. If the right subtree of a binary search tree is nonempty, the additional weight of every point in its right subtree is greater than the value of its root.

4. Both the left and right subtrees of a binary search tree are binary search trees.

The time spent by basic operations on a binary search tree is proportional to the height of the tree. For a binary search tree with $n$ nodes, the optimal time complexity of these operations is $O(\log n)$ and the worst-case complexity is $O(n)$. The expected height of a randomly constructed binary search tree is $O(\log n)$.

Operations

Definition of a Binary Search Tree Node

struct TreeNode {
  int key;
  TreeNode* left;
  TreeNode* right;
  // Maintain other information, such as height and node count
  int size;   // Size of the subtree rooted at the current node
  int count;  // Number of duplicates of the current node

  TreeNode(int value)
      : key(value), size(1), count(1), left(nullptr), right(nullptr) {}
};

Traversing a Binary Search Tree

It follows from the recursive definition of a binary search tree that the sequence of weights in its in-order traversal is nondecreasing. The time complexity is $O(n)$.

The code for traversing a binary search tree is as follows:

void inorderTraversal(TreeNode* root) {
  if (root == nullptr) {
    return;
  }
  inorderTraversal(root->left);
  std::cout << root->key << " ";
  inorderTraversal(root->right);
}

Finding the Minimum/Maximum

By the properties of a binary search tree, its minimum value is the top vertex of its left chain, and its maximum value is the top vertex of its right chain. The time complexity is $O(h)$.

int findMin(TreeNode* root) {
  if (root == nullptr) {
    return -1;
  }
  while (root->left != nullptr) {
    root = root->left;
  }
  return root->key;
}

int findMax(TreeNode* root) {
  if (root == nullptr) {
    return -1;
  }
  while (root->right != nullptr) {
    root = root->right;
  }
  return root->key;
}

Searching for an Element

In the binary search tree rooted at root, search for a node with value value.

The cases are as follows:

• If root is empty, return false.
• If the weight of root equals value, return true.
• If the weight of root is greater than value, continue searching in the left subtree of root.
• If the weight of root is less than value, continue searching in the right subtree of root.

The time complexity is $O(h)$.

bool search(TreeNode* root, int target) {
  if (root == nullptr) {
    return false;
  }
  if (root->key == target) {
    return true;
  } else if (target < root->key) {
    return search(root->left, target);
  } else {
    return search(root->right, target);
  }
}

Insertion, deletion, and modification all require searching the binary search tree first.

Inserting an Element

In the binary search tree rooted at root, insert a node with value value.

The cases are as follows:

• If root is empty, directly return a new node with value value.

• If the weight of root equals value, increment by $1$ the number of occurrences of this value in the node's auxiliary field.

• If the weight of root is greater than value, in the left subtree of root insert a node with weight value.

• If the weight of root is less than value, in the right subtree of root insert a node with weight value.

The time complexity is $O(h)$.

TreeNode* insert(TreeNode* root, int value) {
  if (root == nullptr) {
    return new TreeNode(value);
  }
  if (value < root->key) {
    root->left = insert(root->left, value);
  } else if (value > root->key) {
    root->right = insert(root->right, value);
  } else {
    root->count++;  // The node values are equal; increase the duplicate count
  }
  root->size = root->count + (root->left ? root->left->size : 0) +
               (root->right ? root->right->size : 0);  // Update the size of the node's subtree
  return root;
}

Deleting an Element

In the binary search tree rooted at root, delete a node with value value.

First search the binary search tree for the node with weight value, then consider the following cases:

• If the node's auxiliary count is greater than $1$, only decrease count.

• If the node's auxiliary count is $1$:

  • If root is a leaf node, delete the node directly.

  • If root is a chain node, that is, a node with only one child, return that child.

  • If root has two nonempty child subtrees, it is generally replaced by the maximum value in its left subtree (the rightmost node of the left subtree) or the minimum value in its right subtree (the leftmost node of the right subtree), and then deleted.

The time complexity is $O(h)$.

// The return value here is the new root after deleting value
TreeNode* remove(TreeNode* root, int value) {
  if (root == nullptr) {
    return root;
  }
  if (value < root->key) {
    root->left = remove(root->left, value);
  } else if (value > root->key) {
    root->right = remove(root->right, value);
  } else {
    if (root->count > 1) {
      root->count--;  // The duplicate count is greater than 1; decrease it
    } else {
      if (root->left == nullptr) {
        TreeNode* temp = root->right;
        delete root;
        return temp;
      } else if (root->right == nullptr) {
        TreeNode* temp = root->left;
        delete root;
        return temp;
      } else {
        TreeNode* successor = findMinNode(root->right);
        root->key = successor->key;
        root->count = successor->count;  // Update the duplicate count
        // When successor->count > 1, this node should also be deleted; otherwise
        // subsequent deletions would only decrease the duplicate count
        successor->count = 1;
        root->right = remove(root->right, successor->key);
      }
    }
  }
  // Continue maintaining size rather than writing --root->size;
  // because value may not be in the tree, so no deletion may have occurred
  root->size = root->count + (root->left ? root->left->size : 0) +
               (root->right ? root->right->size : 0);
  return root;
}

// Use the minimum value of the right subtree as an example
TreeNode* findMinNode(TreeNode* root) {
  while (root->left != nullptr) {
    root = root->left;
  }
  return root;
}

Querying an Element's Rank

The rank is defined as the number of elements before the first equal element after sorting the array in ascending order, plus one.

To find an element's rank, first move from the root to that element. Whenever the move goes right, add the number of nodes in the left child and the duplicate count of the current node; finally, add the size of the terminal node's left subtree plus one.

The time complexity is $O(h)$.

int queryRank(TreeNode* root, int v) {
  if (root == nullptr) return 0;
  if (root->key == v) return (root->left ? root->left->size : 0) + 1;
  if (root->key > v) return queryRank(root->left, v);
  return queryRank(root->right, v) + (root->left ? root->left->size : 0) +
         root->count;
}

Finding the Element with Rank k

In a subtree, the rank of the root depends on the size of its left subtree.

• If the size of its left subtree is greater than or equal to $k$, the element is in the left subtree;

• If the size of its left subtree lies in the interval $[k-\textit{count},k-1]$ (count is the number of occurrences of the current node's value), the element is the root of the subtree;

• If the size of its left subtree is less than $k-\textit{count}$, the element is in the right subtree.

The time complexity is $O(h)$.

int querykth(TreeNode* root, int k) {
  if (root == nullptr) return -1;  // Or return another suitable value as needed
  if (root->left) {
    if (root->left->size >= k) return querykth(root->left, k);
    if (root->left->size + root->count >= k) return root->key;
  } else {
    if (k <= root->count) return root->key;
  }
  return querykth(root->right,
                  k - (root->left ? root->left->size : 0) - root->count);
}

Introduction to Balanced Trees

One purpose of using a search tree is to reduce the time needed for insertion, deletion, modification, and lookup (insertion, deletion, and modification all include a lookup operation).

Regarding lookup efficiency, if a tree has height $h$, then in the worst case finding a key requires $h$ comparisons, so the lookup time complexity (also called the average search length, ASL) is no more than $O(h)$. All operations on an ideal binary search tree can be reduced to $O(\log n)$, where n is the total number of nodes.

However, the $O(\log n)$ time complexity describes only the ideal case. In the worst case, a search tree may degenerate into a linked list. Imagine a binary search tree in which every node has only a right child; its behavior is then the same as a linked list, and all operations (insertion, deletion, modification, and lookup) take $O(n)$ time.

It can be seen that the complexity of operations is related to the tree height $h$. This leads to balanced trees, which reduce operation complexity by maintaining the height (balance) of the tree through certain operations.

Definition of Balance

The definition of whether a search tree is “balanced” differs among balanced trees. For example, in a binary search tree rooted at T, if the heights of the left and right subtrees differ greatly, or the left subtree has far more nodes than the right subtree, the tree is clearly not balanced.

For binary search trees, a common definition of balance is: in the tree rooted at T, the heights of the left and right subtrees of every node differ by at most 1.

• Splay tree: for any access operation on a node (search, insertion, or deletion), the accessed node is moved to the root of the tree.

• AVL tree: each node N maintains the height of the tree rooted at N. The AVL balance definition is: T is an AVL tree if and only if both subtrees are AVL trees and $|height(T->left) - height(T->right)| \leq 1$.

• Size Balanced Tree: each node N maintains the number of nodes size in the tree rooted at N. The balance definition is that the size of any node is no smaller than the size of every child of its sibling (Sibling), that is, every Nephew.

In addition, for search trees with the same set of element values, the balanced state may not be unique. In other words, two different search trees may contain the same set of element values and both be balanced.

The Balancing Process

Adjusting a search tree that does not satisfy the balance condition can restore its balance.

For binary balanced trees, balancing operations consist of left rotation (Left Rotate or zag) and right rotation (Right Rotate or zig). Because a binary balanced tree must preserve its in-order traversal sequence during adjustment, neither operation changes that sequence.

We first introduce the right rotation, also called a “right single rotation” or an “LL balance rotation”. A right rotation at node $A$ rotates $A$'s left child $B$ up and to the right to replace $A$ as the root, rotates node $A$ down and to the right to become the root of $B$'s right subtree, and makes the original right subtree of $B$ the left subtree of $A$.

A right rotation changes only three groups of node relationships, equivalent to cyclically permuting three groups of edges, so one node must be saved before performing the rotation update.

The usual update order for a right rotation is: save node $B$ (the new root), make $A$'s left child point to $B$'s right subtree $T2$, make $B$'s right-child pointer point to $A$, and finally make $A$'s parent point to the saved $B$.

By exactly the same reasoning, there is a corresponding left rotation, also called a “left single rotation” or an “RR balance rotation”. A left rotation is the mirror image of a right rotation.

The code for left and right rotations is given below.

TreeNode* rotateLeft(TreeNode* root) {
  TreeNode* newRoot = root->right;
  root->right = newRoot->left;
  newRoot->left = root;
  // Update information for related nodes
  updateHeight(root);
  updateHeight(newRoot);
  return newRoot;  // Return the new root node
}

TreeNode* rotateRight(TreeNode* root) {
  TreeNode* newRoot = root->left;
  root->left = newRoot->right;
  newRoot->right = root;
  updateHeight(root);
  updateHeight(newRoot);
  return newRoot;
}

For this sample code, when calling it, save root's parent pre. The method returns a pointer to the new root, so it is enough to make pre point to the new root.

Four Cases of Balance Violation

Although different binary balanced trees have different definitions, their only differences are the information maintained at each node and the information updated after rotations. A binary balanced tree can lose balance in only the following four ways. Balance adjustments use only left and right rotations. We first introduce the four cases and then compare the different binary balanced trees.

LL case: the left subtree of T's left child is too long, causing a balance violation.

Adjustment: right-rotate node T.

RR case: as in the LL case, the right subtree of T's right child is too long, causing a balance violation.

Adjustment: left-rotate node T.

LR case: the right subtree of T's left child is too long, causing a balance violation.

Adjustment: first left-rotate node L to make it an LL case, then right-rotate node T.

RL case: as in the LR case, the left subtree of T's right child is too long, causing a balance violation.

Adjustment: first right-rotate node R to make it an RR case, then left-rotate node T.