二叉搜索树操作

map和set特性需要先铺垫二叉搜索树而二叉搜索树也是一种树形结构

二叉树中部分面试题稍微有点难度在前面讲解大家不容易接受且时间长容易忘

有些OJ题使用C语言方式实现比较麻烦比如有些地方要返回动态开辟的二维数组非常麻

一、二叉搜索树

二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树:若它的左子树不为空则左子树上所有节点的值都小于根节点的值若它的右子树不为空则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树

2.2

解释假设我们要插入16、0那我们就要根据二叉搜索树的特点来进行判断想要插入16从根节点开始如果比根节点大那么就走右子树继续比较。

如果比根节点小那么就走左子树继续比较

1.2、代码实现

1、我们最开始需要判断二叉树是否为空如果不判断cur就为空就不会进入循环判断的同时之后parent指向结点为野指针不安全

2、在我们循环判断时需要记录cur的父节点cur最终找到的是插入位置如果我们想成功插入那么就需要由该位置的父节点进行链接

2.1、结点删除情况

看起来有待删除节点有4中情况实际情况a可以与情况b或者c合并起来因此真正的删除过程如下

情况a直接删除

情况b删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除

情况c删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除

情况d在它的右子树中寻找中序下的第一个结点(关键码最小)用它的值填补到被删除节点

情况a、b、c都好理解情况a直接删除即可情况bc是让被删除结点的孩子去顶替它的位置即可

难的是情况d,当它有两个孩子时应该怎么去选择我们所用到的替换法删除又是什么呢

2.2、替换删除法

我们所找的去替换被删除结点的值最重要的是能在该位置站得住脚---就是要比左孩子大又要比右孩子小

那哪些结点能站得住脚呢

是被删除结点的左子树的最大结点右结点或者右子树的最小结点左结点

怎么理解我们知道父结点的左子树上的值都要比父结点小父结点的右子树上的值都要比父结点大。

我们再拿父结点的左孩子来说同理比它小的值也同样会走到它的左子树上比它大的值也同样会走到它的右子树上。

那么我们就可以明白被删除结点的左子树的最大右节或者右子树的最小左结点一定会比被删除结点的左孩子大又比其右孩子小

这也是搜索二叉数的特征一棵树的左子树的最右节点是左子树的最大结点一棵树的右子树的最左结点是右子树的最小结点

另外需要注意的是我们被删除结点的左子树的最大结点右结点或者右子树的最小结点左结点是可以直接删除的我们在上面已经分析过删除情况。

2、代码实现

假如我们要删除结点3且被删除结点的左子树为空我们被删除结点的父结点就要链接被删除结点的右子树

假如我们要删除结点3且被删除结点的右子树为空我们被删除结点的父结点就要链接被删除结点的左子树

情况d:

1、找被删除结点的左子树的最大右结点或者右子树的最左小结点这个在后面的理解很重要

2、一棵树的左子树的最右节点是左子树的最大结点一棵树的右子树的最左结点是右子树的最小结点

所以我们需要先找到一个能站得住脚的结点我们就拿右子树的最小结点举例将它命名为rightMin

我们找到rightMin再去将被删除结点与rightMin结点的值key交换并且在找rightMin时再用一个中间变量rightMinParent去记录rightMin的父结点最终在交换完key后我们需要删除交换后的rightMin就需要由父结点来链接。

此时又会遇到两种情况

1、rightMin如果是父结点rightMinParent的左结点我们就需要让rightMinParent去链接rightMin的右节点如果存在即链接不存在即为空

2、1、rightMin如果是父结点rightMinParent的右结点我们就需要让rightMinParent去链接rightMin的右节点如果存在即链接不存在即为空

删除函数代码

(rightMin-_left){rightMinParent

rightMin;rightMin

rightMin-_right;elserightMinParent-_right

rightMin;}return

a、从根开始比较查找比根大则往右边走查找比根小则往左边走查找。

3.2、代码实现

K模型即只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到

具体方式如下

以词库中所有单词集合中的每个单词作为key构建一棵二叉搜索树在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误。

这个我们需要一个词库所以我们在这里先不做这个实现我们用KV模型来实现

2、KV模型

每一个关键码key都有与之对应的值Value即的键值对。

该种方

式在现实生活中非常常见

比如英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英

文单词与其对应的中文就构成一种键值对再比如统计单词次数统计成功后给定单词就可快速找到其出现的次数单词与其出

我们先将KV模型代码写出来

(rightMin-_left){rightMinParent

rightMin;rightMin

rightMin-_right;elserightMinParent-_right

rightMin;}return

nullptr){return;}_InOrder(root-_left);cout

root-_key

endl;_InOrder(root-_right);}private:Node*

_root

1);}else{ret-_value;}}countTree.InOrder();}

插入和删除操作都必须先查找查找效率代表了二叉搜索树中各个操作的性能。

对有n个结点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是结点在二

但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树

最优情况下二叉搜索树为完全二叉树(或者接近完全二叉树)其平均比较次数为$log_2

最差情况下二叉搜索树退化为单支树(或者类似单支)其平均比较次数为$\frac{N}{2}$