mysql数据结构与算法(二分查找法及二叉查找树)
mysql数据结构与算法(二分查找法及二叉查找树)
走世界 发表于3个月前
mysql数据结构与算法(二分查找法及二叉查找树)
  • 发表于 3个月前
  • 阅读 1
  • 收藏 0
  • 点赞 0
  • 评论 0
摘要: mysql索引前言之数据结构与算法

 B+树索引是最为常见,也是在数据库中使用最为频繁的一种索引。在了解索引之前先介绍与之密切相关的一些算法与数据库结构,这有助于读者更好的理解B+树索引的工作方式。

二分查找法

    二分查找法也称为折半查找法,用来查找一组有序记录数组中某一项记录,基本思想是将记录按有序化排列(递增递减),查找过程采用跳跃方式查找,即先以有序数列的重点位置为对比对象,如果要找的元素小于该中点元素,则将待查找序列缩小为左半部分,否则右半部分。如下对5、10、19、21、31、37、42、48、50、52这10个数,要从中查找48这条记录。

从上可以看出3次就找到了48这个数,如果要是按顺序查找则需要8次。因此二分查找法的效率(平均来说)比顺序查找法要好。如下采用java递归方式完成二分查找算法

/** 
 * 递归方法实现二分查找法. 
 * @param Array数组 
 * @param low 数组第一位置 
 * @param high 最高 
 * @param key 要查找的值. 
 * @return 返回值. 
 */  
int BinSearch(int Array[],int low,int high,int key)  
{  
    if (low<=high)  
    {  
        int mid = (low+high)/2;  
        if(key == Array[mid])  
            return mid;  
        else if(key<Array[mid])  
            //移动low和high  
            return BinSearch(Array,low,mid-1,key);  
        else if(key>Array[mid])  
            return BinSearch(Array,mid+1,high,key);  
    }  
    else  
        return -1;  
}

二叉查找树

定义

    二叉查找树或者是一棵空树,或者具有下列性质:

  • 若它的左子树不为空,则左子树上所有结点的值均小于根结点的值;
  • 若它的右子树不为空,则右子树上所有结点的值均大于根结点的值;
  • 它的左右子树均为二分查找树。

插入操作

    如s指向待插入的结点,root指向二叉查找树的根结点,则插入操作的步骤如下:

  • 若root为空,则将s指向的结点作为跟结点插入,否则执行(2)、(3);
  • 若s->data < root->data,则将s指向的结点插入到根结点的左子树中;
  • 若s->data > root->data,则将s指向的结点插入到根结点的右子树中。

    总结:二叉树的构造就是通过不断地插入新的元素。

查找操作

    在二叉查找树中查找给定值k的查找过程如下:

  • 若root=NULL,则查找失败;
  • 若root->data=k,则查找成功;
  • 若k <  root->data,则去root的左边查找;
  • 若k > root->data,则去root的右边查找。

    总结:若二叉查找树接近平衡二叉树,则其时间复杂度为O(logn),若二叉查找树是斜的(如插入是有序插入的情况下),则其实际复杂度为O(n),即退化为线性表。

删除操作

    设p指向待删除的结点,pre指向待删除结点的父亲,则删除操作视如下情况而定:

  • 若待删除的结点是叶子结点,不妨设pre->right=p(即待删除的结点为其父亲结点的右孩子),则直接删除p,对应为:pre->right=NULL,delete p;
  • 若待删除的结点只有左子树或右子树,则只需将待删除结点的父亲与左孩子(或右孩子)连接起来,对应为,不妨设pre->right=p,以待删除结点仅有左子树的情况为例(右子树同理),对应为:pre->right=p->left,delete p;
  • 若待删除结点左右子树则
    • 先找到待删除结点的右子树中的最小值(或左子树中的最大值),对应的指针为min,并记下min的父亲结点为min_pre;
    • 用min所指结值覆盖待删结点的值,对应为:p->data=min->data;
    • 特殊情况:若待删除结点的右孩子无左子树,也就是说待删结点的右孩子就是右子树的最大值,则直接连接即可,对应为:p->right=min->right,delete min;

    •  

      一般情况:若待删除结点的右孩子有左子树,则将min_pre所指结点的右孩子指向min所只结点的右孩子,对应为:min_pre->right=min->right,delete min;

    总结:找到右子树的最小值结点-->连接断开结点-->对最小值结点的上下文做善后工作。

二叉查找树远不止这些内容,在这里之是作为一个引子,今后会对二叉查找树进行详细学习和描述。

共有 人打赏支持
粉丝 2
博文 74
码字总数 70763
×
走世界
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: