优秀网站建设空间,麻将棋牌网站开发,郑州各区房价一览表,网站怎么重装wordpress文章目录 1. 二叉搜索树1.1 二叉搜索树概念1.2 二叉搜索树的查找1.3 二叉搜索树的插入1.4 二叉搜索树的删除 2 二叉搜索树的实现3 二叉搜索树的应用3.1二叉搜索树的性能分析 1. 二叉搜索树
1.1 二叉搜索树概念
二叉搜索树又称二叉排序树#xff0c;它或者是一棵空树#xf… 文章目录 1. 二叉搜索树1.1 二叉搜索树概念1.2 二叉搜索树的查找1.3 二叉搜索树的插入1.4 二叉搜索树的删除 2 二叉搜索树的实现3 二叉搜索树的应用3.1二叉搜索树的性能分析 1. 二叉搜索树
1.1 二叉搜索树概念
二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树:
若它的左子树不为空则左子树上所有节点的值都小于根节点的值。若它的右子树不为空则右子树上所有节点的值都大于根节点的值。它的左右子树也分别为二叉搜索树。 1.2 二叉搜索树的查找
a、从根开始比较查找比根大则往右边走查找比根小则往左边走查找。 b、最多查找高度次(最高位O(N))走到到空还没找到这个值不存在。
1.3 二叉搜索树的插入
插入的具体过程如下 a. 树为空则直接新增节点赋值给root指针 b. 树不空按二叉搜索树性质查找插入位置插入新节点
1.4 二叉搜索树的删除
首先查找元素是否在二叉搜索树中如果不存在则返回, 否则要删除的结点可能分下面四种情 况
a. 要删除的结点无孩子结点 b. 要删除的结点只有左孩子结点 c. 要删除的结点只有右孩子结点 d. 要删除的结点有左、右孩子结点 看起来有待删除节点有4中情况实际情况a可以与情况b或者c合并起来因此真正的删除过程 如下 情况b删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点–直接删除 情况c删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点–直接删除 情况d在它的右子树中寻找中序下的第一个结点(关键码最小)用它的值填补到被删除节点 中再来处理该结点的删除问题–替换法删除。
2 二叉搜索树的实现
templateclass K
struct BSTreeNode
{BSTreeNode* _left;BSTreeNode* _right;K _key;BSTreeNode(const K key):_left(nullptr), _right(nullptr), _key(key){}
};
templateclass K
struct BSTree
{typedef BSTreeNodeK Node;
public:BSTree():_root(nullptr){}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;}elsereturn false;}cur new Node(key);if (parent-_key key){parent-_right cur;}elseparent-_left cur;return true;}bool Find(const K key){Node* cur _root;while (cur){if (cur-_key key)cur cur-_left;else if (cur-_key key)cur cur-_right;elsereturn true;}return false;}bool Erase(const K key){Node* parent nullptr;Node* cur _root;while (cur){if (cur-_key key){parent cur;cur cur-_left;}else if (cur-_key key){parent cur;cur cur-_right;}else//找到了{if (cur-_left nullptr)//左为空{if (cur _root){_root _root-_right;}else{if (parent-_right cur){parent-_right cur-_right;}else{parent-_left cur-_right;}}}else if (cur-_right nullptr)//右为空{if (cur _root){_root _root-_left;}else{if (parent-_right cur){parent-_right cur-_left;}else{parent-_left cur-_left;}}}else//左右都不为空{Node* parent cur;Node* LeftMax cur-_left;while (LeftMax-_right){parent LeftMax;LeftMax LeftMax-_right;}swap(cur-_key, LeftMax-_key);if (parent-_left LeftMax){parent-_left LeftMax-_left;}else{parent-_right LeftMax-_left;}cur LeftMax;}delete cur;return true;}}return false;}void InOrder(){_InOrder(_root);cout endl;}void _InOrder(Node* root){if (root NULL){return;}_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);}
private:Node* _root;
};void TestBSTree1()
{int a[] { 8, 3, 1, 10, 6, 4, 7, 14, 13 };BSTreeint t;for (auto e : a){t.insert(e);}t.InOrder();t.Erase(4);t.InOrder();t.Erase(6);t.InOrder();t.Erase(7);t.InOrder();t.Erase(3);t.InOrder();for (auto e : a){t.Erase(e);}t.InOrder();
}3 二叉搜索树的应用
K模型K模型即只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到 的值。 比如给一个单词word判断该单词是否拼写正确具体方式如下 以词库中所有单词集合中的每个单词作为key构建一棵二叉搜索树 在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误。KV模型每一个关键码key都有与之对应的值Value即Key, Value的键值对。该种方 式在现实生活中非常常见 比如英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英 文单词与其对应的中文word, chinese就构成一种键值对 再比如统计单词次数统计成功后给定单词就可快速找到其出现的次数单词与其出 现次数就是word, count就构成一种键值对。
以下是完整的代码包括改造二叉搜索树为KV结构、测试二叉搜索树的函数和主函数cpp
#include iostream
#include string using namespace std; templateclass K, class V
struct BSTNode
{ BSTNode(const K key K(), const V value V()) : _pLeft(nullptr) , _pRight(nullptr), _key(key), _value(value) {} BSTNodeK, V* _pLeft; BSTNodeK, V* _pRight; K _key; V _value;
}; templateclass K, class V
class BSTree
{
public: typedef BSTNodeK, V Node; typedef Node* PNode;
public: BSTree(): _pRoot(nullptr){} PNode 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 Insert(const K key, const V value){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 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 (parent-_right cur){parent-_right cur-_right;}else{parent-_left cur-_right;}}}// 右为空else if (cur-_right nullptr){if (cur _root){_root cur-_left;}else{if (parent-_right cur){parent-_right cur-_left;}else{parent-_left cur-_left;}}} // 左右都不为空 else{// 找替代节点Node* parent cur;Node* leftMax cur-_left;while (leftMax-_right){parent leftMax;leftMax leftMax-_right;}swap(cur-_key, leftMax-_key);if (parent-_left leftMax){parent-_left leftMax-_left;}else{parent-_right leftMax-_left;}cur leftMax;}delete cur;return true;}}return false;}
private: PNode _pRoot;
};
3.1二叉搜索树的性能分析
插入和删除操作都必须先查找查找效率代表了二叉搜索树中各个操作的性能。 对有n个结点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是结点在二 叉搜索树的深度的函数即结点越深则比较次数越多。 但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树 最优情况下二叉搜索树为完全二叉树(或者接近完全二叉树)其平均比较次数为 l o g 2 N log_2 N log2N 最差情况下二叉搜索树退化为单支树(或者类似单支)其平均比较次数为 N 2 \frac{N}{2} 2N 问题如果退化成单支树二叉搜索树的性能就失去了。那能否进行改进不论按照什么次序插 入关键码二叉搜索树的性能都能达到最优AVL树和红黑树就可以上场了。
