盒子
盒子
文章目录
    1. 引用
  1. 从二叉树到红黑树
    1. 二叉树
    2. 二叉搜索树(Binary Search Tree)
    3. 平衡二叉树(AVL 树)
    4. 2-3 树
    5. 2-3 查找树
    6. 红黑树
  2. B-树
  3. B+树
  4. 完全二叉树
  5. 最优二叉树(就是哈弗曼树)
  6. 满二叉树
  7. KMP 字符串 求 next

总结一下关于树的东西...

叶子结点就是没有孩子的结点,其为0,为二的结点是指有两个子树的结点。

注意树的度 和 图的度 区别

叶子结点

引用

二叉查找树和二叉堆

平衡二叉树、B树、B+树、B*树 理解其中一种你就都明白了

从二叉树到红黑树

这篇文章讲挺好的:Map集合、散列表、红黑树介绍

二叉树

树的每个节点最多只能有两个节点.

对比 2-3 树来看,2-3 树的节点可以拥有 2 或 3 个子节点.

二叉搜索树(Binary Search Tree)

怎么称呼的都有,二分查找树,二叉搜索树,二叉排序树,有序的二叉树…

但是它的功能不仅在搜索哦,还需要增删改…

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为
$$
O(\log n)
$$

如果大量删除,二叉排序树就有可能变为一个单叶的树,此时查询效率就成了O(n)。

二叉查找树越是“矮胖”,也就是每层尽可能地被“塞满”(每个父节点均有两个子节点)时,查找效率越高。每层都被塞满时,查找效率最高,最高为 O(log n)。当二叉查找树退化为单链表时,查找效率最低,最低为O (n)。

为了解决二叉查找树退化为单链表时查找效率低下的问题,引入了平衡二叉树。

相同结点数深度最小的是平衡二叉树。

平衡二叉树(AVL 树)

也叫 平衡二叉搜索树.

当我们谈平衡二叉树时,默认它已经是一棵二叉搜索树.

平衡二叉树是对二叉搜索树的改进.

定义:AVL 树是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

在树有序的情况下,树的查询速度取决于树的深度.

如果仅仅是二叉搜索树,那么在最坏的情况下,查找的效率就是 O(n).

AVL 树的”矮胖”就是使数据尽可能地二分.

使用 AVL 树,查找是快了,但是当涉及到插入时,就需要极大的代价去维护树的平衡.因此,有了 2-3 查找树.

  1. windows 对进程地址空间的管理用到了 AVL 树

2-3 树

2-3 树的节点可以拥有 2 或 3 个子节点.

2-3 树是最简单的 B-树.

直接把定义甩出来很抽象,把 2-3 树放在 2-3 查找树里看,直观一些.

2-3 查找树

2-3 查找树是对平衡二叉树的优化(自然,也是对二叉搜索树的改进).

同理,当我们谈 2-3 查找树时,也就是默认这已经是 AVL 树了.

事实上,2-3 树属于 B-树,B-树已经默认是平衡二叉树.

使用二叉搜索树,动态插入时,要花很高的代价才能保证树的完美平衡.

  1. 什么是树的平衡
  2. 为什么要保持树的完美平衡?

上面平衡树和平衡二叉搜索树有说明.

那么 2-3 查找树怎么花比较小的代价去维护树的平衡?

查询:和二叉查找树差不多

2-3 查找树如何在插入删除时保证平衡

插入:2-3树之所以完美平衡,关键在于插入时的维护。

删除:插入麻烦,删除更麻烦.

红黑树

红黑二叉树是对 2-3 树的优化.

来自书籍 [算法].

红黑树背后的思想是用标准的二叉搜索树(完全由2- 结点构成)和一些额外的信息(替换 3- 结点)来表示 2-3 树.

将树中的链接分为两种类型:

红链接:将两个 2- 结点连接起来构成一个 3- 结点.

黑链接:2-3 树中的普通链接.

  1. 红黑树用于MySQL 的 InnoDB 存储索引.
  2. JDK1.8 中,当桶中节点数目大于 8,将链表转换为红黑树存储.

B-树

上面提到 2-3 树是最简单的 B-树.

B-树属于多叉树,又名平衡多路查找树.也就是在 2-3 上面进行扩展.

2-3 树的节点可以拥有 2 或 3 个子节点,而 B-树的节点可以拥有多个子节点.

B+树

B+树是对 B-树的升级.

  1. B/B+树 用在磁盘文件组织,数据索引和数据库索引

完全二叉树

若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。

完全二叉树——只有最下面的两层结点度小于2,并且最下面一层的结点都集中在该层最左边的若干位置的二叉树.

最优二叉树(就是哈弗曼树)

主要内容是哈弗曼算法,如何构造哈弗曼树,哈夫曼序列.

概念其实很好理解…这里不提了,搜索一下吧.

满二叉树

满二叉树——除了叶结点外每一个结点都有左右子叶且叶结点都处在最底层的二叉树,。

除最后一层无任何子节点外,每一层上的所有结点都有两个子结点(最后一层上的无子结点的结点为叶子结点)。也可以这样理解,除叶子结点外的所有结点均有两个子结点。节点数达到最大值。所有叶子结点必须在同一层上.

KMP 字符串 求 next

也很好理解,但是过一阵子就忘了…