文章首发于「陈树义」公众号及集体博客 shuyi.tech
树结构是数据结构中十分重要的一种类型,本文将从最根底的一般树结构入门,延长到二叉树,再延长至二叉查找树。通过这种思路,让大家构建起对于树的最根本的常识链路。
一般树
树是一种非线性数据结构,它是数据元素按分支关系组织起来的构造,很像自然界中的树那样。
对于树的官网定义是:一棵树是由 N(N>0)个元素组成的无限汇合,其中:
- 每个元素称为结点(node)。
- 有一个特定的结点,称为根结点或根(root)。
- 除根结点外,其余结点被分成 m(m>=0)个互不相交的无限汇合,而每个子集又都是一棵树(称为原树的子树)。
对于树有几个重要的概念,这里简略做下介绍:
- 度
度即节点的分支数,例如上图树中节点 A 有三个子节点,那么咱们称节点 A 的度是 3。
- 档次
节点的档次,示意节点在书中的地位。根结点的档次为 1,其余结点的档次等于它的父结点的档次数加 1。例如上图中节点 F 的档次为 3。
- 深度
树的深度,即组成该树各节点的最大档次。例如上图中节点的最大档次为 K/L/M,那么树的深度就为 K/L/M 任何一个的档次,即树的深度为 4。
- 门路
对于一棵子树中的任意两个不同的结点,如果从一个结点登程,按档次自上而下沿着一个个树枝能达到另一结点,称它们之间存在着一条门路。可用门路所通过的结点序列示意门路,门路的长度等于门路上的结点个数减 1。
例如上图中 A 到 L 的门路为:A > B > E > L,其门路结点个数为 4,那么其长度为 3。
二叉树
二叉树其实就是在一般树的根底上,加上了对树的度限度,即每个节点最多只能有两个子节点。 二叉树有五种根本的状态:
1、空二叉树 —— 如图 a 所示。
2、只有一个根结点的二叉树 —— 如图 b 所示。
3、只有左子树 —— 如图 c 所示。
4、只有右子树 —— 如图 d 所示。
5、齐全二叉树 —— 如图 e 所示。
二叉树是一种简略且重要的树,许多其余类型的树都建设在二叉树的根底之上。依据叶子节点的不同情景,咱们能够将二叉树再细分为:完美二叉树、齐全二叉树、满二叉树。
完美二叉树,指的是所有非叶子节点的度都是 2(只有你有孩子,你必然有两个孩子)。
齐全二叉树 ,指的是深度为 k,有 n 个结点的二叉树当且仅当其每一个结点都与深度为 k 的满二叉树中编号从 1 到 n 的结点一一对应。简略地说,齐全二叉树是满二叉树的一个子集。 简略地说,齐全二叉树就是非叶子节点都有两个子节点,并且必须是从左到右、从上到下的程序。
满二叉树 ,指的是一棵二叉树只有度为 0 的结点和度为 2 的结点,并且度为 0 的结点在同一层上,则这棵二叉树为满二叉树。 简略地说,就是所有叶子节点都在同一个层上,每一层都铺满了节点。
二叉查找树
下面学了那么多树结构的常识,但都没有理论利用,只能说是在打基础,理解基本概念。而二叉查找树能够说是一个十分实用的数据结构,能够用来疾速查找元素。
二叉查找树(Binary Search Tree,BST),有些称其为二叉排序树,其均匀查找效率为 O(logN),最差查找效率为 O(N)(进化为链表)。而其能实现如此疾速的查找速度,次要是其对于数据存储程序的限度。
二叉查找树的定义为:
- 若左子树不空,则左子树上所有结点的值均小于它的根结点的值。
- 若右子树不空,则右子树上所有结点的值均大于它的根结点的值。
- 左、右子树也别离为二叉排序树
- 没有键值相等的结点
依据下面二叉查找树的定义,咱们不难画出上面的二叉查找树。能够看到根节点的 7 元素,大于右边的 3 元素,小于左边的 11 元素。而左右子树 3、11 也同样合乎这样的法则。
依据这样的元素排序,要查找一个元素最多只须要查找树的深度次数就够了。例如要查找元素 5,那么咱们的查找门路是:7 > 3 > 5,只须要查找 3 次。而如果要查找 4,那么咱们的查找门路是:7 > 3 > 5 > 4,只须要查找 4 次。依据二叉树的深度与节点数量的关系,咱们就能够算出二叉查找树的深度为 O(LogN),即二叉查找树的工夫复杂度为 O(LogN)。
二叉查找树在查问方面的效率晋升是微小的,比起链表来说晋升了几万倍。特地是在数据量一直增大的状况下,其晋升性能更加恐怖。例如咱们有 1 亿个元素,如果应用链表存储,那么其均匀须要比拟 5000 万次。而应用二叉查找树存储,咱们只须要比拟 27 次就能够了。5000 万次与 27 次想比拟,相差了 185 万倍!
但二叉查找树也有一个问题,即它在极其状况下会进化成链表。例如咱们有这样一组数字:30、20、10、1,它们组成二叉查找树之后就会进化成一般链表。
那么如何补救二叉查找树的这个缺点呢?这就波及到了树的均衡这个概念。依据树均衡这个思路,先贤们又发明出了均衡二叉树这个概念,发明出了 AVL 树、红黑树等经典的数据结构。咱们下回持续聊均衡二叉树。
总结
明天咱们介绍了一般树结构,以及其相干的根底概念。接着咱们介绍了十分根底的二叉树构造,接着将其扩大到完美二叉树、齐全二叉树、满二叉树。最初,介绍了二叉查找树结构,以及存在的问题。从明天的文章中,咱们能够得出一些论断:
- 二叉树是非凡的树结构,示意其最多只有两个节点。
- 完美二叉树是非叶子节点都有 2 个节点的二叉树。
- 齐全二叉树是在完美二叉树的根底上,加上左右到有、从上到下都有节点的限度。
- 满二叉树是是在齐全二叉树的根底上,加上每层的节点都是满的这个限度。
- 二叉查找树能实现 O(logN)的工夫复杂度查找,然而会有进化成链表的危险。
到目前为止,咱们将学习到的的树结构搭建起来,能够画出如下的树结构小道。
参考资料
- 完满二叉树,齐全二叉树和完美二叉树 – veli – 博客园
- 6 天通吃树结构 —— 第一天 二叉查找树 – 一线码农 – 博客园