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

wordpress 酒店主题seo外链优化

news 2025/7/3 21:05:17
wordpress 酒店主题,seo外链优化,阳江招聘网站哪里最好找工作,公司或(学校)新闻网站建设开题报告jsp+mysql1.二叉搜索树概念 二叉搜索树又称二叉排序树、二叉查找树，它或者是一棵空树，或者是具有以下性质的二叉树: 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.dinnco.com/news/18460.html

相关文章：

  • 湛江市seo网站设计报价网络推广平台收费不便宜
  • seo网站做推广产品策划推广方案
  • 做微商怎么通过网站和贴吧引流客源网络推广的方法和技巧
  • 上哪儿找做网站百度推广平台登录网址
  • 沈阳微信网站开发推广app的单子都在哪里接的
  • 关于政府网站建设管理的演讲稿怎么看关键词的搜索量
  • 福州网站制作官网搜索引擎下载入口
  • 宁波网站建设公司排名百度集团公司简介
  • 做门户网站建设多少钱关键词首页排名优化公司推荐
  • 南阳网站建设今天新闻头条新闻
  • 厦门企业网站建设补贴google官方版下载
  • 手工做火枪的网站百度搜索一下百度
  • 沈阳计算机培训机构宁波企业seo服务
  • 网上共青团 智慧团建网站整站优化价格
  • 怎么设网站建网站设计
  • 为什么很多公司做网站建设seo专员招聘
  • 网站用不用备案典型的口碑营销案例
  • 网站建设备案多长时间宁波seo教程app推广
  • 青海环保网站建设公司网站制作流程
  • 培训学校 网站费用网站数据查询
  • 佛山规划建设局网站资阳市网站seo
  • 购物网站开发过程优化网站界面的工具
  • 中山祥云做的网站怎么样百度百科百度推广查询
  • c 网站开发 pdf拼多多标题关键词优化方法
  • 网站页面上的下载功能怎么做推广平台排名
  • 郑州建设网站新的网站怎么推广
  • 国内响应式网站百度游戏官网
  • 开发公司注册资金要求新的seo网站优化排名 网站
  • 网站建设基础实验1百度推广员工工资怎么样
  • 做统计图的网站南昌网站seo