Study Notes on Tree Structures: Binary Trees, BST, AVL, Heaps, and Multi-way Trees

Introduction to Tree Data Structures

Definition: A tree is a nonlinear hierarchical data structure that consists of nodes connected by edges. Unlike linear data structures (arrays, linked lists, stacks, and queues), trees represent data in a branched, hierarchical manner.
Conceptual Structure: Each tree consists of a root node from which every other element in the tree can be accessed. Starting from this root, each node contains zero or more nodes connected to it, which are referred to as its children.
Non-Linear Nature: Because it is hierarchical, a tree does not have a single linear sequence. It allows for representing relationships such as fold structures, organizational charts, or biological taxonomies.

Anatomy and Terminology of a Tree

Root Node:
- The topmost node of a tree hierarchy.
- It is the first node created during the construction of the tree.
- All elements are accessed starting from this node.
- Example: In a provided tree example with elements like 50, 20, 45, 11, 46, and 15, the node containing element 50 is the root node.
Parent Node:
- A node that references another node (the current node).
- Example: Node 50 is the parent of 20 and 45. Node 20 is the parent of 11, 46, and 15. Node 45 is the parent of 30 and 78.
Child Node:
- Nodes that a parent node points to using references.
- Example: 20 and 45 are children of root node 50. The nodes 11, 46, and 15 are children of node 20. Nodes 30 and 78 are specific children of node 45.
Edge:
- The reference or link through which a parent node is connected to a child node. In visual representations, every arrow connecting two nodes represents an edge.
Leaf Node:
- Nodes that do not have any children (terminal nodes).
- Example: Nodes 11, 46, 15, 30, and 78 are leaf nodes because they do not point to any subsequent nodes.
Internal Node:
- Nodes that have at least one child.
- Example: Nodes 50, 20, and 45 are internal nodes within the structure.
Height and Depth:
- Depth: The distance from the root to a specific node.
- Height: The maximum depth of the tree (the longest path from the root to a leaf).

Binary Tree Abstract Data Type (ADT)

Definition: A binary tree is a data structure where each node can have a maximum of 2 children.
Child Constraints: This means a node may have zero, one, or two children. These children are specifically identified by their positions: the left child and the right child.
Node Components: Each node in a binary tree contains:
1. Data/Item value.
2. Reference to the left child.
3. Reference to the right child.

Python Implementation of a Binary Tree Node

The following class structure represents a node in Python:

class BinaryTreeNode:
    def __init__(self, data):
        self.data = data
        self.leftChild = None
        self.rightChild = None

Logic: The constructor takes a data value, initializes the data field, and sets child references to None. Children are assigned later to build the tree.

Practical Code Example and Output

Building a tree with root 50, and children 20, 45, etc.:

node1 = BinaryTreeNode(50)
node2 = BinaryTreeNode(20)
node3 = BinaryTreeNode(45)
node4 = BinaryTreeNode(11)
node1.leftChild = node2
node1.rightChild = node3
node2.leftChild = node4

Output Observations:
- Root Node: 50
- Left child of 50: 20
- Right child of 50: 45
- Left child of 20: 11
- Leaf nodes like 11 return None for both children.

Types of Binary Trees

1. Full Binary Tree: A tree where every parent or internal node has either exactly two children or no children (zero children). No node has only one child.
2. Perfect Binary Tree: A binary tree where every internal node has exactly two children, and all leaf nodes reside at the same level.
3. Complete Binary Tree: Similar to a full binary tree but with two strict requirements:
1. Every level must be completely filled.
2. All leaf nodes must lean towards the left.
3. Note: A complete binary tree does not necessarily have to be a full binary tree; the last leaf element might not have a right sibling.
4. Degenerate (Pathological) Tree: A tree where every node has only a single child (either left or right). Structurally, it behaves like a linked list.
5. Skewed Binary Tree: A specialized degenerate tree dominated by one side.
- Left-skewed: All nodes have only left children.
- Right-skewed: All nodes have only right children.
6. Balanced Binary Tree: A binary tree where the difference between the height of the left and right subtree for every node is either 0 or 1.

Applications of Trees

General Tree Applications:
- Binary Search Trees (BSTs): Used for rapid searching (checking presence in a set).
- Heaps: Used for Heap Sort and Priority Queues.
- Tries: A modified tree used in modern routers to store and retrieve routing information.
- Databases: Use B-Trees and T-Trees for data storage and indexing.
- Compilers: Use Syntax Trees to validate the syntax of written code.
Binary Tree Specifics:
- Efficient data access.
- Router algorithms.
- Implementation of heap structures.

Tree Traversal Techniques

Concept: Traversing means visiting every node in the tree (e.g., to sum values or find the maximum). Unlike linear structures (array, stack) which have one way to read data, trees offer multiple paths.
Composition: Every tree is viewed recursively as a combination of a root node, a left subtree, and a right subtree.
Types of Traversal:
1. Inorder Traversal:
  1. Visit all nodes in the left subtree.
  2. Visit the root node.
  3. Visit all nodes in the right subtree.
  - Code logic: inorder(root.left), print(root.val), inorder(root.right).
2. Preorder Traversal:
  1. Visit the root node.
  2. Visit all nodes in the left subtree.
  3. Visit all nodes in the right subtree.
  - Code logic: print(root.val), preorder(root.left), preorder(root.right).
3. Postorder Traversal:
  1. Visit all nodes in the left subtree.
  2. Visit all nodes in the right subtree.
  3. Visit the root node.
  - Code logic: postorder(root.left), postorder(root.right), print(root.val).
Visualizing Inorder with a Stack: To remember the path (Left -> Root -> Right), recursion uses a call stack. For a root node 1 with left subtree (5, 12, 6) and right subtree 9, the inorder result is: $5 \rightarrow 12 \rightarrow 6 \rightarrow 1 \rightarrow 9$ .

Binary Search Trees (BST)

Purpose: A BST maintains a sorted list of numbers and allows for searching in $O(\log(n))$ time.
Core Properties:
1. All nodes in the left subtree are less than the root node.
2. All nodes in the right subtree are more than the root node.
3. Both subtrees must also be BSTs (recursive property).
Example of Invalid BST: If a root is 3 and its right child is 6, but the left child of 6 is 2, it is invalid because 2 is smaller than the root 3 yet exists in the right subtree.

BST Operations

Search:
- If value < root, search only the left subtree.
- If value > root, search only the right subtree.
- If value is found, propagate it up through recursion; else return NULL.
Insert:
- The algorithm follows the search path until it finds a NULL position (leaf child) and attaches the new node there.
- Crucial step: return node; at the end of the recursion ensures connections aren't lost as the function exits.
Deletion (Three Cases):
- Case 1 (Leaf Node): Simply remove the node.
- Case 2 (One Child): Replace the node with its child, then remove the original child node.
- Case 3 (Two Children):
  1. Find the Inorder Successor (the smallest value in the right subtree / leftmost leaf of the right child).
  2. Replace the node's value with the Inorder Successor's value.
  3. Delete the original Inorder Successor node.

BST Complexities

Operation	Best Case	Average Case	Worst Case
Search	$O(\log(n))$	$O(\log(n))$	$O(n)$
Insertion	$O(\log(n))$	$O(\log(n))$	$O(n)$
Deletion	$O(\log(n))$	$O(\log(n))$	$O(n)$

Space Complexity: $O(n)$ for all operations.
BST Applications: Multilevel indexing in databases, dynamic sorting, and managing virtual memory areas in the Unix kernel.

AVL Trees (Adelson-Velsky and Landis)

Definition: A self-balancing search tree where each node tracks a Balance Factor (BF).
Balance Factor (BF): The difference between the height of the left and right subtree.
- Formula: $\text{BF} = \text{Height(Left Subtree)} - \text{Height(Right Subtree)}$
- Property: For a balanced AVL tree, the BF of every node must be $-1$ , $0$ , or $+1$ .

AVL Rotations

Rotations interchange node positions to restore balance:

Left Rotate: Transforms a right-heavy arrangement towards the left.
Right Rotate: Transforms a left-heavy arrangement towards the right.
Left-Right (LR) Rotate: Performs a left rotation followed by a right rotation.
Right-Left (RL) Rotate: Performs a right rotation followed by a left rotation.

AVL Insertion and Rebalancing Logic

Insert node normally as a leaf (BF = 0).
Update heights and check BFs of ancestors.
If $BF > 1$ (Left Heavy):
- If newKey < leftChildKey: Right Rotate.
- Else: Left-Right Rotate.
If $BF < -1$ (Right Heavy):
- If newKey > rightChildKey: Left Rotate.
- Else: Right-Left Rotate.

AVL Complexities

Insertion, Deletion, and Search all operate in $O(\log(n))$ for all cases because the tree is always balanced.

Heaps in Python

Definition: A specialized complete binary tree where the root node is either the smallest or greatest element.
Types:
- Min-Heap: Parent nodes are always smaller than children; the root is the minimum.
- Max-Heap: Parent nodes are always greater than children; the root is the maximum.
Memory Representation: Though conceptualized as trees, heaps are stored as Arrays because they are complete.
- Root: Heap[0]
- Parent of Heap[i]: Heap[(i - 1) / 2]
- Left Child: Heap[(2 * i) + 1]
- Right Child: Heap[(2 * i) + 2]
heapq Module: Python's built-in module for Min-Heaps.
- heapify(list): Converts a list into a heap in-place.
- heappush(heap, element): Adds element and maintains heap property.
- heappop(heap): Removes and returns the smallest element (the root).
Applications: Priority queues, Dijkstra's Algorithm, and Heap Sort.

Multi-way Trees

Introduction: Also called multi-ary or generic trees. They allow each node to have more than two children ( $m$ children).
Characteristics:
- Originates from a Root Node.
- Leaf nodes can have any number of children (including zero).
- Highly flexible for modeling complex hierarchical relationships.
Types of Multi-way Trees:
- General Multi-way Trees: No limit on the number of children; used for directory structures.
- B-Trees: Self-balancing trees used extensively in databases and file systems to maintain efficient search/insert/delete operations.
- Ternary Trees: Specifically three children per node; used in language processing optimization.
- Quad Trees and Oct Trees: Used for spatial partitioning in computer graphics and GIS. Quad trees have 4 children; Oct trees have 8.
Significance:
- Versatility: Models varied hierarchies.
- Efficiency: B-trees manage massive datasets efficiently.
- Parsing: Essential for syntax analysis in compilers.
- Spatial Data: Critical for spatial indexing in GIS applications.