介绍

在本教程中,我们将讨论金宝搏官网188be二叉搜索树数据结构的时间复杂度。

2.二叉树的主要性质

Knuth二叉树的定义如下:“一棵二叉树是一个有限的节点集,它要么是空的,要么是由一个根和两个不相交的二叉树(根的左子树和右子树)组成。”

让我们从二叉树的通用结构开始:

当然,也有非二叉树。但是,需要注意的是,二叉树不是树的特殊情况,而是一个不同的概念。例如,那些树:

当定义为普通树时,我们可以认为它们是相同的,但当分析为二叉树时,我们可以认为它们是不同的。

在二叉搜索树中,每个节点都由一个键标识,该键按照以下属性存储:\ boldsymbol {x}是二叉树的一个节点。如果\ boldsymbol {y}它的左子树中有一个节点吗\ boldsymbol {x}然后\ boldsymbol {le关键关键[y] \ [x]}。如果\ boldsymbol {y}在右边的子树中有一个节点吗\ boldsymbol {x},然后\ boldsymbol{键[y] \通用键[x]}

二叉搜索树的初等运算

假设一组数据,例如,一个数据库D,其中包含ASCII格式的信息。数据库中的每一行或记录都由一系列由键标识的不同字段组成。让n是数据库中记录的数量,每个记录由N字段。

然后我们将有一个关键字段和n - 1包含相关信息的字段。假设每个记录的键是唯一的。它可以存储D根据上面提到的性质组织为二叉搜索树。

二叉搜索树中的基本或原始操作包括搜索、最小值、最大值、前身、后继、插入和删除。计算复杂度取决于树的高度的概念h,我们可以非正式地将其定义为组成树的层数。例如,第一个图中的二叉树有5级(包括根)。

4.二叉树搜索的时间复杂度

假设我们有一把钥匙k的关联字段Dk。这个问题可以表述为节点的识别x这样关键[x] = k。因此,我们进入树,从根节点开始,比较我们的键和我们访问的节点的键。注意,每个动作都涉及到在树上下降一个水平

如果键是唯一的,则搜索期间访问的节点数最多等于h,搜寻工作就可以及时完成O (h)。这个行为也被其他的原语操作所满足,所以我们得到了以下重要而直观的结果:二叉搜索树高度的所有运算\ boldsymbol {h}能否及时执行\ boldsymbol {O (h)}

5.搜索优化问题

在执行原语操作时,并非所有二叉搜索树都同样有效。从计算复杂度依赖的角度给出了提高效率的关键h而不是n

元素在二叉树中的排列方式会影响树的高度。一般来说,我们可以表述最优构造的问题,比如搜索通向树的节点的排列,以获得最小的高度。

最糟糕的情况是数据库D已经按键排序了。在这种情况下,如果我们通过插入n按照原始顺序记录,我们将得到一棵只包含左子树或右子树的树,这取决于键的顺序分别是降序还是升序:

在这种情况下,h = n,通过前一段的讨论,实现了原语操作O (n)。这种情况等同于链表。

6.在平衡树中搜索

如果钥匙D是无序的,构建基于插入操作的二叉树产生的结构与h < n。当任意结点的左子树和右子树的高度相差不超过1时,称为树平衡,可以证明如下结果:

一个随机构造的二叉搜索树的平均高度\ boldsymbol {n}不同的键是日志{_2}\ boldsymbol {O (n)}

根据前面的结果,我们得出结论,搜索键,以及在二叉搜索树上执行的任何基元操作,都需要时间O (n)在最坏的情况下O (log {_2} n)在一般情况下。构造一个基于插入的树n的记录D因此需要时间O (n ^ 2)在最坏的情况下O (nlog {_2} n)在一般情况下。

7.二叉搜索树的实际问题和变体

二叉搜索树被用于许多计算过程。然而,本教程中介绍的基本理论并非没有问题。

在实际应用中,二叉搜索树并不一定是平衡的。必须考虑到在每一步保持一个完美平衡的二叉树是一个昂贵的过程,这可能导致消除平衡条件和整体退化。

有一些变体可以解决这些缺陷。的例子是自平衡二叉搜索树RB-trees(红黑)。

在许多数据库引擎中都使用了rb树。与标准二叉树相比,它们还包含一个额外的二进制字段,称为color通过精确的节点着色规则,可以得到任意路径的长度不超过其他路径的两倍。

所有这些二叉树的变种都是为了追求相同的目标而设计的:最优的结构,以获得最优的平衡,从而产生最小高度的树。

8.结论

在本教程中,我们概述了二叉搜索树的基本理论。我们着重讨论了原语操作的计算代价,特别是搜索操作。

在文中,一些想法被建议给读者进一步研究,特别是可能的平衡技巧。

对这篇文章的评论关闭!