Characteristics of Binary Search Trees

1. Ordering

A binary search tree can serve as an implementation of a lookup table.

Our purpose in using a binary search tree is to immediately get the value by looking up the key. minimum, maximum, successor, predecessor, floor, ceil, rank (which element ranks where), and select (which element is the nth one) are all manifestations of the ordering property of binary search trees.

2. Limitations

Binary search trees have limitations in time performance.

As shown in the figure below, with the same element nodes, two different binary search trees can be formed, both satisfying the definition:

A binary search tree may degenerate into a linked list. Correspondingly, the search operation of a binary search tree is related to the height of the tree, and at this point the height of the tree is its number of nodes n. Meanwhile, all corresponding algorithms of the binary search tree degenerate to O(n) level.

other extensions