Alumpath
Back to COMS W3134 – Data Structures - AVL Tree Dictionary Implementation
Columbia University Logo

Columbia University - COMS W3134 – Data Structures

AVL Tree Dictionary Implementation

Assignment Problem:

Implement a dictionary (key-value store where keys are typically strings and are unique) using an AVL Tree data structure in Java. The implementation should support insert, delete, search, and an in-order traversal to print all words (keys) in sorted order. Ensure AVL balance properties are maintained through rotations.

Our Suggested Approach

Understand AVL Trees:

  • Self-balancing Binary Search Tree (BST).
  • For every node, the height difference between its left and right subtrees (balance factor) is at most 1 (i.e., -1, 0, or 1).
  • Rotations (single or double) are performed after insertions or deletions if the balance factor of any node becomes +/-2, to restore the AVL property.

Node Structure (AVLNode):

  • key (e.g., String for dictionary words)
  • value (associated with the key, e.g., definition or count)
  • left child (AVLNode)
  • right child (AVLNode)
  • height (integer, height of the subtree rooted at this node)

Core AVL Tree Operations:

  1. getHeight(AVLNode node): Returns the height of a node (0 if null, otherwise node.height).
  1. getBalanceFactor(AVLNode node): Returns getHeight(node.left) - getHeight(node.right) (0 if node is null).
  1. updateHeight(AVLNode node): Recalculates and updates the height of a node based on the heights of its children: 1 + Math.max(getHeight(node.left), getHeight(node.right)).
  1. Rotations:
  1. rightRotate(AVLNode y): Performs a right rotation around node y. Used when a tree is left-heavy.
  1. leftRotate(AVLNode x): Performs a left rotation around node x. Used when a tree is right-heavy.
  1. Insertion (insert(AVLNode node, String key, ValueType value) - Recursive):
  1. Standard BST insertion: If node is null, create a new node. If key < node.key, insert into left subtree. If key > node.key, insert into right subtree. (Handle key collision as per requirement - e.g., update value or disallow duplicates).
  1. After insertion, update the height of the current node.
  1. Calculate the balanceFactor of the current node.
  1. Rebalancing (if balanceFactor > 1 or < -1):
  1. Left-Left Case (balanceFactor > 1 and key < node.left.key): Perform one rightRotate(node).
  1. Right-Right Case (balanceFactor < -1 and key > node.right.key): Perform one leftRotate(node).
  1. Left-Right Case (balanceFactor > 1 and key > node.left.key): Perform leftRotate(node.left) then rightRotate(node).
  1. Right-Left Case (balanceFactor < -1 and key < node.right.key): Perform rightRotate(node.right) then leftRotate(node).
  1. Return the (potentially new) root of the modified subtree.
  1. Deletion (delete(AVLNode node, String key) - Recursive):
  1. Standard BST deletion: Find the node. If node has 0 or 1 child, handle easily. If 2 children, replace with in-order successor (smallest in right subtree) or predecessor, then delete that successor/predecessor.
  1. After deletion (if node was actually deleted), update the height of the current node.
  1. Calculate balanceFactor and perform rebalancing rotations similar to insertion (but conditions might involve checking balance factors of children to determine single vs. double rotation).
  1. Return the (potentially new) root of the modified subtree.
  1. Search (search(AVLNode node, String key) - Recursive):

Standard BST search. Return the value if key is found, or null/exception if not.

  1. In-Order Traversal (inOrderTraversal(AVLNode node) - Recursive):

Traverse left subtree, visit (print/collect) current node's key, traverse right subtree. This will output keys in sorted order.

Dictionary Class (AVLTreeDictionary):

  • Contains the root (AVLNode) of the AVL tree.
  • Public methods (put(key, value), get(key), remove(key), printSortedKeys()) that call the recursive AVL operations starting from the root.

Illustrative Code Snippet

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
class AVLNode<V> {
    String key;
    V value;
    AVLNode<V> left;
    AVLNode<V> right;
    int height;

    AVLNode(String key, V value) {
        this.key = key;
        this.value = value;
        this.height = 1; // Leaf node height
    }
}

public class AVLTreeDictionary<V> {
    private AVLNode<V> root;

    private int height(AVLNode<V> node) {
        return (node == null) ? 0 : node.height;
    }

    private int getBalance(AVLNode<V> node) {
        return (node == null) ? 0 : height(node.left) - height(node.right);
    }

    private void updateHeight(AVLNode<V> node) {
        if (node != null) {
            node.height = 1 + Math.max(height(node.left), height(node.right));
        }
    }

    private AVLNode<V> rightRotate(AVLNode<V> y) {
        AVLNode<V> x = y.left;
        AVLNode<V> T2 = x.right;

        // Perform rotation
        x.right = y;
        y.left = T2;

        // Update heights
        updateHeight(y);
        updateHeight(x);
        return x; // New root of this subtree
    }

    private AVLNode<V> leftRotate(AVLNode<V> x) {
        AVLNode<V> y = x.right;
        AVLNode<V> T2 = y.left;

        // Perform rotation
        y.left = x;
        x.right = T2;

        // Update heights
        updateHeight(x);
        updateHeight(y);
        return y; // New root of this subtree
    }

    public void put(String key, V value) {
        root = insertRec(root, key, value);
    }

    private AVLNode<V> insertRec(AVLNode<V> node, String key, V value) {
        // 1. Standard BST insert
        if (node == null) {
            return new AVLNode<>(key, value);
        }
        int compare = key.compareTo(node.key);
        if (compare < 0) {
            node.left = insertRec(node.left, key, value);
        } else if (compare > 0) {
            node.right = insertRec(node.right, key, value);
        } else { // Duplicate key, update value (or handle as error)
            node.value = value;
            return node;
        }

        // 2. Update height of current node
        updateHeight(node);

        // 3. Get balance factor
        int balance = getBalance(node);

        // 4. Rebalance if needed (4 cases)
        // Left Left Case
        if (balance > 1 && key.compareTo(node.left.key) < 0) {
            return rightRotate(node);
        }
        // Right Right Case
        if (balance < -1 && key.compareTo(node.right.key) > 0) {
            return leftRotate(node);
        }
        // Left Right Case
        if (balance > 1 && key.compareTo(node.left.key) > 0) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }
        // Right Left Case
        if (balance < -1 && key.compareTo(node.right.key) < 0) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }
        return node; // Return unchanged (or rotated) node
    }

    // public V get(String key) { /* Standard BST search */ return null;}
    // public void remove(String key) { root = deleteRec(root, key); }
    // private AVLNode<V> deleteRec(AVLNode<V> node, String key) { /* Complex: BST delete + rebalancing */ return node;}
    // private AVLNode<V> minValueNode(AVLNode<V> node) { /* For deletion: find in-order successor */ return node;}


    public void printSortedKeys() {
        inOrderRec(root);
        System.out.println();
    }

    private void inOrderRec(AVLNode<V> node) {
        if (node != null) {
            inOrderRec(node.left);
            System.out.print(node.key + " ");
            inOrderRec(node.right);
        }
    }
    // main method for testing...
}

Explanation & Key Points

AVL Node Structure

Each node in an AVL tree stores a key, an associated value, references to left and right children, and its height. The height is crucial for calculating balance factors.

Balance Factor and Height Updates

The balance factor of a node is the height of its left subtree minus the height of its right subtree. It must be -1, 0, or 1. After any insertion or deletion, node heights must be updated bottom-up from the modified leaf.

Rotations (Single and Double)

If an insertion or deletion causes a node's balance factor to become +/-2, rotations are performed to rebalance the tree. There are four cases: Left-Left (LL), Right-Right (RR) require a single rotation (right or left, respectively). Left-Right (LR) and Right-Left (RL) require a double rotation (e.g., LR needs a left rotation on the left child, then a right rotation on the current node).

Insertion Process

Insertion follows standard BST logic. After inserting the new node, the algorithm traverses back up to the root, updating heights and checking balance factors at each node. If an imbalance is detected, the appropriate rotation(s) are performed.

Deletion Process (Conceptual)

Deletion also starts like BST deletion. Finding the node to delete, handling cases with 0, 1, or 2 children (often replacing with in-order successor if two children). After deletion, the path from the deleted node's parent to the root is re-traversed, updating heights and performing rebalancing rotations as needed. Deletion rebalancing can be more complex than insertion.

In-Order Traversal

Performing an in-order traversal (Left subtree, Root, Right subtree) on an AVL tree (or any BST) visits the nodes in ascending order of their keys, which is useful for printing the dictionary's words sorted alphabetically.

Key Concepts to Master

Binary Search Trees (BST)Self-Balancing TreesAVL Tree PropertiesBalance FactorTree Rotations (Single: LL, RR; Double: LR, RL)Recursive AlgorithmsHeight of a Tree/NodeDictionary ADTTime Complexity (O(log n) for insert, delete, search)

How Our Tutors Elevate Your Learning

  • Visualizing Rotations: Drawing out the four rotation cases (LL, RR, LR, RL) and how they restore balance is extremely helpful.
  • Recursive Implementation: Guiding you through the recursive structure of insertRec and deleteRec, particularly how the return values are used to update parent pointers after rotations.
  • Height and Balance Factor Logic: Ensuring the height() and getBalance() methods are implemented correctly and used at the right places in insertRec and deleteRec.
  • Debugging Imbalances: Helping you trace the state of the tree (node heights, balance factors) when an imbalance occurs to identify if rotations are being applied correctly.
  • Deletion Complexity: Walking through the different cases for BST deletion and how rebalancing applies after each, as this is often the trickiest part of AVL implementation.
  • Testing Strategies: Suggesting ways to test your AVL tree thoroughly, including sequences of insertions and deletions that trigger all rotation cases.

Need Personalized Help with Your Assignment?

Our human experts provide tailored guidance for your specific course assignments, helping you understand concepts and succeed.