聊城网站营销,案例网站有哪些,成都校园兼职网站建设,网站外包公司文章目录1 二叉搜索树概念2 二叉搜索树操作与模拟实现2.1 二叉搜索树的查找非递归版本递归版本2.2 二叉搜索树的插入非递归版本递归版本2.3 二叉搜索树的删除非递归版本递归版本3 二叉搜索树的应用#xff08;K模型、KV模型#xff09;4 二叉搜索树的性能分析1 二叉搜索树概念…
文章目录1 二叉搜索树概念2 二叉搜索树操作与模拟实现2.1 二叉搜索树的查找非递归版本递归版本2.2 二叉搜索树的插入非递归版本递归版本2.3 二叉搜索树的删除非递归版本递归版本3 二叉搜索树的应用K模型、KV模型4 二叉搜索树的性能分析1 二叉搜索树概念
二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树:
若它的左子树不为空则左子树上所有节点的值都小于根节点的值若它的右子树不为空则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树一般情况下二叉搜索树的数据是不能重复的
2 二叉搜索树操作与模拟实现
完整代码K模型和KV模型代码链接 结点定义
templateclass K
struct BSTreeNode
{BSTreeNodeK* _left;BSTreeNodeK* _right;K _key;BSTreeNode(const K key):_key(key), _left(nullptr), _right(nullptr){}
};typedef BSTreeNodeK Node;2.1 二叉搜索树的查找 a、从根开始比较查找比根大则往右边走查找比根小则往左边走查找。 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;
}递归版本
bool _FindR(Node* root, const K key)
{if (root nullptr)//没找到return false;if (root-_key key)//被查找到的值大于当前结点去右树找return _FindR(root-_right, key);else if (root-_key key)//被查找到的值小于当前结点去左树找return _FindR(root-_left, key);else//找到了return true;
}2.2 二叉搜索树的插入
插入的具体过程如下 a. 树为空则直接新增节点给root指针赋值 b. 树不空按二叉搜索树性质查找插入位置插入新节点
代码实现
非递归版本
bool Insert(const K key)
{if (_root nullptr){_root new Node(key);return true;}Node* parent nullptr;//记录父节点Node* cur _root;//_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此时为nullptr//父节点parent也被记录cur new Node(key);if (parent-_key key)//寻找该正确的插入位置{parent-_right cur;}else{parent-_left cur;}return true;
}递归版本
可以考虑再增加一个parent参数。 但下面的方法更加巧妙 下面代码传root的引用两个用处 1、如果传进来的就是一颗空树直接给root赋值就可以了比较容易理解. 2、因为传的是引用所以root也是上一步递归传入的root-right或者root-_left的别名非常巧妙的是root new Node(key);就等价于root-rightnew Node(key);或者root-_leftnew Node(key);刚好把结点就赋值到正确的位置省去了上面非递归方法的还需要记录父节点的步骤。
bool _InsertR(Node* root, const K key)//注意细节传的是root的引用
{ if (root nullptr){root new Node(key);return true;}if (root-_key key)//插入的值比当前的结点的值大就往右树走。return _InsertR(root-_right, key);else if (root-_key key)//插入的值比当前的结点的值小就往左树走。return _InsertR(root-_left, key);else//插入的值和当前结点的值相等不需要插入返回falsereturn false;
}下面是插入9的代码调试可以发现确实root和上一步root-left的地址是一样的可见引用在C中的作用是多么大。 2.3 二叉搜索树的删除
首先查找元素是否在二叉搜索树中如果不存在则返回, 否则要删除的结点可能分下面四种情况 a. 要删除的结点无孩子结点例如1、4、7、13 b. 要删除的结点只有左孩子结点例如14 c. 要删除的结点只有右孩子结点例如10 d. 要删除的结点有左、右孩子结点例如3、6、8 看起来删除节点有4种情况实际情况a可以与情况b或者c合并起来因此真正的删除过程如下
情况b删除该结点并且使该删除节点的双亲结点指向该删除节点的左孩子结点——直接删除托孤情况c删除该结点并且使该删除节点的双亲结点指向该删除结点的右孩子结点——直接删除托孤情况d 找被删除结点 左子树的最大 或者 右子树的最小 用它的值填补到被删除节点中(这样才能保证二叉排序树的结构不被破坏)再来删除这个 左子树最大 或者 右子树最小结点——替换法删除。
针对情况d下面图中想删除8用左子树的最大或者右子树的最小 那么由于二叉排序树特殊的结构其实 左子树的最大 也就是 左子树的最右结点——从上往下遍历第一个没有右孩子的结点——7 右子树的最小 也就是 右子树的最左结点——从上往下遍历第一个没有左孩子的结点——10
代码实现 提前声明下面非递归和递归版本都用的是右子树的最小结点来进行替换删除的。 具体细节详解在下面代码注释中一边看图一边看代码注释效果更佳
非递归版本
bool Erase(const K key)
{Node* parent nullptr;//记录父节点Node* cur _root;//_root成员变量while (cur){//能找到开始删除if (cur-_key key){parent cur;cur cur-_right;}else if (cur-_key key){parent cur;cur cur-_left;}else//被删除目标已经找到就存在cur里{if (cur-_left nullptr)//被删除结点的左为空——只有右孩子{//if (parent 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 (parent 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* parent cur; //细节赋值curNode* minRight cur-_right;while (minRight-_left){parent minRight;minRight minRight-_left;}//运行到这里已经找到了右子树最小结点cur-_key minRight-_key;//直接覆盖被删除结点的值或者让右子树和被删除结点交换都可以//minRight是右子树的最左结点——一定没有左孩子//而且要特别注意删除3和删除8结点是不一样的一定要考虑全面if (minRight parent-_left)//删除8结点的情况对于10结点的处理{parent-_left minRight-_right;}else//删除3结点的情况对于4结点的处理{parent-_right minRight-_right;}delete minRight;}return true;}}//找不到需要被删除的节点返回falsereturn false;
}递归版本
bool _EraseR(Node* root, const K key)
{if (root nullptr)//没有找到 或者 root一开始传入的就是一个空树{return false;}//开始找要被删除的结点并将其删除if (root-_key key)//要被删除的值比当前的值大就再去右树找{return _EraseR(root-_right, key);}else if (root-_key key)//要被删除的值比当前的值小就再去左树找{return _EraseR(root-_left, key);}else//找到了开始删除{Node* del root;//记录当前结点方便后面delete//被删除结点只有左孩子例如14if (root-_right nullptr){root root-_left;//被赋值的root也是上一层递归root-_right的别名}//被删除结点只有右孩子例如10else if (root-_left nullptr){root root-_right;//被赋值的root也是上一层递归root-_left的别名}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;}
}完整代码K模型和KV模型代码链接
3 二叉搜索树的应用K模型、KV模型
K模型K模型即只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到的值。比如给一个单词word判断该单词是否拼写正确具体方式如下
以词库中所有单词集合中的每个单词作为key构建一棵二叉搜索树在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误。
KV模型每一个关键码key都有与之对应的值Value即Key, Value的键值对。该种方式在现实生活中非常常见
比如英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英文单词与其对应的中文word, chinese就构成一种键值对再比如统计单词次数统计成功后给定单词就可快速找到其出现的次数单词与其出现次数就是word, count就构成一种键值对。
4 二叉搜索树的性能分析
插入和删除操作都必须先查找查找效率代表了二叉搜索树中各个操作的性能。 对有n个结点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数即结点越深则比较次数越多。 但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树 最优情况下二叉搜索树为完全二叉树(或者接近完全二叉树)其平均比较次数为log2Nlog_2 Nlog2N。 最差情况下二叉搜索树退化为单支树(或者类似单支)其平均比较次数为N{N}N。
