A self-balancing binary search tree in which the heights of the two child subtrees at any node differ by at most one.