每周学点大数据 | No.24二叉搜索树回顾(一)

No.24期

二叉搜索树回顾(一)

Mr. 王:接下来我们谈一谈外存查找结构。内存中的查找结构最典型的就是二查搜索树了。这里我们先来简单地认识一下关于二叉树的问题。为了更好地理解在外存状态下的二叉树,必须要对内存中的树结构非常清楚。

一般意义上的树是一个图,像二叉树这种在计算机中用来存储数据的树型结构和一般的树是不完全一样的,它有一个根节点,而且它有一种自顶向下的方向性。

对于一个一般的图来说,我们将与节点A有直接相连的一条边的节点都称作节点A的邻居。但在树型存储结构中则不然,与A 直接相连、比A 更接近根节点的节点,也就是A 上一层中的节点称作父节点。

与A 直接相连的下一层中的节点称作A 的子节点,A 的父节点的所有儿子,都是A 的兄弟节点。而一个父节点的左儿子及其所有的后代,也就是父节点左边的这一支,我们称之为左子树。相应的,右边的那一部分,我们称之为右子树。

小可:哈哈,父节点和子节点这种叫法还真形象。

Mr. 王:在任何查找树中,每个节点都只有一个父节点。

小可:如果有多个父节点,就会产生环路,是吗?

Mr. 王:没错,反应很快,的确是这样,因为父节点的父节点不断回溯上去,都会汇集到根节点。也就是说,这两个父节点向上的方向是封闭的,如果这两个父节点还有一个共同的儿子,这就会出现一个闭合的回路。这就不符合树的定义了。

小可:之所以树被称为二叉树,是因为每个节点都分两个叉吗?

Mr. 王:顾名思义,但准确地说,二叉树中的每个节点最多有两个子节点,并不是所有的子节点都有两个儿子。不论如何,一棵树都会有叶子。

小可:这个“树”真形象,二叉树还有叶子啊?

Mr. 王:树的叶子节点就是那些度为0 的节点。注意,有根树的度和一般图的度是不一样的。在一般的图中,某个节点n 的度是它邻居的个数;而在一棵有根树中,某个节点n 的度是它的出度,也就是它直接后代的个数,或者说就是儿子节点的个数。

小可:嗯,那我就懂了,叶子就是没有后代的那些节点,只有一条边连向它的父节点。哈哈,这还真像一片叶子。

Mr. 王:如果一棵二叉树除了叶子以外所有节点的度都是2 的话,它就是一棵满二叉树。

小可:嗯,长得像一个金字塔一样。

Mr. 王:如果一棵二叉树不是满二叉树,但是除了最底层以外,其他所有的节点都是填满的,而且最底层节点连续集中排布在左侧的话,这样的二叉树就叫作完全二叉树。

另外,还有一个概念就是树的高度。其实对于一棵有根树来说,从直观上讲,树的高度就是指这棵树有几层。节点在树中的高度,就是指从该节点向下直到某个叶节点的最长简单路径中边的条数。而一棵树的高度,就是指其根节点的高度。在一棵k 叉有n 个节点的有根树中,我们可以非常容易地发现,树的高度是logkn

小可:嗯,二叉树的高度就是log2n

Mr. 王:根据我们前面学过的复杂度分析,可以发现在一棵k 叉树上访问到一个确定节点的复杂度是O(logn)。这也是很显然的,因为途中要经过logkn 条边。

小可突然想到一个问题,说道:我记得前面还有一个概念叫作二叉搜索树,它和二叉树有什么不一样呢?

Mr. 王:二叉搜索树又叫二叉查找树。首先,它是一棵二叉树;其次,它满足这样一个限制,就是对于任意一个节点n 来说,n 的左儿子值比n 的值小,n 的右儿子值比n 的值大。

小可:哦,可是做这样的限制有什么好处呢?

Mr. 王:这样我们就可以更方便地找到一个节点的位置了。比如要查找一个节点,其ID为15。我们发现根节点r 的值是10,于是就可以知道,它一定不是其左儿子,或者其左儿子的所有后代。

小可:因为r 的左儿子值一定比10 小。r 的左儿子值的左儿子值一定比10 还小。

Mr. 王:不难推出r 的左儿子的右子树,其范围在r 的左儿子值到10 之间。这个你可以自己课后思考一下。

小可:的确是这样,所以它一定在它的右子树中。

Mr. 王:于是我们去访问它的右子树,右儿子值是20。

小可:所以说ID 为15 的这个节点一定在右儿子的左子树上!

Mr. 王:没错,就按照这个方法继续访问下去,直到找到15,或者停止在一个非15 的叶子节点上,说明这棵二叉搜索树中不存在值为15 的节点,返回不存在或者空即可。

小可:哦,这样加以限制之后,确实可以让计算机通过很简单的自动化步骤来找到一个特定值的节点。

Mr. 王:其实,这就是在二叉查找树上查找一个节点的算法描述。想一想,这个算法的复杂度如何?

小可:每一次查找,它都会沿着树向下深入一层。这就是说,最多不会超过树的高度,应该是O(logn) !

Mr. 王:很好,O(logn) 这个值是低于线性界限的,是对数级别,说明在二叉查找树上搜索节点的效率是非常高的。二叉查找树这个限制,非常有效地将二叉树变成了一个“有序的状态”。

内容来源:灯塔大数据

原文发布于微信公众号 - 灯塔大数据(DTbigdata)

原文发表时间:2017-01-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏向治洪

数据结构之二叉树

树 定义:满足以下条件的就是树: 1. 有且仅有一个特定的称为根Root的结点。 2. 当n>1时,其余结点可分为m(m>0)个互不相交的有限集,其...

20210
来自专栏kevindroid

leetcode110 Balanced Binary Tree

1465
来自专栏desperate633

LintCode 平衡二叉树题目分析代码

给定一个二叉树,确定它是高度平衡的。对于这个问题,一棵高度平衡的二叉树的定义是:一棵二叉树中每个节点的两个子树的深度相差不会超过1。

712
来自专栏曾大稳的博客

树(Tree)以及二叉树的遍历

树(tree) 是一种抽象数据类型(ADT)或是实作这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。它是由n(n>0)个有限节点组成一个具有层次...

1721
来自专栏java学习

请你对Java中树的了解有多少?

树 1200101班的学生信息表如图6.1所示,其中学生被分到了不同的学习小组,第一组组长是李华,组员有王丽、张阳、赵斌; 第二组组长是孙琪,组员有马丹; 第三...

3635
来自专栏彭湖湾的编程世界

【算法】论平衡二叉树(AVL)的正确种植方法

《算法(java)》                           — — Robert Sedgewick, Kevin Wayne

1082
来自专栏软件开发 -- 分享 互助 成长

二叉排序树和平衡二叉树

二叉排序树又称二叉查找树或二叉搜索树。 它一棵空树或者是具有下列性质: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,...

20710
来自专栏xcywt

《大话数据结构》树以及赫夫曼编码的例子

第六章 树 6.2 树的定义 树(Tree)的n个结点的有限集。当n=0时,称为空树。 任意一个非空树中: 1)有且仅有一个特定的称为根(root)的结点 2)...

4356
来自专栏从流域到海域

校招必考:根据二叉树遍历序列确定二叉树

根据二叉树的前序遍历和中序遍历求其后序遍历或者根据二叉树的后序遍历和中序遍历求其前序遍历是腾讯等校招的必考题,下面我们就来分析一下解题思路。 这道题本质上...

2205
来自专栏彭湖湾的编程世界

【算法】论平衡二叉树(AVL)的正确种植方法

参考资料 《算法(java)》                           — — Robert Sedgewick, Kevin Wayne 《数据结...

31411

扫码关注云+社区