运营网站,wordpress y郁思注意,杭州网站设计工作室,网站建设需要目录
前言#xff1a;
一、二叉搜索树
1.1二叉搜索树概念
2.2 二叉搜索树操作
1. 二叉搜索树的插入
1.1、插入过程
1.2、代码实现
2、二叉树的删除
2.1、结点删除情况
2.2、替换删除法
1、替换思路
2、代码实现#xff1a;
3、二叉搜索树的查找
3.1、查找规则 …目录
前言
一、二叉搜索树
1.1二叉搜索树概念
2.2 二叉搜索树操作
1. 二叉搜索树的插入
1.1、插入过程
1.2、代码实现
2、二叉树的删除
2.1、结点删除情况
2.2、替换删除法
1、替换思路
2、代码实现
3、二叉搜索树的查找
3.1、查找规则
3.2、代码实现 二、二叉搜索树的应用
1. K模型
2、KV模型
三、二叉搜索树的性能分析 前言
1. map和set特性需要先铺垫二叉搜索树而二叉搜索树也是一种树形结构
2. 二叉搜索树的特性了解有助于更好的理解map和set的特性
3. 二叉树中部分面试题稍微有点难度在前面讲解大家不容易接受且时间长容易忘
4. 有些OJ题使用C语言方式实现比较麻烦比如有些地方要返回动态开辟的二维数组非常麻 烦。
一、二叉搜索树
1.1二叉搜索树概念
二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树:若它的左子树不为空则左子树上所有节点的值都小于根节点的值若它的右子树不为空则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树 2.2 二叉搜索树操作
树的框架
//结点
templateclass K
struct BSTreeNode
{BSTreeNodeK* _left;BSTreeNodeK* _right;K _key;BSTreeNode(const K key):_left(nullptr), _right(nullptr), _key(key){}
};
//二叉搜索树的操作
templateclass K
class BSTree
{typedef BSTreeNodeK Node;
private:Node* _root nullptr;
}; 1. 二叉搜索树的插入
1.1、插入过程
插入的具体过程如下
a. 树为空则直接新增节点赋值给root指针
b. 树不空按二叉搜索树性质查找插入位置插入新节点
解释假设我们要插入16、0那我们就要根据二叉搜索树的特点来进行判断想要插入16从根节点开始如果比根节点大那么就走右子树继续比较。如果比根节点小那么就走左子树继续比较 所以我们的插入功能应该如何写呢?
1.2、代码实现
bool Insert(const K key)
{
//判断二叉树是否为空if (_root nullptr){_root new Node(key);return true;}Node* parent nullptr;Node* cur _root;
//进行插入while (cur){if (cur-_key key){parent cur;cur cur-_right;}else if (cur-_key key){parent cur;cur cur-_left;}else{return false;}}
//找到插入位置并新开辟一个结点cur new Node(key);if (parent-_key key){parent-_right cur;}else{parent-_left cur;}return true;
}
细节解释
1、我们最开始需要判断二叉树是否为空如果不判断cur就为空就不会进入循环判断的同时之后parent指向结点为野指针不安全
2、在我们循环判断时需要记录cur的父节点cur最终找到的是插入位置如果我们想成功插入那么就需要由该位置的父节点进行链接
2、二叉树的删除
2.1、结点删除情况 首先查找元素是否在二叉搜索树中如果不存在则返回, 否则要删除的结点可能分下面四种情 况
a. 要删除的结点无孩子结点
b. 要删除的结点只有左孩子结点
c. 要删除的结点只有右孩子结点
d. 要删除的结点有左、右孩子结点
看起来有待删除节点有4中情况实际情况a可以与情况b或者c合并起来因此真正的删除过程如下
情况a直接删除
情况b删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除
情况c删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除
情况d在它的右子树中寻找中序下的第一个结点(关键码最小)用它的值填补到被删除节点 中再来处理该结点的删除问题--替换法删除
情况a、b、c都好理解情况a直接删除即可情况bc是让被删除结点的孩子去顶替它的位置即可
难的是情况d,当它有两个孩子时应该怎么去选择我们所用到的替换法删除又是什么呢
2.2、替换删除法
1、替换思路 我们所找的去替换被删除结点的值最重要的是能在该位置站得住脚---就是要比左孩子大又要比右孩子小 那哪些结点能站得住脚呢 是被删除结点的左子树的最大结点右结点或者右子树的最小结点左结点 怎么理解我们知道父结点的左子树上的值都要比父结点小父结点的右子树上的值都要比父结点大。我们再拿父结点的左孩子来说同理比它小的值也同样会走到它的左子树上比它大的值也同样会走到它的右子树上。 那么我们就可以明白被删除结点的左子树的最大右节或者右子树的最小左结点一定会比被删除结点的左孩子大又比其右孩子小 这也是搜索二叉数的特征一棵树的左子树的最右节点是左子树的最大结点一棵树的右子树的最左结点是右子树的最小结点 另外需要注意的是我们被删除结点的左子树的最大结点右结点或者右子树的最小结点左结点是可以直接删除的我们在上面已经分析过删除情况。
2、代码实现
情况b、c再删除时又会遇到的情况
1、被删除结点的左子树为空 假如我们要删除结点3且被删除结点的左子树为空我们被删除结点的父结点就要链接被删除结点的右子树
2、被删除结点的右子树为空 假如我们要删除结点3且被删除结点的右子树为空我们被删除结点的父结点就要链接被删除结点的左子树
情况d:
我们知道
1、找被删除结点的左子树的最大右结点或者右子树的最左小结点这个在后面的理解很重要
2、一棵树的左子树的最右节点是左子树的最大结点一棵树的右子树的最左结点是右子树的最小结点 所以我们需要先找到一个能站得住脚的结点我们就拿右子树的最小结点举例将它命名为rightMin 我们找到rightMin再去将被删除结点与rightMin结点的值key交换并且在找rightMin时再用一个中间变量rightMinParent去记录rightMin的父结点最终在交换完key后我们需要删除交换后的rightMin就需要由父结点来链接。 此时又会遇到两种情况
1、rightMin如果是父结点rightMinParent的左结点我们就需要让rightMinParent去链接rightMin的右节点如果存在即链接不存在即为空
2、1、rightMin如果是父结点rightMinParent的右结点我们就需要让rightMinParent去链接rightMin的右节点如果存在即链接不存在即为空
删除函数代码
bool Erase(const K key){Node* parent nullptr;Node* cur _root;while (cur){if (cur-_key key){parent cur;cur cur-_right;}else if (cur-_key key){parent cur;cur cur-_left;}else{// 删除// 左为空父亲指向我的右// 先判断删除的是不是头结点if (cur-_left nullptr){//if(parent nullptr)if (cur _root){_root cur-_right;}else{if (cur parent-_left){parent-_left cur-_right;}else{parent-_right cur-_right;}}delete cur;}else if (cur-_right nullptr){//if(parent nullptr)if (cur _root){_root cur-_left;}else{// 右为空父亲指向我的左if (cur parent-_left){parent-_left cur-_left;}else{parent-_right cur-_left;}}delete cur;}else{// 左右都不为空替换法删除// // 查找右子树的最左节点替代删除Node* rightMinParent cur;Node* rightMin cur-_right;while (rightMin-_left){rightMinParent rightMin;rightMin rightMin-_left;}swap(cur-_key, rightMin-_key);if (rightMinParent-_left rightMin)rightMinParent-_left rightMin-_right;elserightMinParent-_right rightMin-_right;delete rightMin;}return true;}}return false;}3、二叉搜索树的查找
3.1、查找规则
a、从根开始比较查找比根大则往右边走查找比根小则往左边走查找。
b、最多查找高度次走到空还没找到这个值不存在
3.2、代码实现
bool Find(const K key)
{Node* cur _root;while (cur){if (cur-_key key){cur cur-_right;}else if (cur-_key key){cur cur-_left;}else{return true;}}return false;
} 二、二叉搜索树的应用
1. K模型 K模型即只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到 的值。 比如给一个单词word判断该单词是否拼写正确。 具体方式如下
以词库中所有单词集合中的每个单词作为key构建一棵二叉搜索树在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误。
这个我们需要一个词库所以我们在这里先不做这个实现我们用KV模型来实现
2、KV模型
每一个关键码key都有与之对应的值Value即的键值对。该种方 式在现实生活中非常常见
比如英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英 文单词与其对应的中文就构成一种键值对再比如统计单词次数统计成功后给定单词就可快速找到其出现的次数单词与其出 现次数就是就构成一种键值对。
我们先将KV模型代码写出来
namespace key_value
{templateclass K, class Vstruct BSTreeNode{BSTreeNodeK, V* _left;BSTreeNodeK, V* _right;K _key;V _value;// pairK, V _kv;BSTreeNode(const K key, const V value):_left(nullptr), _right(nullptr), _key(key), _value(value){}};templateclass K, class Vclass BSTree{typedef BSTreeNodeK, V Node;public:// logNbool Insert(const K key, const V value){if (_root nullptr){_root new Node(key, value);return true;}Node* parent nullptr;Node* cur _root;while (cur){if (cur-_key key){parent cur;cur cur-_right;}else if (cur-_key key){parent cur;cur cur-_left;}else{return false;}}cur new Node(key, value);if (parent-_key key){parent-_right cur;}else{parent-_left cur;}return true;}Node* Find(const K key){Node* cur _root;while (cur){if (cur-_key key){cur cur-_right;}else if (cur-_key key){cur cur-_left;}else{return cur;}}return cur;}bool Erase(const K key){Node* parent nullptr;Node* cur _root;while (cur){if (cur-_key key){parent cur;cur cur-_right;}else if (cur-_key key){parent cur;cur cur-_left;}else{// 删除// 左为空父亲指向我的右if (cur-_left nullptr){//if(parent nullptr)if (cur _root){_root cur-_right;}else{if (cur parent-_left){parent-_left cur-_right;}else{parent-_right cur-_right;}}delete cur;}else if (cur-_right nullptr){//if(parent nullptr)if (cur _root){_root cur-_left;}else{// 右为空父亲指向我的左if (cur parent-_left){parent-_left cur-_left;}else{parent-_right cur-_left;}}delete cur;}else{// 左右都不为空替换法删除// // 查找右子树的最左节点替代删除Node* rightMinParent cur;Node* rightMin cur-_right;while (rightMin-_left){rightMinParent rightMin;rightMin rightMin-_left;}swap(cur-_key, rightMin-_key);if (rightMinParent-_left rightMin)rightMinParent-_left rightMin-_right;elserightMinParent-_right rightMin-_right;delete rightMin;}return true;}}return false;}void InOrder(){_InOrder(_root);cout endl;}private:void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_key : root-_value endl;_InOrder(root-_right);}private:Node* _root nullptr;};
这也只是在我们原先实现的基础上做改动。
示例一翻译单词
void TestBSTree2()
{BSTreestring, string dict;dict.Insert(string, 字符串);dict.Insert(left, 左边);dict.Insert(insert, 插入);//...string str;while (cin str){BSTreeNodestring, string* ret dict.Find(str);if (ret){cout ret-_value endl;}else{cout 无此单词请重新输入 endl;}}
}
示例二计数
void TestBSTree3(){// 统计次数string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜,
苹果, 香蕉, 苹果, 香蕉,苹果,草莓, 苹果,草莓};BSTreestring, int countTree;for (const auto str : arr){auto ret countTree.Find(str);if (ret nullptr){countTree.Insert(str, 1);}else{ret-_value;}}countTree.InOrder();}
}
三、二叉搜索树的性能分析
插入和删除操作都必须先查找查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是结点在二 叉搜索树的深度的函数即结点越深则比较次数越多。
但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树 最优情况下二叉搜索树为完全二叉树(或者接近完全二叉树)其平均比较次数为$log_2 N$
最差情况下二叉搜索树退化为单支树(或者类似单支)其平均比较次数为$\frac{N}{2}$
