Comparing Storage Mechanisms

Array indexing provides rapid access speed but requires element shifting for insertions or modifications, reducing efficiency. Linked structures optimize update operations by simply adjusting references but demand sequential traversal for searches. Tree architectures bridge these gaps, offering balanced performance for retrieval and dynamic manipulation.

Binary Tree Fundamentals

A binary tree constrains each node to a maximum of two children designated as left and right. A Full Binary Tree is completely filled at every level, where the total nodes equal $2^n - 1$. A Complete Binary Tree fills levels top-down and left-to-right; if the final level is incomplete, its nodes must occupy the far-left positions without interruption.

Traversal Strategies

Three recursive methods dictate node processing order:

1. Pre-order: Process root, traverse left subtree, traverse right subtree.
2. In-order: Traverse left subtree, process root, traverse right subtree.
3. Post-order: Traverse left subtree, traverse right subtree, process root.

public class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) { this.value = val; }

    // Pre-order implementation
    void preOrder() {
        System.out.println(value);
        if (left != null) left.preOrder();
        if (right != null) right.preOrder();
    }

    // In-order implementation
    void inOrder() {
        if (left != null) left.inOrder();
        System.out.println(value);
        if (right != null) right.inOrder();
    }

    // Post-order implementation
    void postOrder() {
        if (left != null) left.postOrder();
        if (right != null) right.postOrder();
        System.out.println(value);
    }
}

Search and Modification Operations

Search logic depends on the specific traversal strategy employed. Deletion protocols vary based on the target node's degree:

• Leaf Node: Directly remove the reference from the parent.
• Single Child: Bypass the node by linking the parent directly to the child.
• Two Children: Find the smallest node in the right subtree (in-order successor), copy its value, and delete the successor.

public class BinaryTree {
    private TreeNode root;

    public void searchAndDelete(TreeNode node, int target) {
        if (node == null) return;
        
        // Check current node first
        if (node.value == target) {
            // Handle deletion logic here (complex implementation omitted)
            return;
        }
        
        // Recurse left and check result
        searchAndDelete(node.left, target);
    }
}

Sequential Tree Representation

Arrays can model tree structures efficiently for complete trees using mathematical index mapping:

• Left child index: 2 * i + 1
• Right child index: 2 * i + 2
• Parent index: (i - 1) / 2

This approach allows array-based traversals to mimic tree recursion.

Threading Techniques

Standard binary链表s contain null pointers that waste memory. Threading replaces these nulls with references to predecessor or successor nodes based on traversal order. Type flags distinguish between actual child pointers and threaded links.

enum NodeType { CHILD, THREAD }

class ThreadedNode {
    Object data;
    ThreadedNode left, right;
    NodeType leftType, rightType;
}

Heap Sort Algorithm

Heapsort utilizes a Max-Heap structure to achieve O(n log n) complexity regardless of input order. The algorithm repeatedly extracts the maximum element (root) and restores heap property for the remaining elements.

public static void heapSort(int[] arr) {
    int n = arr.length;

    // Build max heap
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // Extract elements
    for (int i = n - 1; i > 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        heapify(arr, i, 0);
    }
}

private static void heapify(int[] arr, int n, int i) {
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;

    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;

    if (largest != i) {
        int swap = arr[i];
        arr[i] = arr[largest];
        arr[largest] = swap;
        heapify(arr, n, largest);
    }
}

Huffman Coding Compression

Huffman coding constructs an optimal prefix-free code using symbol frequencies. Nodes are iteratively combined starting with the two lowest weights until a single tree remains. Bits traverse the path (0 for left, 1 for right) to form codes.

Node createHuffmanTree(List<Node> nodes) {
    while (nodes.size() > 1) {
        Collections.sort(nodes); // Sort by weight
        Node left = nodes.remove(0);
        Node right = nodes.remove(0);
        Node parent = new Node(left.weight + right.weight);
        parent.left = left;
        parent.right = right;
        nodes.add(parent);
    }
    return nodes.get(0);
}

Binary Search Trees (BST)

BSTs maintain sorted order where left descendants are smaller than the parent, and right descendants are larger. This facilitates efficient lookup, insertion, and deletion.

class BSTNode {
    int key;
    BSTNode left, right;
    
    void insert(BSTNode node) {
        if (node.key < key) {
            if (left == null) left = node;
            else left.insert(node);
        } else {
            if (right == null) right = node;
            else right.insert(node);
        }
    }
}

AVL Self-Balancing Trees

AVL trees enforce strict height balance (difference ≤ 1). Rotations correct imbalances caused by insertions:

• LL/RR: Single rotation.
• LR/RL: Double rotation.

class AVLNode extends BSTNode {
    int height;
    void rotateLeft() { /* ... */ }
    void rotateRight() { /* ... */ }
    void balance() {
        if (balanceFactor() > 1 || balanceFactor() < -1) {
            // Execute rotations based on shape
        }
    }
}

Multi-Way Search Trees

B-Trees increase branching factors to reduce depth. Keys distribute across all levels. B+ Trees store data exclusively in leaves linked sequentialyl, making them ideal for database indexes. B* Trees further improve space utilization by requiring higher occupancy rates.