一、搜索树的复杂度分析
- 本文考察二叉搜索树和索引二叉搜索树
- 二叉搜索树的渐进性能可以和跳表媲美：
- 查找、插入、删除操作所需的平均时间为Θ(logn)
- 查找、插入、删除操作的最坏情况的时间为Θ(n)
- 元素按升序输出时所需时间为Θ(n)
- 虽然在最坏情况下的查找、插入、删除操作，散列表和二叉搜索树的时间性能相同，但是散列表在最好的情况下具有超级性能Θ(1)
- 不过，对于一个指定的关键字，使用二叉搜索树，你可以在Θ(n)时间内，找到最接近它的关键字。例如，给定关键字是k，你可以在Θ(n)时间内，找到最接近k的关键字（即小于等于k的最大关键字，或大于等于k的最小关键字）。而对于散列表来说，这种操作的时间是Θ(n+D)（其中D是散列表除数）；对跳表来说，这种操作的时间是Θ(logn)
- 索引二叉搜索树：
- 使用索引二叉搜索树，你可以按关键字和按名次进行字典操作，例如读取关键字从小打到排名第10的元素，删除关键字从小打到第100的元素。按名次的操作和按关键字的操作，其时间性能一样
- 索引二叉树可以用来表示线性表；其中的元素具有名次（即索引），没有关键字。在这种线性表的表示中，get、erase、insert操作的时间性能为O(logn)，但是前面实现的线性表，这些操作的时间为Θ(n)（不过get操作在用数组实现时，其性能是Θ(1)）
- 总结，对于二叉搜索树和跳表来说，在最坏和最好情况下的渐近时间复杂性是相同的。但是，我们可以对二叉搜索树加以平衡限制，使上述的每一个操作耗时都是Θ(logn)
二、搜索树的高效性
- 在一篇文章中我们引入了抽象数据类型dictionary：https://blog.csdn.net/qq_41453285/article/details/103449056
- 在另一篇文章中（https://blog.csdn.net/qq_41453285/article/details/103533372、https://blog.csdn.net/qq_41453285/article/details/103534526）我们有散列表来描述字典，字典操作（查找、插入、删除）所需要的平均时间为Θ(1)。而这些操作在最坏情况下的时间与字典的元素个数n呈线性关系
- 如果给dictionaty增加以下操作，那么散列不再具有较好的平均性能：
- 1.按关键字的升序输出字典元素
- 2.按升序找到第k个元素
- 3.删除第k个元素
- 如果使用平衡搜索树，那么对字典的基本操作（查找、插入、删除）能够在O(logn)的时间内完成，上述1操作能在Θ(n)时间内完成。使用索引平衡搜索树，我们也能在O(logn)的时间内完成上述操作2和3
三、二叉搜索树
- 概述：二叉搜索树是一棵二叉树，可能为空
- 一棵非空的二叉搜索树满足以下特征：
- 1.每个元素都有一个关键字，并且任意两个元素的关键字都不同；因此，所有的关键字都是唯一的（其实也可以不唯一，见下）
- 2.在根节点的左子树中，元素的关键字（如果有的话）都小于根节点的关键字
- 3.在根节点的右子树中，元素的关键字（如果有的话）都大于根节点的关键字
- 4.根节点的左、右子树也都是二叉搜索树
- 例如下面图a)不是二叉搜索树，图b)和c)都是二叉搜索树
- 如果关键字不唯一，那么这样的二叉树称为“有重复值的二叉搜索树”
二叉搜索树的查找
- 二叉搜索树的查找步骤如下：
- 1.从根开始，如果根节点为空，就停止搜索；如果不为空，进行第2步
- 2.将要查找的元素与根节点进行比较，如果比根节点值小，就向左孩子查找；如果比根节点值大，就向右孩子查找
- 3.重复2步骤，只要比某个节点值小就向左孩子查找；只要比某个节点值大，就向右孩子查找
- 4.查找到之后返回查找的节点，如果没查找就返回空
二叉搜索树的插入
- 二叉搜索树的插入步骤如下：
- 1.从根开始，如果根节点为空，就将新节点作为根节点；如果不为空进行第二步
- 2.将要插入的节点与根节点相比较，遇键值较大者就向左，遇键值较小者就向右
- 3.如果遇到节点的值与插入节点的值相同就退出停止插入（或做其他处理）
- 4.一直到尾端，即为插入点
- 例如：
二叉搜索树的删除
- 删除节点p，要考虑3种情况：
- 1.p是树叶
- 2.p只有一棵非空子树
- 3.p有两颗非空子树
- ①如果删除的是树叶：
- 1.如果删除的节点是叶节点：就释放该叶节点。例如，下面删除图a中的节点35，直接将其父节点40的左孩子域置为NULL即可，结果如图b所示
- 2.如果删除的节点是根节点（说明树总共只有一个节点）：直接令根为NULL
- ②如果删除的节点只有一棵非空子树：
- 1.如果删除的节点是根节点：就另其唯一的子节点作为新的根节点
- 2.如果删除的节点不是根节点：直接将其子节点连至其父节点即可。例如下图想要删除节点5，直接将其子节点2作为父节点30的子节点即可
- ②如果删除的节点有两棵非空子树：
- 那么就将删除的节点替换为它的左子树中的最大元素或者替换为它的右子树中的最小元素
- 查找左子树的最大元素：先指向于左子树，然后一直向左子树的右子树进行查找，直到右孩子指针为NULL为止
- 查找右子树的最小元素：先指向于右子树，然后一直向右子树的左子树进行查找，直到左孩子指针为NULL为止
- 例如下面我们想删除图a中关键字为40的节点，既可以用右子树中的最小元素60来代替（如下图b所示），也可以用其左子树中的最大元素35来代替（如下图c所示）
四、索引二叉搜索树
- 概述：源于普通的二叉搜索树，只是在每个节点中添加一个leftSize域。这个域的值是该节点左子树的元素个数
- 下图是两棵索引二叉搜索树。节点内部的数字是元素的关键字，节点外的数组是leftSize的值
leftSize域索引的作用：
- leftSize同时给出了一个元素的索引（该元素的左子树的元素排在该元素之前）
- 例如在上图中：
- 元素按顺序分别为：12、15、18、20、25、30。按照线性表的形式（e0、e1、...e4）
- 根的索引时3，它等于根元素的leftSize域的值
- 在根为25的子树中，元素按顺序排列为25/30，根元素25的索引时0，而leftSize的值也是0
索引二叉搜索树的查找
- 带有索引的搜索方法与搜索偶对（一个偶对被定义为关键字域key和值域value）的方法是类似的
- 假设我们要查找索引为2的元素：
- 跟的leftSize域的值是3，因此，我们要查找的元素在根的左子树中（进一步说，我们要查找的元素在左子树的索引为2）
- 因为左子树的根（即15）的leftSize域的值为1，所以我们要查找的元素在15的右子树中
- 然而，在15的右子树中，待查元素的索引不再是2，因为15的右子树元素都排在15的左子树元素和15之后
- 为了确定待查元素在15的右子树中的索引，我们要用2减去leftSize+1（其中leftSize是15的leftSize值(1)），结果为2-(1+1)
- 15的右子树的根是18，它的leftSize域的值是0，因此待查元素便是18
- 所需时间为O(h)，其中h是索引搜索树的高
索引二叉搜索树的插入
- 把一个元素插入索引二叉搜索树中，使用的过程类似于下面我们实现的二叉搜索树的find()函数（见下面代码）
- 不过要在根至新插入节点的路径上修改leftSize域的值
- 所需时间为O(h)，其中h是索引搜索树的高
索引二叉搜索树的删除
- 通过索引实施删除的过程是：
- 首先按索引进行搜索，确定要删除的元素的位置
- 然后按照上面介绍的二叉搜索树的删除操作进行删除
- 接下来，如果需要，在从根节点到删除节点的路径上更新leftSize域
- 所需时间为O(h)，其中h是索引搜索树的高
五、搜索树的抽象数据类型（ADT）
二叉搜索树的抽象数据模型
索引二叉搜索树的抽象数据类型
- 支持所有二叉搜索树的方法，另外索引二叉搜索树还支持按名次进行查找和删除操作
六、搜索树的抽象类
二叉搜索树的抽象类
- 因为我们的搜索树主要用来实现字典，所以我们直接让二叉搜索树继承于字典抽象类
- 字典抽象类dictionary可以参见文章：https://blog.csdn.net/qq_41453285/article/details/103448760
索引二叉搜索树
- 索引二叉搜索树具有二叉搜索树的全部方法（所以继承于bsTree就好），并且另外还支持按名次进行查找和删除操作
七、二叉搜索树的编码实现
- 下面我们来实现二叉搜索树，其中每个节点都是一个字典（pair数据类型）
- 我们在前面文章（https://blog.csdn.net/qq_41453285/article/details/103638694）介绍二叉树时，并用linkedBinaryTree类实现了二叉树的链表形式，现在我们的二叉搜索树类binarySearchTree从linkedBinaryTree直接继承而来，然后将元素节点类型改为pair<K,E>即可（K为关键字类型，E为关键字所对应的元素的数据类型）
头文件定义
字典类定义
二叉搜索树抽象类定义
- 二叉搜索树用来实现字典，所以从字典继承而来
二叉搜索树实现（binarySearchTree）
按关键字升序输出二叉树（ascend）
- 按关键字升序输出搜索二叉树，又由于binarySearchTree继承于linkedBinaryTree，所以直接调用linkedBinaryTree中的后续打印函数inOrderOutput()即可
linkedBinaryTree中的__output函数需要改动一下
- 因为现在节点的数据类型为pair了，所以打印时不能直接打印pair数据类型，而是pair.first
static void __output(binaryTreeNode<T>* theNode) { std::cout << theNode->element.second << " "; }判断是否为空（empty()）、返回大小（size()）
- empty()：判断树是否为空
- size()：判断树的大小
查找节点函数（find）
- 根据上面二叉搜索树的查找规则，根据关键字进行查找
插入节点函数（insert）
- 根据上面二叉搜索树的插入规则，先遍历到搜索树的最后一个节点，然后进行插入
节点的删除函数（erase）
- 通过上面的删除规则，我们定义了如下函数，在函数中，如果要删除的节点有两颗非空子树，我们统一用左子树中的最大元素来进行替换
- 因为元素的数据类型为paie<const K,E>，这种删除操作时复杂的，而且改变关键字也是可能的，所以该算法的复杂性为O(h)
主函数
八、代码下载
九、带有相同关键字元素的二叉搜索树
- 如果二叉搜索树可以带有相同的关键字，只需要把上面程序中的insert函数的while循环中的语句的else if中的<改为<=即可
-
while (tempNode !=
NULL)
-
{
-
insertNode = tempNode;
-
-
if (tempNode->element.first > theElement.first)
-
tempNode = tempNode->leftChild;
-
else
if (tempNode->element.first <= theElement.first)
-
tempNode = tempNode->rightChild;
-
else {
-
tempNode->element.second = theElement.second;
-
return;
-
}
-
}
十、索引二叉搜索树编码实现
- 如果用编码实现索引二叉搜索树（indexedBinartSearchTree），一个节点的数值域是三元的：leftSize、key、value
转载：https://blog.csdn.net/qq_41453285/article/details/103963343
查看评论