Trees
structure
Binary Search Tree
Red Black Trees
another red black tree
small rb tree
AVL Trees
Is a binary search tree that is height balanced; for each node $x$, the heights of the lef and right subtrees of $x$ differ by at most 1.
To implement such a tree, maintain an extra attribute $h$ in each node such that $x.h$ is the height of node $x$.