All items, except a privileged item called the root, have exactly one parent
In a binary tree, each node has at most two children (left and right)
A binary tree is either empty or consists of a root plus a left subtree and a right subtree, each of which can be considered as individual binary trees
Binary Search Trees
Definition
Sorted collections can also be represented as tree-like structures
Each node in the left subtree of a given node is less than that node
Each node in the right subtree of a given node is greater than that node
Can support logarithmic searches and insertions
Array Implementation
Elements are stored as nodes by level in the array
Each node comprises a left pointer, the data and a right pointer
The pointers contain the array index of a node.
-1 indicates a null pointer
The index of the root node is stored in the variable Root
Deletion
Case 1: The Node is a Leaf (No Children)
Since the node has no descendants, removing it does not break any structural relationships in the rest of the tree
Sever the link from the parent node by setting its corresponding pointer to NULL
Case 2: The Node Has One Child
When the target node has only a single child (left or right), that child and its entire subtree must be preserved
Bypass the target node, and connect the target node’s parent directly to the target node’s only child
Case 3: The Node Has Two Children
To resolve this, you must find a valid replacement node to occupy the vacant slot
To preserve the sorted order of the BST, the replacement node must be one of two candidates:
Inorder Successor: The smallest value in the right subtree (go right once, then go left as far as possible)
Inorder Predecessor: The largest value in the left subtree (go left once, then go right as far as possible)
Step 1: Find the minimum value node in the target’s right subtree.
Step 2: Copy that successor node’s value into the target node.
Step 3: Recursively delete the original successor node from the right subtree. Because it was the minimum value, it is guaranteed to have at most one child, reducing this step to Case 1 or Case 2.
Hash Table
Definition
A hash table is a data structure that stores data at an index determined by a hash function rather than sequentially.
Purpose: Fast searching (typically O(1) average).
Hash Function
A hash function converts a key into an array index.
Properties of a good hash function:
Fast to compute
Produces valid indices
Distributes items uniformly
Minimises collisions
Collision
A collision occurs when two different keys hash to the same location.
Linear Probing
When collision occurs:
Check the next slot
Continue until an empty slot is found
Wrap around when reaching the end
Searching with Linear Probing
Compute hash.
If slot empty → Not found.
If key matches → Found.
If not, search for the next slot.
Wrap around.
Stop when:
Key found
Empty slot encountered
Returned to starting index
Advantages
Simple
No extra memory
Disadvantages
Primary clustering
Performance deteriorates as table fills
Chaining (Separate Lists)
Each array entry stores a linked list.
If collision occurs:Insert into linked list.
Searching:
Compute hash.
Go to the linked list.
Perform linked list search.
Advantages
Faster than linear probing when many collisions occur.
