二叉树
二叉树既可以用链式存储，也可以用数组顺序存储。除了叶子节点之外的每个节点都有左右两个节点的二叉树是满二叉树。除了叶子节点都靠左排列之外，其他层的节点个数都达到最大的二叉树是完全二叉树。数组顺序存储比较适合完全二叉树。前、中、后序遍历操作的时间复杂度是O(n)。
二叉查找树
二叉查找树是一种常用的二叉树。在树种的任意一个节点，其左子树中的每个节点的值都要小于这个节点的值，而右子树节点的值都大于这个节点的值。它支持快速插入、删除、查找操作，各个操作的时间复杂度和树的高度成正比，理想情况下时间复杂度是O(logn)。
查找
取根节点，如果它等于要查找的数据就返回，如果要查找的数据比根节点小，就在左子树中递归查找，否则在右子树中递归查找。
插入
插入的数据比节点的数据大且右子树为空，则插入右子节点。若不为空，则遍历右子树，查找插入位置。若插入的数据比节点数据小则在左子树中递归。
删除
- 如果要删除的节点没有子节点，则直接删除（父节点的指针置为null）
- 如果删除的节点只有一个子节点，则更新父节点指向要删除的指针为指向该子节点
- 如果要删除的节点有两个子节点，需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上，再删除这个最小节点。
中序遍历二叉查找树，即可得出有序的数据序列。
极端情况下，二叉树会退化成链表，时间复杂度会退化到O(n)。
平衡二叉树
平衡二叉树中任意一个节点的左右子树的高度相差不能大于1。完全二叉树、满二叉树都是平衡二叉树。平衡二叉查找树就是满足平衡二叉树的查找树。
AVL树严格符合平衡二叉查找树的定义。而很多平衡二叉查找树其实并不严格符合上面的定义，比如红黑树它从根节点到各个叶子节点的最长路径可能会比最短路径大一倍。其他平衡二叉查找树有伸展树（Splay Tree）、树堆（Treap）等。
红黑树，Red-Black Tree
简称R-B Tree。红黑树中的节点一类被标记为黑色，一类被标记为红色，且满足：
- 根节点是黑色
- 每个叶子节点都是黑色的空节点
- 任何相邻的节点都不能同时为红色
- 每个节点，从该节点到达其可达叶子节点的所有路径都包含相同数目的黑节点
Treap、Splay Tree无法避免极端情况下时间复杂度的退化，对于单次操作时间非常敏感的场景来说，它们并不适用。AVL 树为了维持高度的平衡，每次插入、删除都要做调整，对于有频繁的插入、删除操作的数据集合，使用 AVL 树的代价较高。红黑树只是做到了近似平衡，在维护平衡的成本上，要比 AVL 树要低，他插入、删除、查找各种操作性能都比较稳定。
红黑树的插入和删除操作可能会破坏红黑树的第三、第四条，因此平衡的调整主要是针对这两点。
左旋与右旋
插入
插入的节点必须是红色的，而且，二叉查找树新插入的节点都是放在叶子节点上。插入有八种情况。
1. 红黑树为空树
把插入节点作为根节点，并把节点设置为黑色。
