🔁Data Structures Unit 5 Review

A Binary Search Tree (BST) is built from nodes that each have at most two children: left and right. The core rule is simple: every value in the left subtree is less than the node, and every value in the right subtree is greater. This ordering property is what makes searching efficient, since you can eliminate half the tree at each step.

AVL Trees solve a major BST weakness. A regular BST can become lopsided (imagine inserting 1, 2, 3, 4, 5 in order), which kills performance. AVL trees are self-balancing BSTs that track a balance factor for each node, defined as the height of the left subtree minus the height of the right subtree. Whenever an insertion or deletion causes any node's balance factor to fall outside the range [-1, 1], the tree performs rotations to restore balance:

Left rotation: fixes right-heavy imbalance
Right rotation: fixes left-heavy imbalance
Left-right rotation: fixes left-child-right-heavy imbalance (double rotation)
Right-left rotation: fixes right-child-left-heavy imbalance (double rotation)

Heaps are complete binary trees that satisfy the heap property. In a Max Heap, every node's value is greater than or equal to its children's values, so the maximum sits at the root. In a Min Heap, every node's value is less than or equal to its children's values, so the minimum sits at the root.

Heaps are commonly implemented using an array rather than linked nodes. The parent-child relationships are maintained purely through index math:

Parent of node at index $i$ : $\lfloor(i-1)/2\rfloor$
Left child: $2i + 1$
Right child: $2i + 2$

This array-based layout is memory-efficient and cache-friendly since no pointers are needed.

Tree-based data structures, Binary Search Tree - Basics Behind

Efficiency of tree operations

Operation	BST (Average)	BST (Worst)	AVL Tree	Heap
Search	$O(\log n)$	$O(n)$	$O(\log n)$	$O(n)$
Insertion	$O(\log n)$	$O(n)$	$O(\log n)$	$O(\log n)$
Deletion	$O(\log n)$	$O(n)$	$O(\log n)$	$O(\log n)$
Find min/max	$O(n)$	$O(n)$	$O(\log n)$	$O(1)$

The BST worst case of $O(n)$ happens when the tree degenerates into a linked list (all nodes on one side). That's exactly the problem AVL trees fix by guaranteeing balance.

Heaps give you $O(1)$ access to the min or max (it's always at the root), but they're not designed for general search. The heap property only guarantees a parent-child ordering, not a left-right ordering like a BST, so you can't prune your search path.

Heapify up (used during insertion): place the new element at the end of the array, then swap it upward with its parent until the heap property is restored.
Heapify down (used during root deletion): replace the root with the last element, then swap it downward with the appropriate child until the heap property is restored.

Tree-based data structures, data structures - AVL tree such that each insert causes rotation (single or double) - Computer ...

Applications of tree structures

Hierarchical Data Representation is the most intuitive use of trees. File systems model directories as internal nodes and files as leaves. XML/HTML documents nest elements inside each other, forming a tree. Organization charts map reporting relationships the same way. Trees naturally capture any data with parent-child relationships.

Expression Evaluation uses Binary Expression Trees. Leaf nodes hold operands (numbers or variables), and internal nodes hold operators (+, -, *, /). For example, the expression $(3 + 5) * 2$ becomes a tree with * at the root, + as the left child (with leaves 3 and 5), and 2 as the right child. Evaluating the tree with a post-order traversal processes operands before their operator, which naturally respects order of operations.

Decision Making uses Decision Trees where each internal node represents a condition (e.g., "Is temperature > 30°?") and each leaf represents an outcome or classification. You traverse from the root, following branches based on your answers, until you reach a leaf. These are foundational in machine learning for classification tasks.

Implementation of tree algorithms

Traversal algorithms define the order in which you visit every node. Each has distinct use cases:

Pre-order (root, left, right): useful for copying a tree or generating a prefix expression
In-order (left, root, right): on a BST, this visits nodes in sorted ascending order
Post-order (left, right, root): useful for deleting a tree (children before parent) or evaluating expression trees
Level-order (breadth-first): visits nodes level by level using a queue; useful for finding the shortest path or printing the tree by depth

Pre-order, in-order, and post-order are typically implemented with recursion (or an explicit stack). Level-order uses a queue: enqueue the root, then repeatedly dequeue a node, process it, and enqueue its children.

Balancing algorithms in AVL trees trigger after every insertion or deletion. The process works like this:

Perform the standard BST insertion or deletion
Walk back up the tree to the root, updating each ancestor's balance factor
At the first node where the balance factor becomes +2 or -2, determine the rotation case
Apply the appropriate rotation (single or double) to restore balance

Memory considerations matter in pointer-based tree implementations. Each node is dynamically allocated and holds pointers to its children (and sometimes its parent). When deleting nodes, you need to deallocate memory to prevent leaks. For performance-critical applications, memory pools or custom allocators can reduce allocation overhead and fragmentation compared to calling malloc/new for every individual node.

🔁Data Structures Unit 5 Review