Binary Search Tree (BST) and Balanced Trees

[ Last Updated: 2024-05-15 ]

Properties

A Binary Search Tree is a tree-based data structure that satisfies the following properties:

• If the left subtree is not empty, the values of all nodes in the left subtree are less than the value of the root node.
• If the right subtree is not empty, the values of all nodes in the right subtree are greater than the value of the root node.
• The left and right subtrees must also be binary search trees.

A BST maintains an ordered dynamic set. A balanced BST can maintain the time complexity of basic operations like insertion and deletion at $O(\log_2 n)$, which is significantly more efficient than a standard linear queue.

Basic Operations

Find Maximum / Minimum Continuously follow the left child pointers until a node has no left child (for minimum) or follow right child pointers until a node has no right child (for maximum).

Find Predecessor / Successor

• Predecessor: If the left subtree is not empty, return the maximum value (rightmost node) in the left subtree. If empty, move up to the first ancestor where the path goes from a left child to its parent.
• Successor: Vice versa.

In-order Traversal

1. If the left subtree is not empty, recursively call the traversal on the left subtree.
2. Print the root node value.
3. If the right subtree is not empty, recursively call the traversal on the right subtree.

Search / Delete a node with value k

• Search: Compare $k$ with the root. If $k < \text{root}$, go left; if $k > \text{root}$, go right.
• Delete:
  • If it is a leaf node, delete it directly.
  • If it has only one child, the child replaces the deleted node's position.
  • If it has two children, find the predecessor (max value in left subtree), swap its value with $k$, then delete the node at the new position.

Find the i-th node Using size(root) to record the number of nodes in a subtree:

1. Let $a = \text{size(left subtree)}$.
2. If $a = i - 1$, return current node.
3. If $a \geq i$, search in the left subtree.
4. If $a < i - 1$, search in the right subtree looking for the $(i - a - 1)$-th node.

Balanced Trees

As mentioned, a balanced BST has a complexity of $\log_2 n$. However, if the tree is unbalanced (e.g., one side is much taller than the other) or degenerates into a linked list, the efficiency of the BST is lost. To ensure the height stays around $\log_2 n$, we must maintain the tree's balance.

Examples of Implementations:

1. Red-Black Tree

Properties:

• Every node is either Red or Black.
• The root is always Black.
• Red nodes cannot have Red children (no two Reds in a row).
• Every path from a node to its descendant NULL nodes must contain the same number of Black nodes.

Proof: A Red-Black tree with $n$ nodes has a height no greater than $2\log_2(n+1)$. Since every path has the same number of Black nodes and Red nodes cannot be adjacent, the longest path (alternating Red/Black) is at most twice as long as the shortest path (all Black).

2. AVL Tree

Introduces a Balance Factor (height of left subtree - height of right subtree). For a tree to be balanced, this factor must be between -1, 0, or 1. If it exceeds this range, "rotations" are required.

3. Scapegoat Tree

Uses a balance coefficient $\alpha$ (typically around 0.7). If a subtree's size relative to its parent exceeds $\alpha$, the subtree is "scapegoated" and completely rebuilt into a perfectly balanced tree.

4. Treap (Tree + Heap)

Assigns a random priority to each node. It maintains the BST property for the key and the Heap property for the priority (usually using rotations).

Note: Different algorithms have different definitions of "balanced." A tree might be unbalanced in AVL but perfectly acceptable in a Scapegoat tree.

Rebalancing: Rotations

Rotations take $O(1)$ time.

Left Rotation (x - y): $y$ becomes the parent of $x$. $x$ takes $y$'s left child as its new right child.

Right Rotation (x - y): $y$ becomes the parent of $x$. $x$ takes $y$'s right child as its new left child.

Implementation: BST via AVL Tree

I implemented the insert logic for an AVL tree. The delete logic is omitted for brevity.

class TreeNode:
    def __init__(self, key):
       self.key = key
       self.left = None
       self.right = None
       self.height = 1
 
class AVLBST:
    def __init__(self):
        self.root = None
 
    def search(self, key):
        return self.searching(self.root, key)
 
    def searching(self, currentroot, key):
        if not currentroot: return False
        if currentroot.key == key:
            return True
        if key < currentroot.key:
            return self.searching(currentroot.left, key)
        return self.searching(currentroot.right, key)
 
    def getheight(self, root):
        if root is None:
            return 0
        return root.height
 
    def avlfactor(self, root):
        if root is None:
            return 0
        return self.getheight(root.left) - self.getheight(root.right)
 
    def insert(self, key):
        self.root = self.inserting(self.root, key)
 
    def inserting(self, currentroot, key):
        if currentroot is None:
            return TreeNode(key)
        if key < currentroot.key:
            currentroot.left = self.inserting(currentroot.left, key)
        else:
            currentroot.right = self.inserting(currentroot.right, key)
            
        currentroot.height = 1 + max(self.getheight(currentroot.left), self.getheight(currentroot.right))
 
        balance = self.avlfactor(currentroot)
        
        # Left Left Case
        if balance > 1 and key < currentroot.left.key:
            return self.rightrotate(currentroot)
        
        # Right Right Case
        if balance < -1 and key > currentroot.right.key:
            return self.leftrotate(currentroot)
            
        # Left Right Case
        if balance > 1 and key > currentroot.left.key:
            currentroot.left = self.leftrotate(currentroot.left)
            return self.rightrotate(currentroot)
            
        # Right Left Case
        if balance < -1 and key < currentroot.right.key:
            currentroot.right = self.rightrotate(currentroot.right)
            return self.leftrotate(currentroot)
 
        return currentroot      
 
    def leftrotate(self, x):
        y = x.right
        T2 = y.left
        y.left = x
        x.right = T2
        x.height = 1 + max(self.getheight(x.left), self.getheight(x.right))
        y.height = 1 + max(self.getheight(y.left), self.getheight(y.right))
        return y
 
    def rightrotate(self, x):
        y = x.left
        T2 = y.right
        y.right = x
        x.left = T2
        x.height = 1 + max(self.getheight(x.left), self.getheight(x.right))
        y.height = 1 + max(self.getheight(y.left), self.getheight(y.right))
        return y
 
    def treeprint(self):
        self.subtreeprint(self.root)
        
    def subtreeprint(self, currentroot):
        if currentroot:
          print("(", end="")
          self.subtreeprint(currentroot.left)
          print(currentroot.key, end="")
          self.subtreeprint(currentroot.right)
          print(")", end="")
 
# Testing
MyTree = AVLBST()
for val in [10, 20, 30, 40, 50, 60, 70]:
    MyTree.insert(val)
 
MyTree.treeprint()
x = int(input("\nEnter key to search: "))
if MyTree.search(x): 
    print(str(x) + " is in the Tree")
else: 
    print(str(x) + " is not in the Tree")
    
 

-Untitled Penguin 2024/5/12