Self-balancing binary search tree

In computer science, a self-balancing (or height-balanced) binary search tree is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions.

These structures provide efficient implementations for mutable ordered lists, and can be used for other abstract data structures such as associative arrays, priority queues and sets.

The red–black tree, which is a type of self-balancing binary search tree, was called symmetric binary B-tree and was renamed but can still be confused with the generic concept of self-balancing binary search tree because of the initials.

Most operations on a binary search tree (BST) take time directly proportional to the height of the tree, so it is desirable to keep the height small. A binary tree with height h can contain at most 2⁰+2¹+···+2^h = 2^h+1−1 nodes. It follows that for a tree with n nodes and height h:

${\displaystyle n\leq 2^{h+1}-1}$

And that implies:

${\displaystyle h\geq \lceil \log _{2}(n+1)-1\rceil \geq \lfloor \log _{2}n\rfloor }$.

...
Wikipedia