树概述

树的类型不少,此篇简要对树进行描述,脑中有个整体概念,细节分篇再研究

树(Tree)是n(n>=0)个结点的有限集。

在任意一棵非空树中:

(1)有且仅有一个特定的称为根(Root)的结点;

(2)当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tn,其中每个集合本身又是一棵树,并称为根的子树(SubTree)

术语

  1. 结点:如上图,每一个圈圈我们就称为树的一个结点
  2. : 结点拥有的子树数称为结点的度-(Degree),树的度取树内各结点的度的最大值
  3. 叶结点(Leaf)或终端结点: 度为0的结点
  4. 内部结点: 度不为0的结点称为分支结点或非终端结点,除根结点外,分支结点也称为内部结点。5. 结点间的关系:结点的子树的根称为结点的孩子(Child),相应的,该结点称为孩子的双亲(Parent),同一双亲的孩子之间互称为兄弟(Sibling)。结点的祖先是从根到该结点所经分支上的所有结点
  5. 深度:树中结点的最大层次称为树的深度(Depth)或高度
  6. 结点的层次(Level): 从根开始定一起,根为第一层,根的孩子为第二层。其双亲在同一层的结点互为堂兄弟
  7. 有序树: 如果将树中结点的各子树看成从左至右是有次序的,不能互换的,则称该树为有序树, 否则为无序树
  8. 森林(Forest): 是 m(m>=0)棵互不相交的树的集合。对树中每个结点而言,其子树的集合即为森林

二叉树

二叉树(Binary Tree)是n(n>=0)个结点的有限集合。该集合可能是空的(空二叉树),也可能由
一个根结点和该根结点的左子树和右子树组成。左右子树不相交,而且都是二叉树

特点

  1. 每个结点最多有两棵字树,即每个结点的度和树的度不大于2。
  2. 结点的左子树和右子树是有顺序的,不能颠倒。
  3. 即使结点只有一棵子树,也是有顺序的

满二叉树

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

完全二叉树

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

之前讲过的《堆排序》 就是依赖完全二叉树结构

二叉查找树

二叉查找树(Binary Search Tree),又被称为二叉搜索树

(1)若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;

(2) 若任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;

(3) 任意节点的左、右子树也分别为二叉查找树;

(4) 没有键值相等的节点

复杂度

复杂度分析:它和二分查找一样,插入和查找的时间复杂度均为O(logn),但是在最坏的情况下仍然会有O(n)的时间复杂度。原因在于插入和删除元素的时候,树没有保持平衡

平衡二叉树

平衡二叉搜索树,又被称为AVL树

由于普通的二叉查找树会容易失去”平衡“,极端情况下,二叉查找树会退化成线性的链表,导致插入和查找的复杂度下降到 O(n) ,所以,这也是平衡二叉树设计的初衷。

具有以下性质

  1. 要么是棵空树,要么其根节点左右子树的深度之差的绝对值不超过1;
  2. 其左右子树也都是平衡二叉树;
  3. 二叉树节点的平衡因子定义为该节点的左子树的深度减去右子树的深度。则平衡二叉树的所有节点的平衡因子只可能是-1,0,1

红黑树

红黑树是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。它是在1972年由Rudolf Bayer发明的,他称之为”对称二叉B树”,它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年写的一篇论文中获得的。它是复杂的,但它的操作有着良好的最坏情况运行时间,并且在实践中是高效的: 它可以在O(log n)时间内做查找,插入和删除,这里的n是树中元素的数目

特性

  1. 每个节点要么是红色,要么是黑色。
  2. 根节点永远是黑色的。
  3. 所有的叶节点都是空节点(即 null),并且是黑色的。
  4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的路径上不会有两个连续的红色节点)
  5. 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。

为什么需要红黑树

平衡二叉树的插入/删除操作带来的旋转操作可能会达到logn次

红黑树的插入操作最多进行两次旋转、删除操作最多进行三次旋转

B树

B树是一种平衡的多路查找树,结点最大的孩子数目称为B树的阶(Order),是为磁盘存储而专门设计的一类平衡搜索树

b-tree分为用“阶”的定义和用“度”的定义,度和阶都是描述子节点的数量的

特性

  1. 定义任意非叶子结点最多只有M个儿子;且M>2;
  2. 根结点的儿子数为[2, M];
  3. 除根结点以外的非叶子结点的儿子数为[M/2, M];
  4. 每个结点存放至少M/2-1(取上整)和至多M-1个关键字;(至少2个关键字)
  5. 非叶子结点的关键字个数=指向儿子的指针个数-1;
  6. 非叶子结点的关键字:K[1], K[2], …, K[M-1];且K[i] < K[i+1];
  7. 非叶子结点的指针:P[1], P[2], …, P[M];其中P[1]指向关键字小于K[1]的子树,P[M]指向关键字大于K[M-1]的子树,其它P[i]指向关键字属于(K[i-1], K[i])的子树;
  8. 所有叶子结点位于同一层;

逻辑结构图

这是B树存储在硬盘的逻辑结构图。

其中根节点中17,35在称为关键字(key) ,实际中往往附带更多复杂类型数据。

可以看出一个节点包含 keys ChildNotePointer 2部分信息

为什么需要B树

  1. 当数据量大的时候,树的高度会比较高,数据量大的时候,查询会比较慢
  2. 树每个节点只存储一个记录,可能导致一次查询有很多次磁盘IO

这是个典型的b树结构,初始因子为1000,高度仅为3的b树,就可以存储1002001000的数据了

假设要查询最后一个数据:

  • 从硬盘加载根节点搜索,IO一次。
  • 根据根节点的指针信息,去加载第二层的节点, IO一次。
  • 重复2,IO一次。
    IO只用了3次,就查询了需要的数据,所以说B树效率是非常高的。

B树的节点,在硬盘里表现为:柱面里的页(page)或盘块(block),如果把索引持久化到内存,只需要一次就够了

B+树

B+树是B-树的变体,也是一种多路搜索树:

  1. 其定义基本与B-树相同
  2. 非叶子结点的子树指针与关键字个数相同(B树中是k-1个元素)
  3. 非叶子结点的子树指针P[i],指向关键字值属于[K[i], K[i+1])的子树(B-树是开区间);
  4. 为所有叶子结点增加一个链指针
  5. 所有关键字都在叶子结点出现

B+的搜索与B-树也基本相同,区别是B+树只有达到叶子结点才命中(B-树可以在非叶子结点命中),其性能也等价于在关键字全集做一次二分查找

B树:有序数组+平衡多叉树

B+树:有序数组链表+平衡多叉树

B+树的关键字全部存放在叶子节点中,非叶子节点用来做索引,而叶子节点中有一个指针指向一下个叶子节点。做这个优化的目的是为了提高区间访问的性能。而正是这个特性决定了B+树更适合用来存储外部数据

为什么需要B+树

  1. b+树的中间节点不保存数据,所以磁盘页能容纳更多节点元素,更“矮胖”;
  2. b+树查询必须查找到叶子节点,b树只要匹配到即可不用管元素位置,因此b+树查找更稳定(并不慢);
  3. 对于范围查找来说,b+树只需遍历叶子节点链表即可,b树却需要重复地中序遍历

B*树

B*树是对B+树进行的又一次的升级。在B+树的非根和非叶子结点再增加指向兄弟的指针

在B+树基础上,为非叶子结点也增加链表指针,将结点的最低利用率从1/2提高到2/3;

在这比如说当你进行插入节点的时候,它首先是放到兄弟节点里面。如果兄弟节点满了的话,进行分裂的时候从兄弟节点和这个节点各取出1/3,放入新建的节点当中,这样也就实现了空间利用率从1/2到1/3。

总结

B树:二叉树,每个结点只存储一个关键字,等于则命中,小于走左结点,大于走右结点

B-树:多路搜索树,每个结点存储M/2到M个关键字,非叶子结点存储指向关键字范围的子结点;
所有关键字在整颗树中出现,且只出现一次,非叶子结点可以命中;

B+树:在B-树基础上,为叶子结点增加链表指针,所有关键字都在叶子结点中出现,非叶子结点作为叶子结点的索引;B+树总是到叶子结点才命中;

B*树:在B+树基础上,为非叶子结点也增加链表指针,将结点的最低利用率从1/2提高到2/3;

参考资料

B-树学习笔记

公众号:码农戏码
欢迎关注微信公众号『码农戏码』