WordPress加速优化方案,云南官网优化,阿里云虚拟主机做网站,女生做网站推广文章目录 1. 二叉搜索树的实现2. 二叉搜索树的应用3. 改造二叉搜索树为 KV 结构4. 二叉搜索树的性能分析 1. 二叉搜索树的实现
namespace key
{templateclass Kstruct BSTreeNode{typedef BSTreeNodeK Node;Node* _left;Node* _right;K _key;BSTreeNode(const… 文章目录 1. 二叉搜索树的实现2. 二叉搜索树的应用3. 改造二叉搜索树为 KV 结构4. 二叉搜索树的性能分析 1. 二叉搜索树的实现
namespace key
{templateclass Kstruct BSTreeNode{typedef BSTreeNodeK Node;Node* _left;Node* _right;K _key;BSTreeNode(const K key): _left(nullptr), _right(nullptr), _key(key){}};templateclass Kclass BSTree{typedef BSTreeNodeK Node;public:// 强制生成默认构造BSTree() default;BSTree(const BSTreeK t){_root Copy(t._root);}BSTreeK operator(BSTreeK t){swap(_root, t._root);return *this;}~BSTree(){Destroy(_root);}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 false;}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 (cur _root){_root cur-_right;}else{if (cur parent-_right){parent-_right cur-_right;}else{parent-_left cur-_right;}}delete cur;return true;}else if (cur-_right nullptr){if (cur _root){_root cur-_left;}else{if (cur parent-_right){parent-_right cur-_left;}else{parent-_left cur-_left;}}delete cur;return true;}else{// 替换法Node* rightMinParent cur;Node* rightMin cur-_right;while (rightMin-_left){rightMinParent rightMin;rightMin rightMin-_left;}cur-_key rightMin-_key;if (rightMin rightMinParent-_left){rightMinParent-_left rightMin-_right;}else{rightMinParent-_right rightMin-_right;}delete rightMin;return true;}}}return false;}void InOrder(){_InOrder(_root);cout endl;}bool FindR(const K key){return _FindR(_root, key);}bool InsertR(const K key){return _InsertR(_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 _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 _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 _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* rightMin root-_right;while (rightMin-_left){rightMin rightMin-_left;}swap(root-_key, rightMin-_key);return _EraseR(root-_right, key);}delete del;return true;}}private:Node* _root nullptr;};
}2. 二叉搜索树的应用 K 模型K 模型即只有 key 作为关键码结构中只需要存储 key 即可关键码即为需要搜索到的值。 比如给一个单词 word判断该单词是否拼写正确具体方式如下 以词库中所有单词集合中的每个单词作为 key构建一颗二叉搜索树在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误。 KV 模型每一个关键码 key都有与之对应的值 value即 Key, Value 的键值对。这种方式在现实生活中非常常见 比如英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英文单词与其对应的中文 word, chinese 就构成一种键值对再比如统计单词个数统计成功后给定单词就可以快速找到其出现的次数单词与其出现次数 word, count 就构成一种键值对。
3. 改造二叉搜索树为 KV 结构
namespace key_value
{templateclass K, class Vstruct BSTreeNode{typedef BSTreeNodeK, V Node;Node* _left;Node* _right;K _key;V _value;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: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;}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 (cur _root){_root cur-_right;}else{if (cur parent-_right){parent-_right cur-_right;}else{parent-_left cur-_right;}}delete cur;return true;}else if (cur-_right nullptr){if (cur _root){_root cur-_left;}else{if (cur parent-_right){parent-_right cur-_left;}else{parent-_left cur-_left;}}delete cur;return true;}else{// 替换法Node* rightMinParent cur;Node* rightMin cur-_right;while (rightMin-_left){rightMinParent rightMin;rightMin rightMin-_left;}cur-_key rightMin-_key;if (rightMin rightMinParent-_left){rightMinParent-_left rightMin-_right;}else{rightMinParent-_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 ;cout root-_value endl;_InOrder(root-_right);}private:Node* _root nullptr;};
}测试代码
namespace key_value
{void TestBSTree1(){// 输入单词查找单词对应的中文翻译BSTreestring, string dict;dict.Insert(string, 字符串);dict.Insert(tree, 树);dict.Insert(left, 左边、剩余);dict.Insert(right, 右边);dict.Insert(sort, 排序);// 插入词库中所有单词string str;while (cin str){BSTreeNodestring, string* ret dict.Find(str);if (ret nullptr){cout 单词拼写错误词库中没有这个单词: str endl;}else{cout str 中文翻译: ret-_value endl;}}}void TestBSTree2(){// 统计水果出现的次数string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜,苹果, 香蕉, 苹果, 香蕉 };BSTreestring, int countTree;for (const auto str : arr){// 先查找水果在不在搜索树中// 1、不在说明水果第一次出现则插入水果, 1// 2、在则查找到的节点中水果对应的次数//BSTreeNodestring, int* ret countTree.Find(str);auto ret countTree.Find(str);if (ret NULL){countTree.Insert(str, 1);}else{ret-_value;}}countTree.InOrder();}
}4. 二叉搜索树的性能分析
插入和删除操作都必须先查找查找效率代表了二叉搜索树中各个操作的性能。
对有 n 和节点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是节点在二叉搜索树的深度的函数即节点越深比较次数越多。
但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树 最优情况下二叉搜索树为完全二叉树或者接近完全二叉树其平均比较次数为 l o g 2 N log_2 N log2N
最差情况下二叉搜索树退化为单支树或者类似单支其平均比较次数为 N 2 \frac{N}{2} 2N。
问题如果退化成单支树二叉搜索树的性能就失去了。能否进行改进不论按照什么次序插入关键码都能使二叉搜索树的性能达到最优
答可以使用 AVL树 和 红黑树 的特性使单支树在达到一定深度时进行“旋转”变回接近完全二叉树的形状这个我们后面再谈。 END
