公司做网站需要提供的材料,w3school网页制作,免费企业网站 优帮云,win10最强性能优化设置一、二叉搜索树概念 二叉搜索树 又称二叉排序树#xff0c;它或者是一棵空树#xff0c;或者是具有以下性质的二叉树#xff1a; 若它的左子树不为空#xff0c;则左子树上所有节点的值都小于根节点的值 若它的右子树不为空#xff0c;则右子树上所有节点的值都大于根节点…一、二叉搜索树概念 二叉搜索树 又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树 若它的左子树不为空则左子树上所有节点的值都小于根节点的值 若它的右子树不为空则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树 对二叉搜索树进行中序遍历正好是一个升序序列。左子树 - 根 - 右子树 二、二叉搜索树操作 增删查的时间复杂度是Oh。h 是树的高度最坏情况是 h 是 N。 int a[] {8, 3, 1, 10, 6, 4, 7, 14, 13}; 1、二叉搜索树的查找 a、从 根 开始比较查找比根大则往右边走查找比根小则往左边走查找。 b、 最多查找高度次 走到空还没找到这个值不存在。 2、二叉搜索树的插入 插入的具体过程如下 树为空则直接新增节点赋值给 root 指针。树不空按二叉搜索树性质查找插入位置插入新节点。 3、搜索二叉搜索树的删除 首先查找元素是否在二叉搜索树中如果不存在则返回否则要删除的结点可能分下面四种情况 要删除的结点无孩子结点。要删除的结点只有左孩子结点。要删除的结点只有右孩子结点。要删除的结点有左、右孩子结点。 看起来有待删除节点有 4 种情况实际情况 a 可以与情况 b/c 合并起来因此真正的删除过程如下 情况 b删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点 -- 直接删除。情况 c删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点 -- 直接删除。情况 d在它的右子树中寻找中序下的第一个结点关键码最小用它的值填补到被删除节点中再来处理该结点的删除问题 —— 替换法删除。 删除 3删除的节点有两个孩子替换法 -- 删除以下两种方法任选一种 左子树的最大节点 —— 2左子树的最右节点右子树的最小节点 —— 4右子树的最左节点 替换节点赋值给删除节点后删除替换节点。替换节点要么没有孩子要么只有一个孩子可以直接删除。 三、二叉搜索树的实现
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;
public:bool Insert(const K key){// 如果树为空直接插入if (nullptr _root){_root new Node(key);return true;}// 按照二叉搜索树的性质查找key在树中的插入位置Node* cur _root;// 记录cur的双亲因为新元素最终插入在cur双亲左右孩子的位置Node* parent nullptr;while (cur){parent cur;if (key cur-_key){parent cur;cur cur-_left;}else if (key cur-_key){parent cur;cur cur-_right;}elsereturn false;}// 插入元素cur new Node(key);if (key parent-_key)parent-_left cur;elseparent-_right cur;return true;}// 根据二叉搜索树的性质查找找到值为key的节点在二叉搜索树中的位置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){// 如果树为空删除失败if (nullptr _root)return false;// 查找在data在树中的位置Node* cur _root;Node* parent nullptr;while (cur){if (key cur-_key){parent cur;cur cur-_left;}else if(key cur-_key){parent cur;cur cur-_right;}else{// 开始删除// 1、左为空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;cur nullptr;}// 2、右为空else if (cur-_right nullptr){if (_root cur){_root cur-_left;}else{if (cur parent-_left){parent-_left cur-_left;}else{parent-_right cur-_left;}}delete cur;cur nullptr;}// 3、左右都不为空else{// 找到右子树最小节点进行替换Node* minParent cur;Node* min cur-_right;while (min-_left){minParent min;min min-_left;}swap(cur-_key, min-_key);if (minParent-_left min)minParent-_left min-_right;elseminParent-_right min-_right;delete min;}return true;}}return false;}// key不在二叉搜索树中无法删除if (nullptr cur)return false;// 分以下情况进行删除if (nullptr cur-_right){// 当前节点只有左孩子或者左孩子为空---可直接删除}else if (nullptr cur-_right){// 当前节点只有右孩子---可直接删除}else{// 当前节点左右孩子都存在直接删除不好删除可以在其子树中找一个替代结点比如// 找其左子树中的最大节点即左子树中最右侧的节点或者在其右子树中最小的节点即右子树中最小的节点// 替代节点找到后将替代节点中的值交给待删除节点转换成删除替代节点}return true;}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);}~BSTree(){_Destory(_root);}BSTree() default;BSTree(const BSTreeK t){_root _Copy(t._root);}// t2 t1BSTreeK operator(BSTreeK t){swap(_root, t._root);return *this;}private:Node* _Copy(Node* root){if (root nullptr){return nullptr;}Node* copyRoot new Node(root-_key);copyRoot-_left _Copy(root-_left);copyRoot-_right _Copy(root-_right);return copyRoot;}void _Destory(Node* root){if (root nullptr){return;}_Destory(root-_left);_Destory(root-_right);delete root;root nullptr;}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-_left nullptr){root root-_right;}else if (root-_right nullptr){root root-_left;}else{// 找右树的最左节点替换删除Node* min root-_right;while (min-_left){min min-_left;}swap(root-_key, min-_key);//return Erase(key); // 错误 - 找到的不是我们要的位置return _EraseR(root-_right, key);}delete del;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);elsereturn 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);elsereturn true;}void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);}private:Node* _root nullptr;
}; 四、二叉搜索树的应用 1、 K模型判断关键字在不在 K 模型即只有 key 作为关键码结构中只需要存储 Key 即可关键码即为需要搜索到 的值。 比如给一个单词 word判断该单词是否拼写正确具体方式如下 以词库中所有单词集合中的每个单词作为 key构建一棵二叉搜索树。在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误。 2、 KV模型 每一个关键码 key都有与之对应的值 Value即 Key, Value 的键值对。该种方式在现实生活中非常常见 比如英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英 文单词与其对应的中文 word, chinese 就构成一种键值对 再比如统计单词次数统计成功后给定单词就可快速找到其出现的次数单词与其出 现次数就是 word, count 就构成一种键值对。 // 改造二叉搜索树为KV结构
templateclass K, class V
struct BSTreeNode
{BSTreeNodeK, V* _left;BSTreeNodeK, V* _right;K _key;V _valueBSTreeNode(const K key, const V value): _left(nullptr), _right(nullptr), _key(key), _Value(value){}
};templateclass K, class V
class BSTree
{typedef BSTNodeK, 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){//...return true;}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 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){cout 对应的中文: ret-_value endl;}else{cout 没有此单词 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){ret-_value;}else{countTree.Insert(str, 1);}}countTree.InOrder();
} 五、二叉搜索树的性能分析 插入和删除操作都必须先查找查找效率代表了二叉搜索树中各个操作的性能。 对有 n 个结点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数即结点越深则比较次数越多。 但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树 最优情况下二叉搜索树为完全二叉树或者接近完全二叉树其平均比较次数为 logN。最差情况下二叉搜索树退化为单支树或者类似单支其平均比较次数为N。 如果退化成单支树二叉搜索树的性能就失去了。那能否进行改进不论按照什么次序插入关键码二叉搜索树的性能都能达到最优 那么我们后面将学习的 AVL 树和红黑树 就可以派上用场了。
