Like hash tables, binary search trees are fast lookup data structures for organizing key value pairs and implement the data dictionary operations. In addition to providing insert, search, and delete, binary tree supports efficient querying such as finding minimum and maximum, successor, and predecessor. When using balanced binary search trees, insert and search operations have a worst-case runtime complexity of O(log n). This is a big theoretical improvement over the worst-case scenario of a hash table, which is O(n).
The structure of a binary tree is composed of a series of nodes connected together via pointers.Figure 3.8shows the fundamental relation between nodes. Each node can have a maximum of two child nodes, a left one and a right one.
Each node (except the top-level node) also has exactly one parent:
Figure 3.8: Showing a simple binary tree relation
Figure 3.9shows some more terminology applied to binary trees. In this diagram...