二叉树:

  • 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$ 。

赫夫曼树(最优二叉树)

一颗带权路径长度最小的二叉树称作赫夫曼数(最优二叉树)。

赫夫曼算法

  1. 将n个权值集合F {$w_1$,$w_2$,$w_3$,…,$w_i$} 看作 n 颗二叉树的集合
  • 从下往上构建
  • 选择两颗根结点权值最小的树作为左右子树构建一颗新的二叉树,新二叉树的根结点的权值为左、右子树上根结点之和。
  • 从F中删除这辆颗树,同时将新得到的数加入
  • 重复3到4,直到F中只剩一棵树为止。
  • 最后一颗树就是最优二叉树。

Huffman Tree

二叉查找树(原理为二分查找)

  • 左节点小于或等于父结点
  • 右节点大于或等于父结点
  • 最大查找次数为树的高度

红黑树(自平衡二叉查找树)

解决了二叉查找树在多次插入新的节点会破坏平衡的问题

解决方法为:

  • 节点变色。通过将结点变为红或黑保持平衡
  • 旋转。通过左旋转和右旋转保持平衡