当前位置： 首页 > news >正文

嘉兴市建设工程监理协会网站阿里云 wordpress邮件

news 2025/11/4 20:21:54
嘉兴市建设工程监理协会网站,阿里云 wordpress邮件,做刷机网站赚钱吗,网站建设属于技术开发吗1.二叉搜索树概念 二叉搜索树又称二叉排序树、二叉查找树，它或者是一棵空树，或者是具有以下性质的二叉树: 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是key，second是value。

K模型：

namespace myBSTree_K
{template <class T>struct BSTNode{BSTNode(const T& data = T()):_left(nullptr), _right(nullptr), _data(data){}BSTNode<T>* _left;BSTNode<T>* _right;T _data;};template <class T>class BSTree{typedef BSTNode<T> 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 V>struct BSTNode{BSTNode(const pair<K,V>& data = pair<K,V>()):_left(nullptr), _right(nullptr), _data(data){}BSTNode<K,V>* _left;BSTNode<K,V>* _right;pair<K,V> _data;};template <class K, class V>class BSTree{typedef BSTNode<K,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 pair<K, 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 pair<K, 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个节点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是节点在二
叉搜索树的深度的函数，即结点越深，则比较次数越多，但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：log2​N
最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：N/2

二叉搜索树退化，使二叉搜索树性能丢失，需要使二叉搜索树平衡，可以使用AVL树和红黑树。

http://www.yayakq.cn/news/781056/

相关文章：

  • 鞍山网站制作的网站seo sem培训
  • 90设计网站可以商用吗网页资源下载
  • 传奇做网站空间电商平台有哪些模式
  • 软件定制网站优化 seo一站式山东省建设部网站
  • 网站建设哪个好房屋设计师破解版
  • 建设集团网站公司信誉好的唐山网站建设
  • 站点搭建深圳找个人做网站
  • 用c 做网站可以吗厦门市建设局官方网站证书查询
  • 怎么建网站新手入门推广标题怎么写
  • 服装设计网站怎么做网站的设计与应用论文
  • 产品推广宣传语济南网站优化收费
  • 岳阳网站建设的公司网站地图
  • 做淘宝网站要安全保障么wordpress程序图片打开慢
  • 汽车类网站搭建网站上传页面
  • 广东省网站免备案表网站对于企业的好处
  • 一级a做爰片免费网站下载wordpress博客亚马逊广告
  • 手机餐饮网站开发乐清柳市阿里巴巴做网站的
  • 台州网站制作定制网站识别手机电脑自动跳转
  • 佛山网站seo优化排名公司被逆冬seo课程欺骗了
  • 小区媒体网站建设台州网站制作服务
  • 网站注册备案之后怎么做网站智能经济高峰论坛
  • 网站域名怎么看做设计有必要买素材网站会员
  • 网站运营怎么学做网站3年3万
  • 网站建设发布深圳债务优化
  • 大理州建设局官方网站三秦seo
  • 萍乡网站设计公司软件工程开发师
  • 做接口的网站angular网站模板下载
  • 如何推广运营网站网站开发人员招聘it管理
  • 设计logo网站 生成器无极网站维护
  • 代刷网站建设网站建设 排名