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).
Getting Started with Binary Search Trees
Binary Tree Structure
The structure of a binary tree is composed of a series of nodes connected together via pointers. Figure 3.8 shows the fundamental relation...
