手机网站设计建设服务,遵义建设厅官方网站 元丰,网站建设信息表,wordpress自动提取标签一、概念
二叉搜索树又称二叉排序树#xff0c;它或者是一棵空树#xff0c;或者是具有以下性质的二叉树:
若它的左子树不为空#xff0c;则左子树上所有节点的值都小于根节点的值若它的右子树不为空#xff0c;则右子树上所有节点的值都大于根节点的值它的左右子树也分别…一、概念
二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树:
若它的左子树不为空则左子树上所有节点的值都小于根节点的值若它的右子树不为空则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树 二、二叉搜索树的操作
1. 查找
从根开始比较查找比根大则往右边走查找比根小则往左边走查找最多查找高度次走到空还没找到这个值不存在
2. 插入
插入的具体过程如下
树为空则直接新增节点赋值给root指针树不空按二叉搜索树性质查找插入位置插入新节点
3. 删除
首先查找元素是否在二叉搜索树中如果不存在则直接返回 否则要删除的结点可能分下面四种情况
a. 要删除的结点无孩子结点
b. 要删除的结点只有左孩子结点
c. 要删除的结点只有右孩子结点
d. 要删除的结点有左、右孩子结点
情况a可以与情况b或者c合并起来因此真正的删除过程如下
情况b删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点–直接删除情况c删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点–直接删除情况d在它的右子树中寻找中序下的第一个结点关键码在右子树中最小用它的值填补到被删除节点中再来处理该结点的删除问题–替换法删除 依次删除上图的7、14、3、8 7、14属于直接删除的场景 3、8属于需要替换法进行删除的场景 三、二叉搜索树的实现
1. 基本框架
namespace K
{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:BSTree():_root(nullptr){}//……各种函数private:Node* _root;};
}2. 构造和析构
namespace nb
{//……templateclass Kclass BSTree{typedef BSTreeNodeK Node;public:BSTree():_root(nullptr){}BSTree(const BSTreeK tree){_root Copy(tree._root);}~BSTree(){Destroy(_root);}private:Node* Copy(Node* root){if (root nullptr) return nullptr;//前序构建树Node* newRoot new Node(root-_k);newRoot-_left Copy(root-_left);newRoot-_right Copy(root-_right);return newRoot;}void Destroy(Node* root){if (root nullptr) return;//后序销毁树Destroy(root-_left);Destroy(root-_right);delete root;}private:Node* _root;};
}3. 查找
实现可以使用迭代也可以使用递归。 递归版本需要写一个子函数因为类外部是不能直接访问私有成员变量_root的
bool Find(const K key)
{Node* cur _root;while (cur){if (key cur-_key){//大了往右边查找cur cur-_right;}else if (key cur-_key){//小了往左边查找cur cur-_left;}else{//查找到了return true;}}//没有查找到return false;
}
//递归版
bool FindR(const K key)
{return _FindR(_root, key);
}
bool _FindR(Node* root, const K key)
{if (root nullptr)return false;if (key root-_key)return _FindR(root-_left, key);else if (key root-_key)return _FindR(root-_right, key);elsereturn true;
}4. 插入
bool Insert(const K key)
{//是空树直接赋值if (_root nullptr){_root new Node(key);return true;}//不是空树找到对应位置在插入Node* cur _root;Node* parent nullptr;//记录双亲节点用于链接newNodewhile (cur){if (key cur-_key){parent cur;cur cur-_right;}else if (key cur-_key){parent cur;cur cur-_left;}else{//树中已经有该key则不插入return false;}}cur new Node(key);//key大了往右边插小了往左边插if (cur-_key parent-_key){parent-_right cur;}else{parent-_left cur;}return true;
}
//递归版
bool InsertR(const K key)
{return _InsertR(_root, key);
}
//注意root传引用
bool _InsertR(Node* root, const K key)
{//走到空时插入此时的root是上一次根的左指针或右指针的引用if (root nullptr){root new Node(key);return true;}//key大了往右边走小了往左边走if (key root-_key){return _InsertR(root-_right, key);}else if (key root-_key){return _InsertR(root-_left, key);}else{return false;}
}5. 删除
直接删除 替换法删除 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 // 找到相等节点开始删除操作{// 1. 左为空// 2. 右为空// 3. 左右不为空if (cur-_left nullptr){// 特判一下cur为根的情况此时parent为空不能解引用// if (parent nullptr)// 也可以用这个判断条件if (cur _root){//左为空指向右_root _root-_right;}else{//链接时需要判断是根的左还是右再将根的左或右链接cur的右if (cur parent-_left){parent-_left cur-_right;}else{parent-_right cur-_right;}}//最后删除delete cur;}else if (cur-_right nullptr){//右为空与左为空处理过程基本相同if (cur _root){_root _root-_left;}else{if (cur parent-_left){parent-_left cur-_left;}else{parent-_right cur-_left;}}delete cur;}else{//左右不为空parent cur;//当前要删除的节点//先找右子树的最小节点Node* minRight cur-_right;while (minRight-_left){parent minRight;minRight minRight-_left;}//将minRight替换到curcur-_key minRight-_key;//链接if (minRight parent-_left){parent-_left minRight-_right;}else{parent-_left minRight-_right;}//删除delete minRight;}return true;}}return false;
}//递归版
bool EraseR(const K key)
{return _EraseR(_root, key);
}
//root传引用用于链接
bool _EraseR(Node* root, const K key)
{if (root nullptr){return false;}if (key root-_key){return _EraseR(root-_left, key);}else if (key root-_key){return _EraseR(root-_right, key);}else{Node* del root;if (root-_left nullptr) //左为空{root root-_right;}else if (root-_right nullptr) //右为空{root root-_left;}else //左右不为空递归处理子树{Node* minRight root-_right;while (minRight-_left){minRight minRight-_left;}//替换swap(root-_key, minRight-_key);//递归处理子树在右子树中删除keyreturn _EraseR(root-_right, key);}delete del;return true;}
} 四、二叉搜索树的应用
K模型K模型即只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到的值。
比如给一个单词word判断该单词是否拼写正确具体方式如下 以词库中所有单词集合中的每个单词作为key构建一棵二叉搜索树 在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误。
KV模型每一个关键码key都有与之对应的值Value即Key, Value的键值对。
该种方式在现实生活中非常常见
比如英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英文单词与其对应的中文Word, Chinese就构成一种键值对
再比如统计单词次数统计成功后给定单词就可快速找到其出现的次数单词与其出现次数就是word, count就构成一种键值对。
将二叉搜索树改造为KV结构也比较简单整体代码 二叉搜索树整体代码 五、二叉搜索树的性能分析
插入和删除操作都必须先查找查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是结点在二 叉搜索树的深度的函数即结点越深则比较次数越多。 但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树 最优情况下二叉搜索树为完全二叉树(或者接近完全二叉树)其平均比较次数为log2Nlog_2 Nlog2N
最差情况下二叉搜索树退化为单支树(或者类似单支)其平均比较次数为N2\frac{N}{2}2N
问题如果退化成单支树二叉搜索树的性能就失去了。那能否进行改进不论按照什么次序插入关键码二叉搜索树的性能都能达到最优此时AVL树和红黑树就可以上场了。
