疯狂的小鸡

数据结构-树

字数统计: 3.6k阅读时长: 12 min
2018/10/22 Share

介绍一些常见的树,了解一些树的基本概念,具体代码操作不做详细说明。

二叉查找树

二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),亦称二叉搜索树。

二叉排序树或者是一棵空树,或者是具有下列性质的二叉树:

  • 若左子树不空,则左子树上所有结点的值均小于或等于它的根结点的值;
  • 若右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值;
  • 左、右子树也分别为二叉排序树。

查找:

若根结点的关键字值等于查找的关键字,成功。

否则,若小于根结点的关键字值,递归查左子树。若大于根结点的关键字值,递归查右子树。

若子树为空,查找不成功。

最差情况分析 O(n)
平均情况分析:O(logn)

插入:

首先执行查找算法,找出被插结点的父亲结点。判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。

删除:

在二叉排序树删去一个结点,分三种情况讨论:

1) 若*p结点为叶子结点,即PL(左子树)和PR(右子树)均为空树。由于删去叶子结点不破坏整棵树的结构,则可以直接删除此子结点。

2) 若p结点只有左子树PL或右子树PR,此时只要令PL或PR直接成为其双亲结点f的左子树(当p是左子树)或右子树(当p是右子树)即可,作此修改也不破坏二叉排序树的特性。

3) 若p结点的左子树和右子树均不空。在删去p之后,为保持其它元素之间的相对位置不变,可按中序遍历保持有序进行调整,可以有两种做法:

  • 其一是令p的左子树为f的左/右(依p是f的左子树还是右子树而定)子树,*s为p左子树的最右下的结点,而p的右子树为*s的右子树;

  • 其二是令p的直接前驱(或直接后继)替代p,然后再从二叉排序树中删去它的直接前驱(或直接后继)-即让f的左子树(如果有的话)成为p左子树的最左下结点(如果有的话),再让f成为p的左右结点的父结点。

二叉堆 heap

在实际应用中,我们主要考虑最大堆(也称大顶堆)和最小堆(小顶堆)。其中最大堆(Max Heap)的根节点关键字(key)为所有节点关键字中最大值,且要求所有节点关键字的值大于等于其左孩子和右孩子的关键字。最小堆同理。

插入:新元素放在树最底层右边,然后上浮

删除根节点: 使用末节点替换根节点,然后对跟节点下沉。

删除任意节点:使用末节点替换被删除节点,然后对该节点先下沉再上浮。

堆的构建

方法1:插入法:
从空堆开始,依次插入每一个结点,直到所有的结点全部插入到堆为止。
时间:O(n*log(n))

方法2:调整法:
序列对应一个完全二叉树;从最后一个分支结点(n div 2)开始,到根(1)为止,依次对每个分支结点进行调整(下沉),
以便形成以每个分支结点为根的堆,当最后对树根结点进行调整后,整个树就变成了一个堆。
时间:O(n)

2-3查找树

一棵2-3查找树或为一颗空树,或由以下节点组成:
2-节点:含有一个键和两条链接,左链接指向的2-3树中的键都小于该节点,右链接指向的2-3树中的键都大于该节点。
3-节点:含有两个键和三条链接,左链接指向的2-3树中的键都小于该节点,中链接指向的2-3树中的键都位于该节点的两个键之间,右链接指向的2-3树中的键都大于该节点。
23树示例

插入(难点)因为要维持平衡

每当有新的元素插入时,进行一次未命中查找,当有存放它的位置时,2-节点还尚有一个存储空间,它就存放。
如果遇到的是一个3-节点,没有位置放,则我们先把他变成一个4-节点,然后分情况讨论:

  • 如果这个4-节点的父节点为2-节点,则将中键上提到父节点,形成2个3-节点
  • 如果这个父节点也为3节点,则不断上提中键,直到遇到一个父节点为2-节点
  • 如果一直到根节点全是3-节点,则分裂生成的4-节点为2个2-节点

红黑树

红黑树可以说利用二叉查找树对2-3查找树的实现,红链接将两个2-节点连起来构成一个3-节点,黑链接则是普通链接。这种实现的好处是可以使用二叉查找树高效的查找方法并能使用2-3树高校的平衡插入方法。事实上,将红黑树的红链接画平就是一个2-3树。
红黑树树示例1
红黑树树示例2

红黑树的性质:

  • 节点是红色或黑色(红黑树结的的颜色实际上是指该节点与其父节点之间链接的颜色)
  • 根节点是黑色 。根据节点颜色定义可得
  • 所有叶子都是黑色(叶子是NIL节点)。
  • 每个红色节点的两个子节点都是黑色。没有任何一个结点同时和两条红链接相连,不然就变成4-节点了.
  • 该树是完美黑色平衡的,即任意空链接到根结点的路径上的黑链接数量相同。
  • 红链接均为左链接。只允许红色左链接可以减少可能出现的情况,从而减少代码量。也有支持红色右链接的红黑树实现。

旋转:
左旋转将一个红色右链接转化为红色左链接,右旋转相反。网上分各种旋转的可能性,其实只需对比2-3树,把红链接链接的两个节点当作一个3节点来看就知道怎么旋转了。

插入:
可对比2-3树插入,结果再进行旋转保证红黑树性质即可。

删除(难点):结合具体情况具体分析。。。

AVL树

平衡二叉树又称AVL树,它或者是一棵空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1。

AVL树是最先发明的自平衡二叉查找树算法。在AVL中任何节点的两个儿子子树的高度最大差别为1,所以它也被称为高度平衡树,n个结点的AVL树最大深度约1.44log2n。

查找、插入和删除在平均和最坏情况下都是O(log n)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

平衡二叉树追求绝对平衡,条件比较苛刻,实现起来比较麻烦,每次插入新节点之后需要旋转的次数不能预知。

B树

一个 m 阶的B树满足以下条件:

  • 树中每个结点最多含有m个孩子(m>=2);
  • 除根结点和叶子结点外,其它每个结点至少有[ceil(m / 2)]个孩子;
  • 若根结点不是叶子结点,则至少有2个孩子(特殊情况:没有孩子的根结点,即根结点为叶子结点,整棵树只有一个根节点);
  • 所有叶子结点都出现在同一层。

每个非终端结点中包含有n个关键字信息: (n,P0,K1,P1,K2,P2,……,Kn,Pn)。其中:
a) Ki (i=1…n)为关键字,且关键字按顺序升序排序K(i-1)< Ki。
b) Pi为指向子树根的接点,且指针P(i-1)指向子树种所有结点的关键字均小于Ki,但都大于K(i-1)。
c) 关键字的个数n必须满足: [ceil(m / 2)-1]<= n <= m-1。

B树示例

B树是对二叉查找树的改进。它的设计思想是,将相关数据尽量集中在一起,以便一次读取多个数据,减少硬盘操作次数。

B树为系统最优化大块数据的读和写操作。B树算法减少定位记录时所经历的中间过程,从而加快存取速度。普遍运用在数据库和文件系统。

假定一个节点可以容纳100个值,那么3层的B树可以容纳100万个数据,如果换成二叉查找树,则需要20层!假定操作系统一次读取一个节点,并且根节点保留在内存中,那么B树在100万个数据中查找目标值,只需要读取两次硬盘。

为什么计算机系统内会优先使用B树而不是红黑树?

计算机有一个局部性原理,就是说,当一个数据被用到时,其附近的数据也通常会马上被使用。所以当你用红黑树的时候,你一次只能得到一个键值的信息,而用B树,可以得到最多M-1个键值的信息。这样来说B树当然更好了。另外一方面,同样的数据,红黑树的阶数更大,B树更短,这样查找的时候当然B树更具有优势了,效率也就越高。

B+树

B+树是B树的变体,也是一种多路搜索树:
1.其定义基本与B树同,除了:
2.非叶子结点的子树指针与关键字个数相同;
3.非叶子结点的子树指针P[i],指向关键字值属于[K[i], K[i+1])的子树(B-树是开区间);
5.为所有叶子结点增加一个链指针;
6.所有关键字都在叶子结点出现;

B+树示例

为什么说B+树比B 树更适合实际应用中操作系统的文件索引和数据库索引?

  • B+-tree的磁盘读写代价更低
    B+-tree的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中,那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。

  • B+-tree的查询效率更加稳定
    由于非终结点并不是最终指向文件内容的结点,而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当。

  • 数据库索引采用B+树的主要原因是 B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题,B+树应运而生。B+树只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的,而B树不支持这样的操作(或者说效率太低)。

注意了,没有B- 树。B-树就是B树,中间是横杠不是减号。

B*树

B-tree是B+-tree的变体,在B+树的基础上(所有的叶子结点中包含了全部关键字的信息,及指向含有这些关键字记录的指针),B树中非根和非叶子结点再增加指向兄弟的指针;B树定义了非叶子结点关键字个数至少为(2/3)\M,即块的最低使用率为2/3(代替B+树的1/2)。

B*树示例

B+树的分裂:当一个结点满时,分配一个新的结点,并将原结点中1/2的数据复制到新结点,最后在父结点中增加新结点的指针;B+树的分裂只影响原结点和父结点,而不会影响兄弟结点,所以它不需要指向兄弟的指针。

B*树的分裂:当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了);如果兄弟也满了,则在原结点与兄弟结点之间增加新结点,并各复制1/3的数据到新结点,最后在父结点增加新结点的指针。

所以,B*树分配新结点的概率比B+树要低,空间使用率更高;

Trie树(字典树)

字典树又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希表高。

Trie树示例

字典树很明显的就是用空间来换时间,空间复杂度特别大,比如字典数单单存26个小写字母,那么每个节点的孩子节点都有26个孩子节点,字典树中的每一层都保留着不同单词的相同字母。

CATALOG
  1. 1. 二叉查找树
    1. 1.1. 查找:
    2. 1.2. 插入:
    3. 1.3. 删除:
  2. 2. 二叉堆 heap
    1. 2.1. 堆的构建
  3. 3. 2-3查找树
    1. 3.1. 插入(难点)因为要维持平衡
  4. 4. 红黑树
  5. 5. AVL树
  6. 6. B树
    1. 6.1. B+树
    2. 6.2. B*树
  7. 7. Trie树(字典树)