网站推广公司哪家好,简单html网站模板,酥糖的网站建设的目的是什么,网络营销有哪些主要内容目录 前言
一、二叉搜索树概念
二、二叉搜索树的实现与操作
1.查找
2.插入
3.删除
4.中序遍历
5.完整代码
三、二叉搜索树的应用#xff08;K模型、KV模型#xff09;
1.K模型
2.KV模型
3.完整代码
四、二叉搜索树的性能分析 前言
为何学#xff1f;
1.二叉…目录 前言
一、二叉搜索树概念
二、二叉搜索树的实现与操作
1.查找
2.插入
3.删除
4.中序遍历
5.完整代码
三、二叉搜索树的应用K模型、KV模型
1.K模型
2.KV模型
3.完整代码
四、二叉搜索树的性能分析 前言
为何学
1.二叉搜索树是一种树形结构是一种查找效率非常高的结构值得我们去学习
2.map和set的底层也是二叉搜素树学习二叉搜索树可以让我们更好的了解set和map的特性
一、二叉搜索树概念
二叉搜索树BST,Binary Search Tree又称二叉排序树、二叉查找树
它可以是一颗空树
如果不是它或者说它的任何一颗子树必须满足下列条件
1.如果它的左子树不为空则左子树上的所有节点值都小于根节点的值
2.如果它的右子树不为空则右子树上的所有节点值都大于根节点的值
3.左、右子树都是二叉搜索树 二、二叉搜索树的实现与操作
节点结构
templateclass K
struct BSTreeNode
{typedef BSTreeNodeK Node;Node* _left;Node* _right;K _key;BSTreeNode(const K key):_left(nullptr), _right(nullptr), _key(key){}
};
树类
templateclass K, class V
class BSTree
{typedef BSTreeNodeK Node;
public:bool Insert(const K key){}bool Find(const K key){}bool Erase(const K key){}void _InOrder(Node* root){}void InOrder(){_InOrder(root);}
private:Node* root nullptr;
};1.查找
从根开始查找比较比当前根值大往右边查找比当前根值大往右边查找且最多查找高度次走到空还未找到则所查找值不存在
代码实现
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;
}
2.插入
1.如果为空树则将创建新节点并将新节点赋值给根节点root指针
2.如果树不为空则按二叉搜索树的性质先查找插入位置再插入
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;}else{return false;}}cur new Node(key);if (parent-_key key){parent-_right cur;}else{parent-_left cur;}return true;
}
3.删除
在二叉搜索树中删除是一个稍显麻烦的事其中包含了许多细节
我们可以知道待删除的节点有四种情景
1.要删除的结点无孩子结点
2.要删除的结点只有左孩子结点
3.要删除的结点只有右孩子结点
4.要删除的结点有左、右孩子结点 在后面的处理中1情景和23情景可以融合因此去掉1情景我们有3种情景
情景2使待删除节点的父节点指向待删除节点的左孩子删除待删除节点情景3使待删除节点的父节点指向待删除节点的右孩子删除待删除节点 情景4
这里我们事用替换法删除--即在待删除节点的子树中找一个合适的替换节点用它的值替换填补调待删除节点可以找左子树的最大值或者右子树的最小值 在处理替换节点的子树问题
下面的演示代码找的树右子树的最小值替换
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 (cur parent-_right){parent-_right cur-_right;}else{parent-_left cur-_right;}}delete cur;return true;}else if (cur-_right nullptr){if (cur _root){_root cur-_left;}else{if (cur parent-_right){parent-_right cur-_left;}else{parent-_left cur-_left;}}delete cur;return true;}else{// 替换法Node* rightMinParent cur;Node* rightMin cur-_right;while (rightMin-_left){rightMinParent rightMin;rightMin rightMin-_left;}cur-_key rightMin-_key;if (rightMin rightMinParent-_left)rightMinParent-_left rightMin-_right;elserightMinParent-_right rightMin-_right;delete rightMin;return true;}}}return false;
}4.中序遍历
既然二叉搜索树能叫做二叉排序树自然是有原因的在二叉搜索树中对二叉搜索树来一次中序遍历即可得到一组有序元素 在C的类中不能直接调用递归函数需要嵌套一层递归
void InOrder()
{_InOrder(_root);cout endl;
}
void _InOrder(Node* root)
{if (root nullptr)return;_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);
}
5.完整代码
templateclass K
struct BSTreeNode
{typedef BSTreeNodeK Node;Node* _left;Node* _right;K _key;BSTreeNode(const K key):_left(nullptr), _right(nullptr), _key(key){}
};templateclass K
class BSTree
{typedef BSTreeNodeK Node;
public:BSTreeK operator(BSTreeK t){swap(_root, t._root);return *this;}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;}else{return false;}}cur new Node(key);if (parent-_key key){parent-_right cur;}else{parent-_left cur;}return true;}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){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 (cur parent-_right){parent-_right cur-_right;}else{parent-_left cur-_right;}}delete cur;return true;}else if (cur-_right nullptr){if (cur _root){_root cur-_left;}else{if (cur parent-_right){parent-_right cur-_left;}else{parent-_left cur-_left;}}delete cur;return true;}else{// 替换法Node* rightMinParent cur;Node* rightMin cur-_right;while (rightMin-_left){rightMinParent rightMin;rightMin rightMin-_left;}cur-_key rightMin-_key;if (rightMin rightMinParent-_left)rightMinParent-_left rightMin-_right;elserightMinParent-_right rightMin-_right;delete rightMin;return true;}}}return false;}void InOrder(){_InOrder(_root);cout endl;}void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);}private:Node* _root nullptr;
};三、二叉搜索树的应用K模型、KV模型
1.K模型
K模型中只有一个key值作为关键码只存储key值
如我们要在一个词库中搜索一个单词 “key”我们只需要以这个词库的每一个单词作为key值构建二叉搜索树再在这个树中查找key值为“key”的节点
2.KV模型
KV模型中的每一个key值都有一个对应的value值也叫映射即Key,Value键值对
如我们平时学习上经常用到的英汉词典每个英文都对应着中文英文单词与其对应的Word,Chinese就构成了一种键值对
下面就是上述K模型代码改造的KV模型代码
3.完整代码
templateclass K, class V
struct BSTreeNode
{typedef BSTreeNodeK, V Node;Node* _left;Node* _right;K _key;V _value;BSTreeNode(const K key, const V value):_left(nullptr), _right(nullptr), _key(key), _value(value){}
};templateclass K, class V
class BSTree
{typedef BSTreeNodeK, 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){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 (cur parent-_right){parent-_right cur-_right;}else{parent-_left cur-_right;}}delete cur;return true;}else if (cur-_right nullptr){if (cur _root){_root cur-_left;}else{if (cur parent-_right){parent-_right cur-_left;}else{parent-_left cur-_left;}}delete cur;return true;}else{// 替换法Node* rightMinParent cur;Node* rightMin cur-_right;while (rightMin-_left){rightMinParent rightMin;rightMin rightMin-_left;}cur-_key rightMin-_key;if (rightMin rightMinParent-_left)rightMinParent-_left rightMin-_right;elserightMinParent-_right rightMin-_right;delete rightMin;return true;}}}return false;}void InOrder(){_InOrder(_root);cout endl;}private:void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);}private:Node* _root nullptr;
};
四、二叉搜索树的性能分析
根据上面的介绍我们可以知道无论是删除还是插入都需要先查找到需要处理的位置因此查找效率代表了二叉搜索树的各个操作额性能
对于一个有n个节点的二叉搜索树查找的平均长度差不多就是二叉搜索树的深度节点越深次数越多。
插入次序不同得到的二叉搜索树的结构可能不同比如下图 对于较好的情况参考上面的左图二叉树为完全二叉树或者说接近完全二叉树查找的平均次数为
对于较差的情况参考上面的右图二叉搜索树退化成单只树或者说接近单只树查找的平均次数为n
若是退化为单只树二叉搜索树就失去了它的性能优势
要想二叉搜索树的性能不管怎样插入都能达到最优请继续学习后面大佬们发明的AVL树和红黑树在那里你可以找到所要的答案
