二叉树：
- AVL树(自平衡二叉树)
- 红黑树
- 哈夫曼树(最优二叉树)
B树不是二叉树
二叉树
- 二叉树的第 $i$ 层至多拥有 $ 2^{i-1} $ 个节点数；
- 深度为 $k$ 的二叉树至多总共有 $2^{k+1} - 1$ 个节点数（定义根节点所在深度为$k_{0}=0$），而总计拥有节点数匹配的，称为“满二叉树”；
- 深度为 $k$ 有 $n$ 个节点的二叉树，当且仅当其中的每一节点，都可以和同样深度 $k$ 的满二叉树，序号为 $1$ 到 $n$ 的节点一对一对应时，称为“完全二叉树”。；
- 对任何一棵非空的二叉树 T , 如果其叶片(终端节点)数为 $n_{0}$，分支度为 $2$ 的节点数为 $n_{2}$，则 $n_{0}= n_{2} + 1$ 。
赫夫曼树(最优二叉树)
一颗带权路径长度最小的二叉树称作赫夫曼数(最优二叉树)。
赫夫曼算法
- 将n个权值集合F {$w_1$,$w_2$,$w_3$,…,$w_i$} 看作 n 颗二叉树的集合
- 从下往上构建
- 选择两颗根结点权值最小的树作为左右子树构建一颗新的二叉树，新二叉树的根结点的权值为左、右子树上根结点之和。
- 从F中删除这辆颗树，同时将新得到的数加入
- 重复3到4，直到F中只剩一棵树为止。
- 最后一颗树就是最优二叉树。
二叉查找树（原理为二分查找）
- 左节点小于或等于父结点
- 右节点大于或等于父结点
- 最大查找次数为树的高度
红黑树(自平衡二叉查找树)
解决了二叉查找树在多次插入新的节点会破坏平衡的问题
解决方法为:
- 节点变色。通过将结点变为红或黑保持平衡
- 旋转。通过左旋转和右旋转保持平衡
