Detailed Notes on Binary Search Trees (BSTs)

Definition of Binary Search Tree (BST)

• A binary tree in symmetric order.

• It can be either:

  • Empty

  • Two disjoint binary trees (left and right).

• Keys are ordered such that:

  • Each node's key is larger than all keys in its left subtree.

  • Each node's key is smaller than all keys in its right subtree.

Anatomy of a Binary Tree

• Structure consists of nodes with links to left and right children.

• Example keys: A, C, E, H, R, S, X

Operations on BSTs

Search

• Process:

  • If key < current node, go left.

  • If key > current node, go right.

  • If key == current node, search successful.

Insert

• Process:

  • If key < current node, go left.

  • If key > current node, go right.

  • If null link is reached, insert the new node.

Structure in Java

• A Node consists of:

  • Key and Value

  • References to left and right subtrees

• BST is a class composed of a root Node.

Get Operation

• Returns value associated with a key if found, else returns null.

• Cost: Number of comparisons equals depth of node.

Put Operation

• Associates a value with a given key:

  • If key exists, reset value.

  • If not, add a new node.

• Cost: Similar to Get operation.

Insertion Characteristics

• The shape of the BST is influenced by the order of insertion:

  • Best Case: Balanced tree

  • Worst Case: Degenerate tree (linked list)

• Average compares for search/insert: ~ 2 ln(N), where N is the number of distinct keys inserted.

Floor and Ceiling Operations

Floor

• The largest key ≤ a given key.

Ceiling

• The smallest key ≥ a given key.

Deletion in BSTs

General Method

• To delete a node with key:

  • Set its value to null (lazy deletion).

  • For true node removal, consider cases based on children:

  • No Children: Remove node by setting parent's link to null.

  • One Child: Link parent to child node.

  • Two Children: Find successor, delete the minimum in the right subtree.

Deleting Minimum

• Traverse left until a node without left child is found, then replace with right child.

BST Tree Characteristics

• Height of a random BST

  • Expected: ~ 4.311 ln(N)

  • Worst-case height is N-1.

Summary of Time Complexities

Closing Notes

• BST allows for efficient ordered operations on keys, maintaining a logarithmic performance average if balanced.

class Node {
    int key, value;
    Node left, right;
    Node(int key, int value) {
        this.key = key;
        this.value = value;
        left = right = null;
    }
}

class BST {
    Node root;

    // Insert operation
    public void insert(int key, int value) {
        root = insertRec(root, key, value);
    }

    private Node insertRec(Node root, int key, int value) {
        if (root == null) {
            root = new Node(key, value);
            return root;
        }
        if (key < root.key) {
            root.left = insertRec(root.left, key, value);
        } else if (key > root.key) {
            root.right = insertRec(root.right, key, value);
        } else { // Update value if the key already exists
            root.value = value;
        }
        return root;
    }

    // Search operation
    public Node search(int key) {
        return searchRec(root, key);
    }

    private Node searchRec(Node root, int key) {
        if (root == null || root.key == key) {
            return root;
        }
        return key < root.key ? searchRec(root.left, key) : searchRec(root.right, key);
    }

    // In-Order Traversal
    public void inorder() {
        inorderRec(root);
    }

    private void inorderRec(Node root) {
        if (root != null) {
            inorderRec(root.left);
            System.out.print(" " + root.key);
            inorderRec(root.right);
        }
    }

    // Find Minimum
    public Node findMin() {
        return findMinRec(root);
    }

    private Node findMinRec(Node root) {
        return root.left == null ? root : findMinRec(root.left);
    }

    // Find Maximum
    public Node findMax() {
        return findMaxRec(root);
    }

    private Node findMaxRec(Node root) {
        return root.right == null ? root : findMaxRec(root.right);
    }

    // Find Floor
    public Node floor(int key) {
        return floorRec(root, key);
    }

    private Node floorRec(Node root, int key) {
        if (root == null) return null;
        if (root.key == key) return root;
        return key < root.key ? floorRec(root.left, key) : (floorRec(root.right, key) != null ? floorRec(root.right, key) : root);
    }

    // Find Ceiling
    public Node ceiling(int key) {
        return ceilingRec(root, key);
    }

    private Node ceilingRec(Node root, int key) {
        if (root == null) return null;
        if (root.key == key) return root;
        return key > root.key ? ceilingRec(root.right, key) : (ceilingRec(root.left, key) != null ? ceilingRec(root.left, key) : root);
    }
}

This code defines a basic Binary Search Tree with methods for insertion, searching by key, in-order traversal, finding the minimum and maximum keys, as well as calculating the floor and ceiling for a given key.