广告制作公司转型,云南网站建设优化企业,阿里巴巴怎么做自己的免费网站,个人网页设计作品欣赏前言 作者#xff1a;小蜗牛向前冲 名言#xff1a;我可以接受失败#xff0c;但我不能接受放弃 如果觉的博主的文章还不错的话#xff0c;还请点赞#xff0c;收藏#xff0c;关注#x1f440;支持博主。如果发现有问题的地方欢迎❀大家在评论区指正。 目录
一、二叉搜… 前言 作者小蜗牛向前冲 名言我可以接受失败但我不能接受放弃 如果觉的博主的文章还不错的话还请点赞收藏关注支持博主。如果发现有问题的地方欢迎❀大家在评论区指正。 目录
一、二叉搜索树的基本知识
1、什么是二叉搜索树
2、二叉搜索树的性能分析
二、底层模拟实现
1、构建二叉搜索树
2、二叉搜索树的查找
3、二叉搜索树的插入
4、二叉搜索树的删除节点 5、完整代码实现
三、二叉搜索树的应用
1、K模型
2、KV模型 本期学习目标清楚什么是二叉搜索树模拟实现二叉搜索树理解二叉搜索树的K模型和KV模型。
一、二叉搜索树的基本知识
1、什么是二叉搜索树
二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树: 若它的左子树不为空则左子树上所有节点的值都小于根节点的值若它的右子树不为空则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树 二叉搜索树的这种特性使得在其中进行搜索、插入和删除操作具有高效性能。通过对节点值的比较我们可以迅速定位目标节点或确定应插入的位置。 上图中就是二叉搜索树的构成他满足所有左叶子节点比跟小所以的右叶子节点比根要大。
为了更好的理解二叉搜索树下面将带来大家底层实现二叉搜索树的查找插入删除。
2、二叉搜索树的性能分析
对有n个结点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是结点在二 叉搜索树的深度的函数即结点越深则比较次数越多
但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树 最优情况下二叉搜索树为完全二叉树(或者接近完全二叉树)其平均比较次数为O(log n)最差情况下二叉搜索树退化为单支树(或者类似单支)其平均比较次数为O(n) 二、底层模拟实现
1、构建二叉搜索树
templateclass Kstruct BSTreeNode{BSTreeNodeK* _left;BSTreeNodeK* _right;K _key;BSTreeNode(const K key):_key(key), _left(nullptr), _right(nullptr){}};templateclass Kclass BSTree{typedef BSTreeNodeK Node;public://函数private:Node* _root nullptr;}
这里我们定义好节点和树的主体就好了下面我的二叉搜索树的功能函数多在类中实现。
2、二叉搜索树的查找
现在给我们一颗搜索二叉树那我们是如何让他查找到我们想要的元素 查找原则 从根开始比较查找比根大则往右边走查找比根小则往左边走查找。最多查找高度次走到到空还没找到这个值不存在。 顺着这个思路我们很容易思路就可以写出查找
普通写法
//查找
bool Find(const K key)
{Node* cur _root;while (cur){if (cur-_key key){cur cur-_left;}else if (cur-_key key){cur cur-_right;}else{return true;}}return false;
}
递归写法
bool _FindR(Node* root, const K key)
{if (root nullptr){return false;}if (root-_key key){return _FindR(root-_right, key);}else if (root-_key key){return _FindR(root-_left, key);}else{return true;}
}
这二种写法在这里好像看不出来特别大的差别。
3、二叉搜索树的插入 这里我们思考一下如果我们要在1处插入 0 我们要找到插入的位置。然后在new一个节点进连接就可以 插入的具体过程如下 a. 树为空则直接新增节点赋值给root指针 b. 树不空按二叉搜索树性质查找插入位置插入新节点 普通写法 bool Inert(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-_left;}else if (cur-_key key){parent cur;cur cur-_right;}else{return false;}}//创建节点cur new Node(key);//连接树if (parent-_key key){parent-_left cur;}else{parent-_right cur;}return true;}
递归写法 bool _InsertR(Node* root, const K key){if (root nullptr){root new Node(key);return true;}if (root-_key key){return _InsertR(root-_right, key);}else if (root-_key key){return _InsertR(root-_left, key);}else{return false;}}
递归写法最让我们感到绝妙的是我们在这里传root用的是引用因为用递归时(如果没有用root的引用)并没有传父亲节点这也就在连接的时候会遇到到问题但是我们这里传了root的引用就可以解决这个问题
这里当我们要插入9到我们递归到root 10时候,在进行递归时会往root-left递归指向空,就可以插入而root是root-left指针的别名就可以完美的连接起来。
4、二叉搜索树的删除节点
这里是本次模拟的难点所在大家可以细细品味
首先查找元素是否在二叉搜索树中如果不存在则返回, 否则要删除的结点可能分下面四种情 况 a. 要删除的结点无孩子结点b. 要删除的结点只有左孩子结点c. 要删除的结点只有右孩子结点d. 要删除的结点有左、右孩子结点 其实我们可以总结为3种删除情况 情况1删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除情况2删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除情况3在它的右子树中寻找中序下的第一个结点(关键码最小)用它的值填补到被删除节点 中再来处理该结点的删除问题--替换法删除 普通写法
这里我们重点注意第三种情况这里我们是找左树的最大或者说是右树的最小和我们要删除的数进行替换在删除就可以了。
//删除
bool Erase(const K key)
{Node* parent nullptr;Node* cur _root;while (cur){//先找到要删除的数if (cur-_key key){parent cur;cur cur-_left;}else if (cur-_key key){parent cur;cur cur-_right;}else{//1、左为空//2、右为空// 1.2都可以直接删除//在直接删除前我们还要做好cur的左右节点的链接工作并处理特殊情况(cur_root)if (cur-_left nullptr){//处理特殊情况if (cur _root){_root cur-_right;}else{if (parent-_left cur){parent-_left cur-_right;}else{parent-_right cur-_right;}}delete cur;}else if (cur-_right nullptr){//处理特殊情况if (cur _root){_root cur-_left;}else{if (parent-_left cur){parent-_left cur-_left;}else{parent-_right cur-_left;}}delete cur;}
递归写法
bool _EraseR(Node* root, const K key)
{if (root nullptr){return false;}//先找到要删除的位置if (root-_key key){return _EraseR(root-_right, key);}else if (root-_key key){return _EraseR(root-_left, key);}else{Node* del root;if (root-_right nullptr){root root-_left;}else if (root-_left nullptr){root root-_right;}else{Node* minRight root-_right;while (minRight-_left){minRight minRight-_left;}swap(root-_key, minRight-_key);//转换为在子树中删除节点return _EraseR(root-_right, key);}delete del;return true;}
} 5、完整代码实现
namespace K
{templateclass Kstruct BSTreeNode{BSTreeNodeK* _left;BSTreeNodeK* _right;K _key;BSTreeNode(const K key):_key(key), _left(nullptr), _right(nullptr){}};templateclass Kclass BSTree{typedef BSTreeNodeK Node;public://默认构造BSTree():_root(nullptr){}//构造函数BSTree(const BSTreeK t){_root Copy(t._root);}//赋值重载BSTreeK operator(BSTreeK t){swap(_root, t._root);return *this;}//析构函数~BSTree(){Destroy(_root);_root nullptr;}//搜索二插树插入bool Inert(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-_left;}else if (cur-_key key){parent cur;cur cur-_right;}else{return false;}}//创建节点cur new Node(key);//连接树if (parent-_key key){parent-_left cur;}else{parent-_right cur;}return true;}//查找bool Find(const K key){Node* cur _root;while (cur){if (cur-_key key){cur cur-_left;}else if (cur-_key key){cur cur-_right;}else{return true;}}return false;}//删除bool Erase(const K key){Node* parent nullptr;Node* cur _root;while (cur){//先找到要删除的数if (cur-_key key){parent cur;cur cur-_left;}else if (cur-_key key){parent cur;cur cur-_right;}else{//1、左为空//2、右为空// 1.2都可以直接删除//在直接删除前我们还要做好cur的左右节点的链接工作并处理特殊情况(cur_root)if (cur-_left nullptr){//处理特殊情况if (cur _root){_root cur-_right;}else{if (parent-_left cur){parent-_left cur-_right;}else{parent-_right cur-_right;}}delete cur;}else if (cur-_right nullptr){//处理特殊情况if (cur _root){_root cur-_left;}else{if (parent-_left cur){parent-_left cur-_left;}else{parent-_right cur-_left;}}delete cur;}//3、左右都不为空//找cur右子数的最小节点else{Node* parent cur;Node* minRight cur-_right;while (minRight-_left){parent minRight;minRight minRight-_left;}cur-_key minRight-_key;//连接if (parent-_left minRight){parent-_left minRight-_right;}else{parent-_right minRight-_right;}//删除节点delete minRight;}return true;}}return false;}void InOrder(){_InOrder(_root);cout endl;}bool InsertR(const K key){return _InsertR(_root, key);}bool FindR(const K key){return _FindR(_root, key);}bool EraseR(const K key){return _EraseR(_root, key);}//递归写法完成增删查改private:void Destroy(Node* root){if (root nullptr){return;}Destroy(root-_left);Destroy(root-_right);delete root;}//拷贝节点Node* Copy(Node* root){if (root nullptr){return nullptr;}Node* newRoot new Node(root-_key);newRoot-_left Copy(root-_left);newRoot-_right Copy(root-_right);return newRoot;}void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);}bool _InsertR(Node* root, const K key){if (root nullptr){root new Node(key);return true;}if (root-_key key){return _InsertR(root-_right, key);}else if (root-_key key){return _InsertR(root-_left, key);}else{return false;}}bool _FindR(Node* root, const K key){if (root nullptr){return false;}if (root-_key key){return _FindR(root-_right, key);}else if (root-_key key){return _FindR(root-_left, key);}else{return true;}}bool _EraseR(Node* root, const K key){if (root nullptr){return false;}//先找到要删除的位置if (root-_key key){return _EraseR(root-_right, key);}else if (root-_key key){return _EraseR(root-_left, key);}else{Node* del root;if (root-_right nullptr){root root-_left;}else if (root-_left nullptr){root root-_right;}else{Node* minRight root-_right;while (minRight-_left){minRight minRight-_left;}swap(root-_key, minRight-_key);//转换为在子树中删除节点return _EraseR(root-_right, key);}delete del;return true;}}private:Node* _root nullptr;};
}
三、二叉搜索树的应用
1、K模型
K模型K模型即只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到 的值。 比如给一个单词word判断该单词是否拼写正确具体方式如下 以词库中所有单词集合中的每个单词作为key构建一棵二叉搜索树 在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误。
这里就是我们完整实现的二叉树这里我们用二叉搜索树的查找功能如果该单词存在树中就会返回true否则返回false。
2、KV模型
KV模型每一个关键码key都有与之对应的值Value即的键值对。该种方 式在现实生活中非常常见 比如英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英 文单词与其对应的中文就构成一种键值对再比如统计单词次数统计成功后给定单词就可快速找到其出现的次数单词与其出 现次数就是就构成一种键值对。 这里我们上面代码进行简单改造就可以得到我们的KV模型
namespace KV
{templateclass K, class Vstruct BSTreeNode{BSTreeNodeK, V* _left;BSTreeNodeK, V* _right;K _key;V _value;BSTreeNode(const K key, const V value):_key(key), _value(value), _left(nullptr), _right(nullptr){}};//BSTreestring, vectorstring bookInfo;templateclass K, class Vclass BSTree{typedef BSTreeNodeK, V Node;public:bool 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 nullptr;}void Inorder(){_Inorder(_root);}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()
{
// Key/Value的搜索模型,通过Key查找或修改ValuKV::BSTreestring, string dict;dict.Insert(sort, 排序);dict.Insert(string, 字符串);dict.Insert(left, 左边);dict.Insert(right, 右边);string str;while (cin str){KV::BSTreeNodestring, string* ret dict.Find(str);if (ret){cout ret-_value endl;}else{cout 无此单词 endl;}}
} 这里我们对改造的二叉搜索树就可以进行通过英文快速找到英文。
