做pc网站排,东莞厚街天气,杭州有名的纯设计公司,网络舆情分析师证书1、二叉搜索树的概念
二叉搜索树又叫做二叉排序树#xff0c;他或者是一棵空树#xff0c;或者具有以下性质#xff1a;
若他的左子树不为空#xff0c;则左子树的所有节点的值都小于根节点的值#xff0c;
若他的右子树不为空#xff0c;则右子树的所有节点的值都大于…1、二叉搜索树的概念
二叉搜索树又叫做二叉排序树他或者是一棵空树或者具有以下性质
若他的左子树不为空则左子树的所有节点的值都小于根节点的值
若他的右子树不为空则右子树的所有节点的值都大于根节点的值
他的左右子树也分别为二叉搜索树
2、二叉搜索树的操作 int a[] {8, 3, 1, 10, 6, 4, 7, 14, 13}; 1.二叉搜索树的查找
从根节点开始找比根大往右边查找比根小往左边查找最多查找高度次走到空还没找到则该值不存在
2.二叉搜索树的插入
若树为空则新增节点赋值给root指针
若树不为空按二叉搜索树查找插入位置插入新节点 3.二叉搜索树的删除
首先查找元素是否在二叉搜索树中如果不存在则返回如果存在则分为以下四种情况 a. 要删除的结点无孩子结点 b. 要删除的结点只有左孩子结点 c. 要删除的结点只有右孩子结点 d. 要删除的结点有左、右孩子结点 其实a情况可以和b c 情况合并起来这样我们只需要考虑三种删除方式 情况b: 删除该节点并使该节点的父亲节点指向删除节点的左节点 情况c:删除该节点并使该节点的父亲节点指向删除节点的右节点 情况d:替换法找到该节点右子树的最小节点或者左子树的最大节点与该节点替换然后删除右子树的最小节点或左子树的最大节点 4.二叉搜索树的实现
#pragma once#includeiostream
#includestring
using namespace std;
namespace key
{templateclass Kstruct BSTreeNode{BSTreeNodeK* _left;BSTreeNodeK* _right;K _key;BSTreeNode(const K key):_left(nullptr),_right(nullptr),_key(key){ }};templateclass Kclass BSTree{typedef BSTreeNodeK Node;public: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-_keykey){cur cur-_left;}else{cout true endl;return true;}}cout false endl;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 (parent-_left cur){parent-_left cur-_right;}else{parent-_rightcur-_right;}}delete cur;}//右为空父亲指向我的左else if (cur-_right nullptr){if (cur _root){_root cur-_left;}else{if (parent-_left cur){parent-_left cur-_left;}else{parent-_right cur-_left;}}delete cur;}else{//左右都不为空替换法//查找右子树的最小节点或左子树的最大节点//我们这里找右子树的最小节点(也就是最左节点)Node* rightMinParent cur;Node* rightMin cur-_right;while (rightMin-_left){rightMinParent rightMin;rightMin rightMin-_left;}swap(cur-_key, rightMin-_key);if (rightMinParent-_left rightMin){rightMinParent-_left rightMin-_right;}else{rightMinParent-_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);}Node* _root nullptr;};void TestBSTree1(){BSTreeint b;b.Insert(1);b.Insert(2);b.Insert(3);b.Insert(4);b.Insert(5);b.Find(6);b.Find(3);b.Find(5);b.InOrder();}void TestBSTree2(){int a[] { 8, 3, 1, 10, 6, 4, 7, 14, 13 };BSTreeint t1;for (auto e : a){t1.Insert(e);}/*t1.InOrder();t1.Erase(8);t1.InOrder();*/for (auto e : a){t1.Erase(e);t1.InOrder();}}
}namespace key_value
{templateclass K,class Vstruct BSTreeNode{BSTreeNodeK,V* _left;BSTreeNodeK,V* _right;K _key;V _value;BSTreeNode(const K key,const V value):_left(nullptr), _right(nullptr), _key(key), _value(value){ }};templateclass K,class Vclass 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 cur;}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-_left cur){parent-_left cur-_right;}else{parent-_right cur-_right;}}delete cur;}//右为空父亲指向我的左else if (cur-_right nullptr){if (cur _root){_root cur-_left;}else{if (parent-_left cur){parent-_left cur-_left;}else{parent-_right cur-_left;}}delete cur;}else{//左右都不为空替换法//查找右子树的最小节点或左子树的最大节点//我们这里找右子树的最小节点(也就是最左节点)Node* rightMinParent cur;Node* rightMin cur-_right;while (rightMin-_left){rightMinParent rightMin;rightMin rightMin-_left;}swap(cur-_key, rightMin-_key);if (rightMinParent-_left rightMin){rightMinParent-_left rightMin-_right;}else{rightMinParent-_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 : root-_value ;_InOrder(root-_right);}Node* _root nullptr;};void TestBSTree3(){BSTreestring, string dict;dict.Insert(string, 字符串);dict.Insert(left, 左边);dict.Insert(insert, 插入);string str;while (cin str){BSTreeNodestring, string* ret dict.Find(str);if (ret){cout ret-_value endl;}else{cout 无此单词请重新输入 endl;}}}void TestBSTree4(){// 统计次数string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜,苹果, 香蕉, 苹果, 香蕉,苹果,草莓, 苹果,草莓 };BSTreestring, int countTree;for (const auto str : arr){auto ret countTree.Find(str);if (ret nullptr){countTree.Insert(str, 1);}else{ret-_value;}}countTree.InOrder();}}5、二叉搜索树的应用
1.K模型K模型只有key作为关键码结构中只需要存储key即可关键码即为需要搜索到的值
比如给一个单词word判断该单词是否拼写正确
2.K-V模型每一个关键码都对应一个Value即Key,value的键值对
比如英汉字典中用英文与中文的对应关系通过英文可以快速找到对应的中文
6、二叉搜索树的性能分析
对于有n个节点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是高度次但对于同一个关键码集合如果插入的次序不同可能得到不同结构的二叉树 最优情况下二叉搜索树为完全二叉树(或者接近完全二叉树)其平均比较次数为O(logN) 最差情况下二叉搜索树退化为单支树(或者类似单支)其平均比较次数为O(N);
