5.2_1_二叉树

未匹配的标注

5.2_1_二叉树的定义和基本术语

5.2_1_二叉树的定义和基本术语

5.2_1_二叉树的定义和基本术语

二叉树

5.1.1 树的定义和基本术语

5.1.1 树的定义和基本术语

二叉树的存储

5.1.1 树的定义和基本术语

5.1.1 树的定义和基本术语

5.1.1 树的定义和基本术语

二叉排序(查找)树

5.1.1 树的定义和基本术语

平衡二叉树(AVL)

5.1.1 树的定义和基本术语
平衡二叉树要求每个节点的左子树和右子树的高度差至多等于 1,这个高度(深度)差的值叫做平衡因子 BF,也就是说 BF 的值不能大于 1,否则就不是平衡二叉树。
如果平衡因子小于 -1,即右子树高度值比较大,则需要左旋:

5.1.1 树的定义和基本术语

反之,如果平衡因子大于 1,即左子树高度值比较大,则需要右旋:

5.1.1 树的定义和基本术语

四种调整方式:LL(右旋)、RR(左旋)、LR(先右旋再左旋)、RL(先左旋再右旋)

平衡二叉树性能是最好的,也是最稳定的,但是这套算法实现起来比较复杂,每次插入节点和删除节点都需要判断剩下节点构成的二叉排序树是否满足平衡二叉树的要求,如果不满足需要做相应的左旋右旋处理,维护成本高,因此,在工程实践上,我们更多时候使用的是红黑树这种二叉排序树,它是一种不严格的平衡二叉树,实现起来更加简单,性能也接近严格的平衡二叉树

红黑树

  • 节点是红色或黑色;
  • 根节点是黑色的;
  • 每个叶子节点都是黑色的空节点(NIL),也就是说,叶子节点不存储数据;
  • 任何相邻的节点都不能同时为红色,也就是说,红色节点是被黑色节点隔开的;
  • 每个节点,从该节点到达其可达叶子节点的所有路径,都包含相同数目的黑色节点;

下面是一个典型的红黑树示例:

5.1.1 树的定义和基本术语

应用:

  1. 著名的 linux 进程调度,用红黑树管理进程控制块
  2. epoll 在内核中的实现,用红黑树管理事件块
  3. nginx 中,用红黑树管理 timer 等
  4. Java 的 TreeMap 实现
  5. 广泛用在 C++ 的 STL 中。map 和 set 都是用红黑树实现的。

压缩算法的基础:赫夫曼树

哈夫曼树是一种带权路径长度最短的二叉树,也称为最优二叉树。

5.1.1 树的定义和基本术语

它们的带权路径长度分别为:

图 a: WPL=5 * 2 + 7 * 2 + 2 * 2 + 13 * 2=54

图 b: WPL=5 * 3 + 2 * 3 + 7 * 2 + 13 * 1=48

可见,图 b 的带权路径长度较小,我们可以证明图 b 就是哈夫曼树 (也称为最优二叉树)。

本文章首发在 LearnKu.com 网站上。

上一篇 下一篇
讨论数量: 0
发起讨论 查看所有版本


暂无话题~