网站icp备案管理系统,wordpress用户登录注册,杭州网站开发企业,企业网站托管公司二叉搜索树BST
概念
二叉搜索树又称二叉排序树#xff0c;它可以是一棵空树#xff0c;或者是具有以下性质的二叉树#xff1a;若它的左子树不为空#xff0c;则左子树上所有节点的值都小于根节点的值#xff1b;若它的右子树不为空#xff0c;则右子树上所有节点的值都…二叉搜索树BST
概念
二叉搜索树又称二叉排序树它可以是一棵空树或者是具有以下性质的二叉树若它的左子树不为空则左子树上所有节点的值都小于根节点的值若它的右子树不为空则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树。
即当我们按中序来遍历输出这棵树的节点时是有序的按从小到大的顺序。
实现的细节
搜索key的过程Find/FindR
a.从根开始查找val比根节点值大则往右边走查找比根节点值小则往左边走查找; b.最多查找高度次走到到空还没找到说明这个值不存在。
//普通版本--用循环解决
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;
}//用递归来解决
public:
bool FindR(const K key)
{return _FindR(_root, key);
}
private:
bool _FindR(Node* root, const K key)
{if (root nullptr)return false;if (key root-_key)return _FindR(root-_right, key);else if (key root-_key)return _FindR(root-_left, key);elsereturn true;
}插入key的过程Insert/InsertR
需要考虑以下场景
a.树为空则直接新增节点new赋值给root指针; b.树不为空按二叉搜索树性质查找插入位置即与根节点比较比根节点的值小往左查找比根节点的值大往右查找找到该位置后插入新节点。这个过程需要用到2个指针一个为判断当前值与key孰大孰小的cur指针一个是保存cur的父节点的parent指针最终要把key值节点插入在parent的左/右节点。【注意此处的二叉搜索树无相同值】
bool Insert(const K key)
{//如果根节点为空直接插入这个值if (_root nullptr){_root new Node(key);return true;}Node* cur _root;Node* parent nullptr;while (cur){if (cur-_key key){//如果二叉搜索树中已经有一样的值了插入失败return false;}else if (key cur-_key){parent cur;//与根节点比较比根节点的值小往左走比根节点的值大往右走cur cur-_right;}else{parent cur;cur cur-_left;}}cur new Node(key);//与根节点比较比根节点的值大就链接在右边if (key parent-_key){parent-_right cur;}else{parent-_left cur;}return true;
}public:bool InsertR(const K key){return _InsertR(_root, key);}
private:
bool _InsertR(Node* root, const K key){//方式1 bool _InsertR(Node* root, const K key)//if (key root-_key)//{// if (root-_right nullptr)// {// root-_right new Node(key);// return true;// }// else// return _InsertR(root-_right, key);//}//else if (key root-_key)//{// if (root-_left nullptr)// {// root-_left new Node(key);// return true;// }// else// return _InsertR(root-_left, key);//}//else// return false;//方式2 bool _InsertR(Node* root, const K key)if (root nullptr){root new Node(key);return true;}if (key root-_key)return _InsertR(root-_right, key);else if (key root-_key)return _InsertR(root-_left, key);elsereturn false;}这里的二叉搜索树无法保证左右平衡。
删除的过程Erase/EraseR
首先查找元素是否在二叉搜索树中如果不存在则返回, 否则要删除的结点可能分下面四种情况
要删除的结点无孩子结点–直接删除其父节点原来指向它的变成指向空要删除的结点只有左孩子结点–托孤让该节点的父节点直接指向该节点的孩子节点要删除的结点只有右孩子结点–托孤让该节点的父节点直接指向该节点的孩子节点要删除的结点有左、右孩子结点–替换找左子树的最大和右子树的最小
看起来待删除节点的处理方式有4种情况实际上情况1可以与情况2或者3合并起来因此真正的删除过程如下
删除该结点且使被删除节点的父结点指向被删除节点的左孩子结点–直接删除删除该结点且使被删除节点的父结点指向被删除结点的右孩子结点–直接删除在它的右子树中寻找中序下的第一个结点(关键码最小)用它的值填补到被删除节点中再来处理该结点的删除问题–替换法删除
//普通版本
bool Erase(const K key)
{Node* parent nullptr;Node* cur _root;while (cur){//与根节点比较比根节点的值大往右走比根节点的值小往左走if (key cur-_key){parent cur;cur cur-_right;}else if (key cur-_key){parent cur;cur cur-_left;}else{//能走到这就说明找到了要删除的这个节点要删除的节点为cur//情况1左子节点为空右子节点不为空if (cur-_left nullptr){//需要特殊处理根节点因为根节点无父节点if (cur _root){_root cur-_right;}else{//cur为parent的左子节点cur的子节点就得继承parent的左子节点if (parent-_left cur){parent-_left cur-_right;}//cur为parent的右子节点cur的子节点就得继承parent的右子节点else{parent-_right cur-_right;}}delete cur;}//情况2左子节点不为空右子节点为空else if (cur-_right nullptr){//需要特殊处理根节点因为根节点无父节点if (cur _root){_root cur-_left;}else{//cur为parent的左子节点cur的子节点就得继承parent的左子节点if (parent-_left cur){parent-_left cur-_left;}//cur为parent的右子节点cur的子节点就得继承parent的右子节点else{parent-_right cur-_left;}}delete cur;}//情况3左右子节点均不为空else{//在cur的右子树中寻找中序的第一个结点Node* parent cur;Node* minRight cur-_right;//此处前置条件是cur的左右子树均不为空while (minRight-_left){parent minRight;minRight minRight-_left;}//交换cur和minRight的值cur-_key minRight-_key;//删除minRightif (minRight parent-_left)parent-_left minRight-_right;elseparent-_right minRight-_right;delete minRight;}return true;}}//走到这说明没找到return false;
}//递归版本
public:bool EraseR(const K key){return _EraseR(_root, key);}
private:bool _EraseR(Node* root, const K key){if (root nullptr)return false;if (key root-_key){return _EraseR(root-_right, key);}else if (key root-_key){return _EraseR(root-_left, key);}else{Node* del root;//相等就开始删除if (root-_left nullptr){root root-_right;}//情况2左子节点不为空右子节点为空else if (root-_right nullptr){ root root-_left;}//情况3左右子节点均不为空else{Node* minRight root-_right;while (minRight-left){minRight minRight-left;}swap(root-_key, minRight-_key);// 转换成在子树中去删除节点return _EraseR(root-_right, key);}delete del;return true; }}中序遍历InOrder
在不暴露根节点_root的情况下比如写一个函数getroot()等让用户获取套一层函数接口就直接在类内使用这个_root实现中序遍历
void InOrder()
{_InOrder(_root);std::cout std::endl;
}
private:
void _InOrder(Node* root)
{//中序左根右if (root nullptr) return;_InOrder(root-_left);std::cout root-_key ;_InOrder(root-_right);
}注意二叉搜素树不支持改对于二叉搜索树而言仅仅修改对应节点的值极有可能破坏原结构所以改删除插入
构造函数、拷贝构造函数、赋值构造函数、析构函数
public:BSTree():_root(nullptr){}BSTree(const BSTreeK t){_root Copy(t._root);}BSTreeK operator(BSTreeK t){swap(_root, t._root);return *this;}~BSTree(){Destory(_root);_root nullptr;}
private:void Destory(Node* root){if (root nullptr)return;//按后序来删除Destory(root-_left);Destory(root-_right);delete root;}Node* Copy(Node* root){if (root nullptr)return nullptr;//前序遍历再递归拷贝Node* newnode new Node(root-_key);newnode-_left Copy(root-_left);newnode-_right Copy(root-_right);return newnode;}应用场景
K模型–判断某个key在不在的场景KV模型–通过key查找或修改value
K模型K模型即只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到的值。
比如给一个单词word判断该单词是否拼写正确具体方式如下以词库中所有单词集合中的每个单词作为key构建一棵二叉搜索树在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误。其他场景检查单词拼写是否正确/车库出入系统/宿舍楼门禁系统
KV模型每一个关键码key都有与之对应的值Value即Key, Value的键值对。该种方式在现实生活中非常常见
比如英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英文单词与其对应的中文word, chinese就构成一种键值对再比如统计单词次数统计成功后给定单词就可快速找到其出现的次数单词与其出现次数就是word, count就构成一种键值对。其他场景英汉互译/学号学生对应
性能分析
插入和删除操作都必须先查找查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数即结点越深则比较次数越多。 但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树
最优情况下二叉搜索树为完全二叉树(或者接近完全二叉树)其平均比较次数为log2Nlog_2 Nlog2N最差情况下二叉搜索树退化为单支树(或者类似单支)其平均比较次数为N2\frac{N}{2}2N
但是如果退化成单支树二叉搜索树的性能就很差后续引入红黑树和AVL树来解决。
