无法进行网站备案,免费企业网站程序,Wordpress提高pagespeed,网站服务器重做系统怎么做1.二叉搜索树概念
二叉搜索树又称二叉排序树、二叉查找树#xff0c;它或者是一棵空树#xff0c;或者是具有以下性质的二叉树: 1. 非空左子树的所有键值小于其根节点的键值 2. 非空右子树的所有键值大于其根节点的键值 3. 左右子树也分别为二叉搜索树
二叉搜索树一般不支持…1.二叉搜索树概念
二叉搜索树又称二叉排序树、二叉查找树它或者是一棵空树或者是具有以下性质的二叉树: 1. 非空左子树的所有键值小于其根节点的键值 2. 非空右子树的所有键值大于其根节点的键值 3. 左右子树也分别为二叉搜索树
二叉搜索树一般不支持key值冗余不允许有重复的key值 二叉搜索树的性质使搜索时非常方便高效最多搜索高度次O(log N)二叉树退化为O(N)需要二叉搜索树平衡使用AVL树或红黑树 二叉搜索树的中序遍历能对key进行排序
二叉搜索树的应用K模型K模型只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到的值 例如查找某个key值存不存在KV模型每一个关键码key都有与之对应的值Value即Key, Value的键值对 key值不能冗余但value值可以相同 例如key值为单词value为对应单词的英文 2.二叉搜索树操作K模型为例 2.1 二叉搜索树的查找
1. 从根节点开始查找查找的key比cur(当前节点)的key大则cur向右查找查找的key比cur的key小则cur向左查找直到找到key值相同或查找的key值不存在。 2. 最多查找高度次cur走到空就说明查找的key不存在。
Node* find(const T data)
{Node* cur _root;while (cur){//找到返回if (data cur-_data)return cur;//大于cur向右找else if (data cur-_data)cur cur-_right;//小于cur向左找elsecur cur-_left;}//没找到return nullptr;return nullptr;
} 2.2 二叉搜索树的插入
1. 树为空树时则直接新增节点并作为该对象的根节点(_root)。 2. 树不为空树时按二叉树的性质查找位置并插入
bool insert(const T data)
{//树为空if (_root nullptr){_root new Node(data);return true;}//树不为空Node* cur _root;Node* parent nullptr;while (cur){if (data cur-_data){parent cur;cur cur-_right;}else if (data cur-_data){parent cur;cur cur-_left;}else//树中已经存在return false;}//插入cur new Node(data);if (data parent-_data)parent-_right cur;elseparent-_left cur;return true;
} 2.3 二叉搜索树的删除
查找元素是否在二叉搜索树中如果不存在则返回否则要删除的节点分四种情况 1. 要删除的节点无孩子节点 -- 直接删除该节点 2. 要删除的节点只有左孩子节点 -- 让左孩子节点替代该节点位置并删除该节点 3. 要删除的节点只有右孩子节点 -- 让右孩子节点替代该节点位置并删除该节点 4. 要删除的节点有左右孩子节点 -- 由二叉树性质查找删除节点的右子树key值最小节点让最小节点的key覆盖掉删除节点的key最小节点一定是只有一个右孩子节点或没有孩子节点的情况按1或2删除最小节点。最小节点不可能存在左孩子不然就不是最小节点了更不可能有两个孩子
bool erase(const T data)
{//空树删除失败if (_root nullptr)return false;Node* cur _root;Node* parent nullptr;while (cur){if (data cur-_data){parent cur;cur cur-_right;}else if (data cur-_data){parent cur;cur cur-_left;}else//此时cur就是需要删除都节点break;}//不存在if (cur nullptr)return false;//存在if (cur-_left nullptr){//cur是根节点if (parent nullptr)_root cur-_right;else{if (cur parent-_left)parent-_left cur-_right;elseparent-_right cur-_right;}delete cur;return true;}else if (cur-_right nullptr){//cur是根节点if (parent nullptr)_root cur-_left;else{if (cur parent-_left)parent-_left cur-_left;else if (cur parent-_right)parent-_right cur-_left;}delete cur;return true;}//删除节点有两个孩子节点else{Node* minNode cur-_right;Node* minNodeParent cur;while (minNode-_left ! nullptr){//最左就是最小节点minNodeParent minNode;minNode minNode-_left;}//修改_datacur-_data minNode-_data;//删除minNodeif (minNodeParent-_left minNode)minNodeParent-_left minNode-_right;else//注意这个情况minNodeParent-_right minNode-_right;delete minNode;return true;}
}
2.4 二叉搜索树代码K模型和KV模型
KV模型与K模型类似只是KV模型的data类型是pair类型first是keysecond是value。
K模型
namespace myBSTree_K
{template class Tstruct BSTNode{BSTNode(const T data T()):_left(nullptr), _right(nullptr), _data(data){}BSTNodeT* _left;BSTNodeT* _right;T _data;};template class Tclass BSTree{typedef BSTNodeT Node;public:BSTree():_root(nullptr){}BSTree(const BSTree tree){_root _Copy(tree._root);}//析构函数无法传参只能调用子函数进行递归销毁~BSTree(){//后序遍历销毁_destory(_root);_root nullptr;}Node* find(const T data){Node* cur _root;while (cur){//找到返回if (data cur-_data)return cur;//大于cur向右找else if (data cur-_data)cur cur-_right;//小于cur向左找elsecur cur-_left;}//没找到return nullptr;return nullptr;}bool insert(const T data){//树为空if (_root nullptr){_root new Node(data);return true;}//树不为空Node* cur _root;Node* parent nullptr;while (cur){if (data cur-_data){parent cur;cur cur-_right;}else if (data cur-_data){parent cur;cur cur-_left;}else//树中已经存在return false;}//插入cur new Node(data);if (data parent-_data)parent-_right cur;elseparent-_left cur;return true;}bool erase(const T data){//空树删除失败if (_root nullptr)return false;Node* cur _root;Node* parent nullptr;while (cur){if (data cur-_data){parent cur;cur cur-_right;}else if (data cur-_data){parent cur;cur cur-_left;}else//此时cur就是需要删除都节点break;}//不存在if (cur nullptr)return false;//存在if (cur-_left nullptr){//cur是根节点if (parent nullptr)_root cur-_right;else{if (cur parent-_left)parent-_left cur-_right;elseparent-_right cur-_right;}delete cur;return true;}else if (cur-_right nullptr){//cur是根节点if (parent nullptr)_root cur-_left;else{if (cur parent-_left)parent-_left cur-_left;else if (cur parent-_right)parent-_right cur-_left;}delete cur;return true;}//删除节点有两个孩子节点else{Node* minNode cur-_right;Node* minNodeParent cur;while (minNode-_left ! nullptr){//最左就是最小节点minNodeParent minNode;minNode minNode-_left;}//修改_datacur-_data minNode-_data;//删除minNodeif (minNodeParent-_left minNode)minNodeParent-_left minNode-_right;else//注意这个情况minNodeParent-_right minNode-_right;delete minNode;return true;}}void InOrder(){_InOrder(_root);}private:void _destory(Node* root){if (root nullptr){return;}_destory(root-_left);_destory(root-_right);delete root;root nullptr;}Node* _Copy(const Node* root){if (root nullptr)return nullptr;Node* newRoot new Node(root-_data);newRoot-_left _Copy(root-_left);newRoot-_right _Copy(root-_right);return newRoot;}//中序遍历void _InOrder(const Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_data ;_InOrder(root-_right);}//成员变量Node* _root;};
}
KV模型
namespace myBSTree_KV
{template class K, class Vstruct BSTNode{BSTNode(const pairK,V data pairK,V()):_left(nullptr), _right(nullptr), _data(data){}BSTNodeK,V* _left;BSTNodeK,V* _right;pairK,V _data;};template class K, class Vclass BSTree{typedef BSTNodeK,V Node;public:BSTree():_root(nullptr){}BSTree(const BSTree tree){_root _Copy(tree._root);}//析构函数无法传参只能调用子函数进行递归销毁~BSTree(){//后序遍历销毁_destory(_root);_root nullptr;}Node* find(const K key){Node* cur _root;while (cur){//找到返回if (key cur-_data.first)return cur;//大于cur向右找else if (key cur-_data.first)cur cur-_right;//小于cur向左找elsecur cur-_left;}//没找到return nullptr;return nullptr;}bool insert(const pairK, V data){//树为空if (_root nullptr){_root new Node(data);return true;}//树不为空Node* cur _root;Node* parent nullptr;while (cur){if (data.first cur-_data.first){parent cur;cur cur-_right;}else if (data.first cur-_data.first){parent cur;cur cur-_left;}else//树中已经存在return false;}//插入cur new Node(data);if (data.first parent-_data.first)parent-_right cur;elseparent-_left cur;return true;}bool erase(const K key){//空树删除失败if (_root nullptr)return false;Node* cur _root;Node* parent nullptr;while (cur){if (key cur-_data.first){parent cur;cur cur-_right;}else if (key cur-_data.first){parent cur;cur cur-_left;}else//此时cur就是需要删除都节点break;}//不存在if (cur nullptr)return false;//存在if (cur-_left nullptr){//cur是根节点if (parent nullptr)_root cur-_right;else{if (cur parent-_left)parent-_left cur-_right;elseparent-_right cur-_right;}delete cur;return true;}else if (cur-_right nullptr){//cur是根节点if (parent nullptr)_root cur-_left;else{if (cur parent-_left)parent-_left cur-_left;else if (cur parent-_right)parent-_right cur-_left;}delete cur;return true;}//删除节点有两个孩子节点else{Node* minNode cur-_right;Node* minNodeParent cur;while (minNode-_left ! nullptr){//最左就是最小节点minNodeParent minNode;minNode minNode-_left;}//修改_datacur-_data minNode-_data;//删除minNodeif (minNodeParent-_left minNode)minNodeParent-_left minNode-_right;else//注意这个情况minNodeParent-_right minNode-_right;delete minNode;return true;}}//改--如果key相同改value如果key不存在不改bool update(const pairK, V data){Node* cur find(data.first);if (cur nullptr)return false;else{cur-_data.second data.second;return true;}}void InOrder(){_InOrder(_root);}private:void _destory(Node* root){if (root nullptr){return;}_destory(root-_left);_destory(root-_right);delete root;root nullptr;}Node* _Copy(const Node* root){if (root nullptr)return nullptr;Node* newRoot new Node(root-_data);newRoot-_left _Copy(root-_left);newRoot-_right _Copy(root-_right);return newRoot;}//中序遍历void _InOrder(const Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_data.first : root-_data.second endl;_InOrder(root-_right);}//成员变量Node* _root;};
}
3. 二叉搜索树的性能分析
插入和删除操作都必须先查找查找效率代表二叉搜索树的各个操作的性能 对有n个节点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是节点在二 叉搜索树的深度的函数即结点越深则比较次数越多但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树
最优情况下二叉搜索树为完全二叉树(或者接近完全二叉树)其平均比较次数为log2N 最差情况下二叉搜索树退化为单支树(或者类似单支)其平均比较次数为N/2
二叉搜索树退化使二叉搜索树性能丢失需要使二叉搜索树平衡可以使用AVL树和红黑树。
