二叉查找树

左子树的值小于根节点的值，右子树的值全部大于根节点的值；左右子树分别都是一颗二叉查找树。（递归定义），缺点，可能退化形成单链表，此时搜索效率降低为 O(n)

平衡二叉查找树

平衡二叉树, 树上任一结点的左子树和右子树的高度之差不超过1

红黑树

红黑树，任何一个节点都有颜色，黑色或者红色，根节点是黑色的，空节点被认为是黑色的，父子节点之间不能出现两个连续的红节点，任何一个节点向下遍历到其子孙的任何子节点，所经过的黑节点个数必须相等。红黑树只追求近似平衡，所以在插入与删除节点时，翻转次数远远少于平衡树。