每周学点大数据 | 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) 这个值是低于线性界限的，是对数级别，说明在二叉查找树上搜索节点的效率是非常高的。二叉查找树这个限制，非常有效地将二叉树变成了一个“有序的状态”。
内容来源：灯塔大数据