树的示意办法

  • 直观表示法

    树的直观表示法就是以倒着的分支树的模式示意，如下图所示就是一棵树的直观示意。其特点就是对树的逻辑构造的形容十分直观，是数据结构中最罕用的树的形容办法

  • 嵌套汇合表示法

    所谓嵌套汇合是指一些汇合的个体，对于其中任何的两个汇合，或者不相交，或者一个蕴含另一个。用嵌套汇合的模式示意树，就是将根节点视为一个大的汇合，其若干棵子树形成这个大汇合中若干个互不相交的子集，如此嵌套上来，即形成一棵树的嵌套汇合示意。如下图所示

  • 凹入表示法

    次要用于树的屏幕输入和打印输出

  • 狭义表表示法

    树用狭义表示意，就是将根作为由子树森林组成的表的名字写在表的右边，这样一次将树示意进去。如下所示

    (A(B(D,E(H,I),F),C)G)))

术语

  • 结点

    示意树中的元素，包含数据项及若干指向其子树的分支

  • 结点的度

    结点所领有的子树的个数称为该结点的度

  • 叶子结点

    度为0的结点称为叶子结点，或者称为终端结点

  • 分支结点

    度不为0的结点称为分支结点，或者称为非终端结点。一棵树的结点除叶子结点外，其余的都是分支结点

  • 孩子、双亲、兄弟

    若在一棵树中一个结点A的子树的根节点是B，则称B为A的孩子，称A为B的双亲。具备同一个双亲的子结点互称为兄弟

  • 门路、门路长度

    如果一棵树的一串结点$n_1,n_2,...n_k$有如下关系，即结点$n_i$是$n_{i+1}$的父结点（1<=i<k）,就把$n_1,n_2,...,n_k$称为一条由$n_1$到$n_k$的门路。这条门路的长度是k-1

  • 先人、子孙

    如果有一条门路从结点M到结点N，那么M就称为N的先人，而N称为M的子孙

  • 结点的层数

    规定树的根节点的层树为1，其余结点的层树等于它的双亲结点的层树加1

  • 树的深度

    树中所有结点的最大层树称为树的深度

  • 树的度

    树中各结点度的最大值称为该树的度

  • 有序树和无序树

    如果一棵树中结点的各子树从左到右是有秩序的即若替换了某结点各子树的绝对地位，则形成不同的树，称这棵树为有序树，反之称为无序树

  • 森林

    零棵或无限棵不相交的树的汇合称为森林。自然界中树和森林是不同的概念。在数据结构中，树和森林只有很小的差异，任何一棵树，删去根节点就变成了森林

二叉树

定义

二叉树是指树中节点的度不超过2的有序树。二叉树的递归定义能够为一棵空树，或者一个有根节点和两棵互不相交的，别离称为根的左子树和右子树组成的非空树，左子树右子树又同样是二叉树。

二叉树是递归定义的，节点上有左右子树之分，逻辑上二叉树有五种根本状态

根本状态

  • 空树（图-a）
  • 只有一个根节点的二叉树(图-b)
  • 只有左子树(图-c)
  • 只有右子树(图-d)

  • 齐全二叉树(图-e)

非凡状态

  • 满二叉树

    深度为k，且有 $2^k -1$ 个节点的树称为满二叉树

    满二叉树定义，每一层上的所有节点都有两个子节点，也即是倒数第二层的所有节点都有两个子节点，那么最初一层的所有节点数肯定是倒数第二层的2倍，所以最初一层一个节点都不能缺

  • 齐全二叉树

    深度为k，有n个节点的二叉树当且仅当每一个节点都与深度为k的满二叉树中编号从1到n的节点一一对应时，称为实现二叉树

    叶子节点只能呈现在最上层或者次上层，且最上层的节点集中在树的左侧，满二叉树必定是齐全二叉树，齐全二叉树不肯定是满二叉树

性质

  • 性质1 一棵非空二叉树的第i层上最多有 $2^{i-1}$ 个结点(i>=1)

    在图1中，第4层的结点正好为$2^{4-1}=8$个结点

  • 性质2 一棵深度为k的二叉树中，最多具备$2^k-1$个结点

    在图1中，二叉树的深度为4，正好领有$2^4-1=15$个结点

  • 性质3 对于一棵非空的二叉树，如果叶子结点数为$n_0$,度数为2的结点数为$n_2$,则有$n_0=n_2+1$

    在图1中，二叉树的叶子结点有：H，I，J，K，L，M，N，O共8个结点，而度数为2的结点有：A，B，C，D，E，F，G，共7个结点

  • 性质4 具备n个结点的齐全二叉树的深度k为$log2^n+1$

    在图2中，共有10个结点，其深度正好是$log_2{10}+1=4$

  • 性质5 对于具备n个结点的齐全二叉树,如果依照从上至下，从左到右的程序对二叉树中的所有结点从1开始进行程序编号，则对于任意的序号为i的结点，有：

    • 如果i>1，则序号为i的结点的父结点的序号为i/2;如果i=1，则该结点是根节点，无父结点
    • 如果2i<=n,则序号为i的结点的左子结点的序号为2i；如果2i>n，则序号为i的结点无左子结点
    • 如果2i+1<=n,则序号为i的结点的右子结点的序号为2i+1；如果2i+1>n，则序号为i的结点无右子结点

    对于以上性质，参考图2了解

遍历

以上图二叉树为例，三种遍历形式后果如下

先序遍历（DLR）

  • 拜访根节点
  • 先序遍历根结点的左子树
  • 先序遍历根结点的右子树

输入：ABDC

中序遍历（LDR）

  • 中序遍历根结点的左子树
  • 拜访根结点
  • 中序遍历根结点的右子树

输入：BDAC

后序遍历（LRD）

  • 后序遍历根结点的左子树
  • 后序遍历根结点的右子树
  • 拜访根结点

输入：DBCA

B树

定义

B树也成多路均衡查找树，咱们形容一棵B树的时候个别指定它的阶数，阶数示意一个结点最多有多少个孩子结点，个别用字母m示意阶数，当 m=2，也就是咱们说的二叉查找树

一棵m阶的B树定义如下：

  • 树中每个结点最多有m棵子树
  • 若根结点不是叶子结点，则至多有两棵子树
  • 除根之外的所有非叶子结点至多有[m/2]棵子树
  • 所有的非叶子结点蕴含下列信息数据($n,p_0,k_1,p_1,p_2,...,k_n,p_n$),$k_i$是关键字，且$k_i$<$k_{i+1}$，$p_i$为指向子树根结点的指针，且$p_i$所指向子树中所有结点的关键字均小于$k_{i+1}$,$p_i$为指向根结点的指针，且$p_i$所指子树中所有节点的关键字均小于$k_{i+1}$且大于$k_i$，n为关键字的个数
  • 所有的叶子结点都呈现在同一档次上，根结点到每个叶子结点的长度统一

B+树

定义

B树的变形树，B+树上的叶子结点存储关键字以及相应记录的地址，叶子结点以上各层作为索引应用，一棵m阶的B+树定义如下

  • 每个结点最多有m个子女
  • 除根结点外，每个结点至多有[m/2]个子女，根结点至多有2个子女
  • 有k个子女的节点必有k个关键字

B+树的查找与B树不同，当索引局部某个结点的关键字与所查的关键字相等时，并不进行查找，应持续沿着这个关键字右边的指针向下，始终查找该关键字所在的叶子结点为止

上面是B树结构的演示视频

  • 【100，200，300，400，500，600，700，800，900】插入流程
  • 500的查问
  • 400的删除

B树与B+树比照

  • B+树的磁盘读写代价更低

    B+树的外部结点并没有指向关键字具体信息的指针，所以其外部结点绝对B树更小，如果把所有同一外部结点的关键字寄存在同一盘块中，那么盘块所能包容的关键字数量也越多，。相对来说IO读写次数也就升高了，查找速度更快了

  • B+树查问效率更稳固

    因为非叶子结点并不是最终指向文件内容的结点，而只是叶子结点关键字的索引。所以B+树中任何关键字的查找必须走一条从根结点到叶子结点的路，所有关键字查问的门路长度雷同，导致每一个数据的查问效率相当，而对于B树来说，因为每个结点都存有具体的数据，因而其查问速度不稳固，可能很快也可能很慢。

  • B+树便于范畴查问

    B树在进步了IO性能的同时，并没有解决元素遍历效率低下的问题。为了解决这个问题，B+树应运而生。B+树只须要遍历叶子结点就能够实现整棵树的遍历（B+树叶子结点保护有序链表。在数据库中基于范畴的查找也是十分频繁的，因而MySQL的Innodb引擎就应用了B+树作为其索引的数据结构

根本状态

  • 【100，200，300，400，500，600，700，800，900】插入流程
  • 500的查问

  • 400的删除

红黑树

定义

红黑树是一种特定类型的二叉树，它是在计算机科学中用来组织数据比方数字的块的一种构造

红黑树是一种均衡二叉查找树的变体，它的左右子树高差有可能大于1，所以红黑树不是严格意义上的均衡二叉树（AVL），但对之进行均衡的代价较低，其均匀统计性能要强于AVL

因为每一棵红黑树都是一棵二叉排序树，因而，在对红黑树进行查找时，能够采纳使用于一般二叉树上的查找算法，在查找过程中 不须要色彩信息

性质

  • 结点是红色或彩色
  • 根结点是彩色
  • 所有叶子都是彩色（叶子是NIL结点）
  • 每个红色结点的两个字结点都是彩色（从每个叶子到根的所有门路上不能由两个间断的红色的结点）
  • 从任一结点到其每个叶子的所有门路都蕴含雷同数据的彩色结点

根本状态

  • 【100，200，300，400，500，600，700，800，900】插入流程
  • 500的查问
  • 400的删除

原文链接