← BIT 201 Data Structures and Algorithms
Trees, Graphs and Hashing
Notes
Hierarchical and connected data
A tree represents a hierarchy of nodes connected by edges, with a root and no cycles. In a rooted tree, each non-root node has one parent, and nodes without children are leaves. A binary search tree places smaller keys in the left subtree and larger keys in the right subtree under a consistent duplicate policy. A graph models more general relationships between vertices and edges. Directed edges represent one-way relationships, while weighted edges attach quantities such as distance, cost or travel time.
Traversal and key lookup
Traversal systematically visits nodes. Breadth-first search uses a queue to explore successive levels and can find shortest paths measured in edges in an unweighted graph. Depth-first search explores one branch before backtracking and can use a stack. A hash table computes a bucket from a key using a hash function. Different keys can produce the same bucket, called a collision. Chaining stores multiple entries in a bucket. Good distribution and controlled load factors support fast average lookup, but do not guarantee constant worst-case performance.
Practical example
A Kisumu wholesale shop hashes supplier identifiers into 10 buckets using the remainder after division by 10. Identifiers 142 and 152 both produce bucket 2, so a chained implementation stores both entries there and compares full identifiers during retrieval. With 25 suppliers, the load factor is 25 divided by 10 = 2.5 entries per bucket on average. The shop also represents delivery stops as a graph. A route with two edges may be shorter in stop count but longer in kilometres than a three-edge route, so weighted distance needs a suitable shortest-path algorithm.
Quiz
1. Why must a hash lookup compare complete keys inside a bucket?
2. Which method finds minimum edge-count routes in an unweighted graph?
3. What is the load factor for 25 entries and 10 buckets?
Sign in to submit and securely grade your quiz.