青海省住房城乡建设厅网站首页,你认为什么对网络营销至关重要,临汾推广型网站开发,如何做网站宣传自己文章目录 1、二叉搜索树1.1 二叉搜索数的概念1.2 二叉搜索树的操作1.2.1 二叉搜索树的查找1.2.2 二叉搜索树的插入1.2.3 二叉搜索树的删除 2、二叉搜索树的应用2.1 K模型2.2 KV模型 3、二叉搜索树的性能分析4、K模型与KV模型完整代码4.1 二叉搜索树的模拟实现#xff08;K模型… 文章目录 1、二叉搜索树1.1 二叉搜索数的概念1.2 二叉搜索树的操作1.2.1 二叉搜索树的查找1.2.2 二叉搜索树的插入1.2.3 二叉搜索树的删除 2、二叉搜索树的应用2.1 K模型2.2 KV模型 3、二叉搜索树的性能分析4、K模型与KV模型完整代码4.1 二叉搜索树的模拟实现K模型4.2 KV模型的模拟实现 1、二叉搜索树
1.1 二叉搜索数的概念
二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树:
若它的左子树不为空则左子树上所有节点的值都小于根节点的值若它的右子树不为空则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树 我们先给出两个示例 此二叉树就不是搜索二叉树根据性质来看每颗子树也是二叉搜索树红圈圈起来的地方显然是违背了这个性质。 此搜索二叉树按性质来看是完全满足的因此此二叉树就是二叉搜索树。
1.2 二叉搜索树的操作
二叉搜索树的操作包含增删查下面我们就来分别模拟实现这些接口。
1.2.1 二叉搜索树的查找
思路 a、从根开始比较查找比根大则往右边走查找比根小则往左边走查找。 b、最多查找高度次走到到空还没找到这个值不存在。 查找比较好理解这里就不画图了直接开始写代码。 1.查找的非递归方法
bool Find(const K key)
{Node* root _root;while (root){if (key root-_key)root root-_right;else if (key root-_key)root root-_left;elsereturn true;}return false;
}2.查找的递归方法
bool FindR(const K key)
{return _FindR(_root, key);
}bool _FindR(Node* root, const K key)
{if (nullptr root)return false;if (key root-_key)return _FindR(root-_right, key);else if (key root-_key)return _FindR(root-_left, key);elsereturn true;
}在递归查找中我们用户在使用的时候只需要填入要查找的数字但是我们的查找接口需要两个参数开始节点与查找数值因此我们在 FindR 下再封装一层 _FindR 就可以实现了。
1.2.2 二叉搜索树的插入
二叉搜索树的插入思路 a. 树为空则直接新增节点赋值给root指针 b. 树不空按二叉搜索树性质查找插入位置插入新节点 我们先来以图例演示一遍过程 对下面这棵树插入一个值为11的节点
这里是成功插入的情况具体过程是上面的图例我们在梳理一遍 1、首先我们用两个结点指针 parent和cur cur不断寻找正确插入位置parent不断记下来cur的父节点指针 2、当 cur 找到正确位置之后先 new 一个节点对象给 cur此时 new 出来的对象只是给了 cur 这个指针变量并没有链接起来 3、判断要插入的位置是 parent 的左孩子还是右孩子再将其链接到正确位置插入就算完成了。 失败情况 因为是二叉搜索树节点左子树的值全小于节点的值右子树的值全大于节点的值不存在相等的情况因此当找到一个节点的值与要插入的值相等时就是插入失败此时返回false。 根据上面的图示以及过程的梳理我们来写非递归版本的代码
bool Insert(const K key)
{if (nullptr _root){_root new Node(key);return true;}Node* parent nullptr;Node* cur _root;while (cur){if (key cur-_key){parnet cur;cur cur-_right;}else if (key cur-_key){parent cur;cur cur-_left;}else{return false;}}cur new Node(key);if (key parent-_key){parent-_right cur;}else{parent-_left cur;}return true;
}insert接口我们只提供非递归版本的。
1.2.3 二叉搜索树的删除
首先查找元素是否在二叉搜索树中如果不存在则返回, 否则要删除的结点可能分下面四种情 况 a. 要删除的结点无孩子结点 b. 要删除的结点只有左孩子结点 c. 要删除的结点只有右孩子结点 d. 要删除的结点有左、右孩子结点 看起来有待删除节点有4中情况实际情况a可以与情况b或者c合并起来因此真正的删除过程 如下 情况b删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点–直接删除 情况c删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点–直接删除 情况d在它的右子树中寻找中序下的第一个结点(关键码最小)用它的值填补到被删除节点 中再来处理该结点的删除问题–替换法删除 1、删除节点没有左孩子
// 1、左为空
if (cur-_left nullptr)
{if (cur _root){_root cur-_right;}if (parent-_left cur){parent-_left cur-_right;}else{parent-_right cur-_right;}
}2、删除节点没有右孩子
// 2、右为空
else if (cur-_right nullptr)
{if (cur _root){_root cur-_left;} if (parent-_left cur){parent-_left cur-_left}else{parent-_right cur-_left;}
}3、删除节点左右孩子都存在
// 3、左右都不为空
else
{Node* parent cur;Node* subLeft cur-_right;while (subLeft-_left){parent subLeft;subLeft subLeft-_left;}swap(cur-_key, subLeft-_key);if (subLeft parent-_left)parent-_left subLeft-_right;elseparent-_right subLeft-_right;delete(subLeft);
}整个删除接口合在一起的代码
bool Erase(const K key)
{Node* parent nullptr;Node* cur _root;while (cur){if (key cur-_key){parnet cur;cur cur-_right}else if (key cur-_key){parent cur;cur cur-_left;}else{// 1、左为空if (cur-_left nullptr){if (cur _root){_root cur-_right;}if (parent-_left cur){parent-_left cur-_right;}else{parent-_right cur-_right;}delete(cur);}// 2、右为空else if (cur-_right nullptr){if (cur _root){_root cur-_left;} if (parent-_left cur){parent-_left cur-_left}else{parent-_right cur-_left;}delete(cur);}// 3、左右都不为空else{Node* parent cur;Node* subLeft cur-_right;while (subLeft-_left){parent subLeft;subLeft subLeft-_left;}swap(cur-_key, subLeft-_key);if (subLeft parent-_left)parent-_left subLeft-_right;elseparent-_right subLeft-_right;delete(subLeft);}}}
}递归版本 递归版本与非递归版本类似 非递归版本中使用while循环来找key位置递归就是不断调用自身来找key位置当找到后依然分三种情况来分析左为空、右为空、左右都不为空。 递归版本中用引用来接受传来的root因此不用考虑链接问题也就不存在判断删除位置是父节点的左还是右直接修改root即可。 1、左为空/左右都为空先记下要删除的节点再修改root最后释放删除的节点。 Node* del root; root root-_right; delete(del); 2、右为空先记下要删除的节点再修改root最后释放删除的节点。Node* del root; root root-_left; delete(del); 3、左右都不为空先找到右子树的最左节点最小值交换 root-_key与subLeft-_key 右子树的最左节点一定是叶子节点因此删除subLeft直接再去调用函数自身即可即再来一次左右都为空左为空的删除。
bool EraseR(const K key)
{return _EraseR(_root, key);
}
bool _EraseR(Node* root, const K key)
{if (root nullptr)return false;if (root-_key key){_EraseR(root-_right, key);}else if (root-_key key){_EraseR(root-_left, key);}else{if (root-_left nullptr){Node* del root;root root-_right;delete(del);// 必须释放不释放会导致内存泄漏return true;}else if (root-_right nullptr){Node* del root;root root-_left;delete(del);return true;}else{Node* subLeft root-_right;while (subLeft-_left){subLeft subLeft-_left;}swap(root-_key, subLeft-_key);return _EraseR(root-_right, key);}}
}2、二叉搜索树的应用
2.1 K模型
K模型K模型即只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到的值。 比如给一个单词word判断该单词是否拼写正确具体方式如下
以词库中所有单词集合中的每个单词作为key构建一棵二叉搜索树在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误。
2.2 KV模型
KV模型每一个关键码key都有与之对应的值Value即Key, Value的键值对。 该种方式在现实生活中非常常见 ● 比如英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英文单词与其对应的中文word, chinese就构成一种键值对 ● 再比如统计单词次数统计成功后给定单词就可快速找到其出现的次数单词与其出现次数就是word, count就构成一种键值对。
3、二叉搜索树的性能分析
插入和删除操作都必须先查找查找效率代表了二叉搜索树中各个操作的性能。 对有n个结点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数即结点越深则比较次数越多。 但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树 最优情况下二叉搜索树为完全二叉树(或者接近完全二叉树)其平均比较次数为log_2 N 最差情况下二叉搜索树退化为单支树(或者类似单支)其平均比较次数为N 最差情况是退化为单支树性能就变得很差了因为后续我们将改进搜索二叉树的插入与删除来实现平衡二叉搜索树即AVL树与红黑树RB树。
4、K模型与KV模型完整代码
4.1 二叉搜索树的模拟实现K模型
namespace key
{template class Kstruct BSTreeNode{BSTreeNode* _left;BSTreeNode* _right;K _key;BSTreeNode(const K key):_left(nullptr), _right(nullptr), _key(key){}};template class Kclass BSTree{typedef BSTreeNodeK Node;public: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;}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 true;}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{// 删除分情况讨论// 1. 左为空左右都为空2. 右为空3.左右都不为空if (cur-_left 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 (cur _root)// 根节点是删除的节点情况_root cur-_left;else{if (cur parent-_left){parent-_left cur-_left;}else{parent-_right cur-_left;}}delete(cur);}else// 左右都不为空{// 替换法找左子树最大 / 右子树最小来替换curNode* parent cur;Node* subLeft cur-_right;while (subLeft-_left){parent subLeft;subLeft subLeft-_left;}swap(cur-_key, subLeft-_key);if (subLeft parent-_left)parent-_left subLeft-_right;else// 处理删除根节点的情况parent-_right subLeft-_right;delete(subLeft);}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);}// C11BSTree() default; // 强制编译器生成默认构造BSTree(const BSTreeK t){_root Copy(t._root);}// 赋值重载现代写法BSTreeK operator(BSTreeK t){swap(_root, t._root);return *this;}~BSTree(){Destroy(_root);}private: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 Destroy(Node* root){if (root nullptr)return;Destroy(root-_left);Destroy(root-_right);delete root;root nullptr;}bool _InsertR(Node* root, const K key){if (root nullptr){root new Node(key);return true;}if (root-_key key){_InsertR(root-_right, key);}else if (root-_key key){_InsertR(root-_left, key);}else{return false;}}bool _FindR(Node* root, const K key){if (root nullptr){return false;}if (root-_key key){_FindR(root-_right, key);}else if (root-_key key){_FindR(root-_left, key);}else{return true;}}bool _EraseR(Node* root, const K key){if (root nullptr)return false;if (root-_key key){_EraseR(root-_right, key);}else if (root-_key key){_EraseR(root-_left, key);}else{if (root-_left nullptr){Node* del root;root root-_right;delete(del);// 必须释放不释放会导致内存泄漏return true;}else if (root-_right nullptr){Node* del root;root root-_left;delete(del);return true;}else{Node* subLeft root-_right;while (subLeft-_left){subLeft subLeft-_left;}swap(root-_key, subLeft-_key);return _EraseR(root-_right, key);}}}void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);}private:Node* _root nullptr;};
};4.2 KV模型的模拟实现
namespace kv
{template class K, class Vstruct BSTreeNode{BSTreeNodeK, V* _left;BSTreeNodeK, V* _right;K _key;V _val;BSTreeNode(const K key, const V val):_left(nullptr), _right(nullptr), _key(key), _val(val){}};template class K, class Vclass BSTree{typedef BSTreeNodeK, V Node;public:bool Insert(const K key, const V val){if (_root nullptr){_root new Node(key, val);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, val);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;}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{// 删除分情况讨论// 1. 左为空左右都为空2. 右为空3.左右都不为空if (cur-_left 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 (cur _root)// 根节点是删除的节点情况_root cur-_left;else{if (cur parent-_left){parent-_left cur-_left;}else{parent-_right cur-_left;}}delete(cur);}else// 左右都不为空{// 替换法找左子树最大 / 右子树最小来替换curNode* parent cur;Node* subLeft cur-_right;while (subLeft-_left){parent subLeft;subLeft subLeft-_left;}swap(cur-_key, subLeft-_key);if (subLeft parent-_left)parent-_left subLeft-_right;else// 处理删除根节点的情况parent-_right subLeft-_right;delete(subLeft);}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-_val endl;_InOrder(root-_right);}private:Node* _root nullptr;};
};
