concept binary search tree in category algorithms

appears as: binary search trees, binary search tree, binary search trees, A binary search tree
Algorithms and Data Structures in Action

This is an excerpt from Manning's book Algorithms and Data Structures in Action.

One could think that heaps needs to be binary trees: after all, binary search trees are the most common kind of trees, intrinsically associated with ordering. It turns out that there is no reason to keep our branching factor[10] fixed and equal to 2. On the contrary, we can use any value greater than 2, and use the same array representation for the heap.

Treap[1] is just the portmanteau[2] of tree and heap: binary search trees, in fact, offer the best average performance across all standard operations: insert, remove and search (and also min and max).

Figure 6.3 A more compact representation of a trie. This example trie contains the same elements as the binary search tree in figure 6.1.