- 一个节点可以只有根节点 也可以是一棵树
- ...
每个节点最多有两个子节点的树称为二叉树
- 树及其子树的左右高度差不能超过1
- 空树及只有根节点的树也是平衡二叉树
擅长数据的查找
对于任何节点：
- 左子树上所有节点都小于它
- 右子树所有节点都大于它
查找树随着数据的不断增加或插入容易失衡
在增加和删除节点时通过旋转来保持平衡
右旋：以某个节点为中心 将它沉入当前右子节点的位置 然后让当前左子节点作为新树的根
左旋：
红黑树不追求左右子树高度差不超过1
而是保证从根节点到叶尾的最长路径不超过最短路径的2倍
其他约束条件：
- 节点只能是红色或者黑色
- 根节点必须是黑色
- NIL(Nothing in leaf)节点都是黑色
- 相连的两个节点不能都是红色
- 根节点到叶子节点的所有路径黑色节点数量都相同
红黑树的任何旋转至多3次就能完成