COMP3830 Tree and Binary Search Tree Notes

Tree Structure: A tree is a non-linear data structure consisting of nodes. It has a hierarchical structure with a root node and child nodes.
- Root Node: The top node in a tree.
- Child Nodes: Nodes that are connected to a parent node.
- Leaf Nodes: Nodes with no children.
Binary Tree: A tree where each node can have at most two children, referred to as left and right children.
Binary Search Tree (BST): A special type of binary tree that maintains a sorted order.
- For each node, all elements in the left subtree are less than the node's key, and all elements in the right subtree are greater.

Height Definition: Height of a tree is the length of the longest path from the root to a leaf.
- Recursive Definition: Height of a tree T = 1 + max(height of left subtree, height of right subtree).
- Base Case: Height of an empty tree is -1.
- Example: If the binary tree has 7 levels, its height is 6.

Each node in the tree can be represented in a linear array.
- For a node at index i:
- Left child index = 2*i + 1
- Right child index = 2*i + 2
Advantages: Simple, easy to implement, all nodes accessed in constant time.
Disadvantages: Fixed size, inefficient for sparse trees.

Binary Search Tree Search Process:
- Start from root. If the target value is less than the node's value, move to the left child; if greater, move to the right child. Recur until the node is found or null is reached.
- Time Complexity: O(h), where h is the height of the tree.
Searching in Unordered Collections:
- Unordered Array: Use linear search. Time Complexity: O(n).
- Unordered Linked List: Similar to an unordered array; traverse list until the value is found.
Searching in Ordered Collections:
- Ordered Array: Use binary search. Time Complexity: O(log n).
- Ordered Linked List: Inefficient; linear search is still O(n).

Insertion: Follow the rules of BST to insert a node; start at the root and place it in the correct position based on its value.
Deletion: Can be done using two strategies:
1. Largest Previous Element: Replace the node with the largest node in its left subtree.
2. Smallest Next Element: Replace the node with the smallest node in its right subtree.
Finding Minimum/Maximum: The minimum element can be found by traversing to the leftmost node, and the maximum element can be found by traversing to the rightmost node.

Tree Structures: Crucial for organizing data in a hierarchical format.
Binary Search Trees: Enable efficient searching, insertion, and deletion operations.
Height Calculation: Important for understanding tree efficiency and performance.
Different Collection Types: Knowledge of searching mechanisms through arrays, linked lists, and binary trees is essential for algorithm design.