Data Structure Visualizer -- BST, AVL Tree, and Heap Operations Animated

How Binary Search Trees Work

A Binary Search Tree (BST) is a tree data structure where each node has at most two children. The key property is that for any node, all values in the left subtree are less than the node's value, and all values in the right subtree are greater.

Insert Operation

To insert a value, start at the root and compare. If the value is less than the current node, go left; if greater, go right. Repeat until you find an empty spot and insert the new node there.

Delete Operation

Deleting has three cases:

• Leaf node: Simply remove it.
• One child: Replace the node with its child.
• Two children: Find the in-order successor (smallest node in right subtree), copy its value to the current node, then delete the successor.

Search Operation

Start at the root and compare the target value with the current node. Go left if smaller, right if larger. If you find the value, return success. If you reach a null node, the value doesn't exist.

Complexity: In a balanced BST, operations are O(log n). However, in the worst case (inserting sorted data), the tree degrades to a linked list with O(n) operations. This is why AVL trees exist.

How AVL Trees Work (Self-Balancing BST)

An AVL tree is a BST that automatically maintains balance. Each node tracks its height, and after every insert or delete, the tree checks if any node has become unbalanced (left and right subtree heights differ by more than 1). If so, it performs rotations to restore balance.

Balance Factor

Balance Factor = Height(Left Subtree) - Height(Right Subtree). A node is balanced if its balance factor is -1, 0, or 1.

Rotation Types

• Left Rotation (LL): Used when the right subtree is too heavy and the imbalance is in the right-right path.
• Right Rotation (RR): Used when the left subtree is too heavy and the imbalance is in the left-left path.
• Left-Right Rotation (LR): Used when the left subtree is too heavy but the imbalance is in the left-right path. Perform left rotation on the left child, then right rotation on the current node.
• Right-Left Rotation (RL): Used when the right subtree is too heavy but the imbalance is in the right-left path. Perform right rotation on the right child, then left rotation on the current node.

Guarantee: AVL trees ensure O(log n) time for insert, delete, and search, no matter the insertion order. The trade-off is extra bookkeeping (height tracking) and more rotations.

How Heaps Work

A heap is a complete binary tree stored as an array. Heaps satisfy the heap property:

• Min Heap: Every parent is smaller than or equal to its children. The root is the minimum element.
• Max Heap: Every parent is larger than or equal to its children. The root is the maximum element.

Array Representation

Heaps are typically stored in arrays. For a node at index i:

• Left child is at index 2*i + 1
• Right child is at index 2*i + 2
• Parent is at index floor((i - 1) / 2)

Insert Operation (Heapify-Up)

Add the new element at the end of the array. Then "bubble up" by comparing with the parent. If the heap property is violated, swap with the parent and repeat until the property is restored.

Delete Operation (Heapify-Down)

Typically, you delete the root (min or max). Replace the root with the last element in the array, then "bubble down" by comparing with children. Swap with the smaller child (min heap) or larger child (max heap) until the heap property is restored.

Use Cases: Heaps are perfect for priority queues. Insert and delete both run in O(log n) time. Finding the min/max is O(1) since it's always at the root.

Data Structure Comparison

Note: Heaps are not optimized for search. Use them when you only need to access the min/max element quickly. BSTs and AVL trees provide fast search capabilities.

Privacy & Security

This data structure visualizer runs entirely in your browser. No data is transmitted to any server. All tree operations and visualizations are computed locally using JavaScript and Canvas. Your exploration of data structures is completely private.