文档章节

mysql数据结构与算法(二分查找法及二叉查找树)

走世界
 走世界
发布于 2017/08/31 00:00
字数 1187
阅读 5
收藏 0

 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;

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

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

© 著作权归作者所有

共有 人打赏支持
走世界
粉丝 5
博文 96
码字总数 91434
作品 0
和平
程序员
私信 提问
算法-数据结构

时间复杂度 O(log n) 意味着什么? 写给小白的时间复杂度指南 查找算法的 Java 实现 查找算法的 Java 实现 两个有序数组合并成一个有序数组 用拉链法和线性探测法解决哈希冲突 用拉链法和线性...

掘金官方
2017/12/14
0
0
二叉排序树(Binary Sort Tree)

1、定义 二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为:二叉排序树或者是空树,或者是满足如下性质的二叉树: ① 若它的左子树非空,则左子树上所有...

野渡书生
2016/04/28
96
0
算法——几种查找算法的比较和应用

几种基础查找方法的性能比较: 算法(数据结构) 查找(最坏) 插入(最坏) 查找命中(平均) 插入(平均) 插入(平均)是否支持有序性相关操作 顺序查询(无序联播) N N N/2 N 否 二分查...

努力学习ding
03/08
0
0
算法与数据结构(五)二叉搜索树

二叉搜索树 (Binary Search Tree) 核心是解决问题。高效解决问题。 查找问题 Searching Problem: 查找问题是计算机中非常重要的基础问题 查找问题的基础:二分查找法 Binary Search 对于有序...

天涯明月笙
2017/09/16
0
0
常用的排序/查找算法的时间复杂度和空间复杂度

常用的排序算法的时间复杂度和空间复杂度 排序法 最差时间分析 平均时间复杂度 稳定度 空间复杂度 冒泡排序 O(n2) O(n2) 稳定 O(1) 插入排序 O(n2) O(n2) 稳定 O(1) 选择排序 O(n2) O(n2) 稳...

xiaomin0322
04/27
0
0

没有更多内容

加载失败,请刷新页面

加载更多

“敏捷开发”怎么就“敏捷”了

什么是敏捷开发 传统的软件开发过程中,我们往往会针对特定的用户需求,采用“瀑布模型”,从用户的需求开始一步步进行需求分析、软件设计、软件开发、软件测试以及软件交付与维护。 然而,这...

SamYjy
43分钟前
2
0
聊聊我怎么系统学习Linux技能并快速提高的

随着电子信息科技时代的发展,学会使用计算机在我们的生活中成为了必不可少的一项技能。而作为计算机中的三大操作系统之一的Linux更是饱受计算机爱好者们的喜爱。今天我们就来和大家一起聊一...

linuxprobe16
55分钟前
3
0
MySQL专题—— 从认识索引到理解索引【索引优化】

认识索引 认识索引是什么东西非常关键,一个非常恰当的比喻就是书的目录页与书的正文内容之间的关系,为了方便查找书中的内容,通过对内容建立索引形成目录。因此,首先你要明白的一点就是,...

架构师springboot
59分钟前
2
0
Java-怎样构造方法和匿名对象

前言 在编写程序时不安全的初始化会导致程序发生发生重大错误。为了使程序可以被安全地初始化,C++引入了构造器(也可以成为构造方法)的概念,这是一个在创建对象时被自动调用的特殊方法。J...

小刀爱编程
今天
2
0
7、MyBaties 增删改

事务 : 从数据库角度出发,完成业务时需要执行的 SQL 集合,统称一个事务. 1、在 mybatis 中默认是关闭了 JDBC 的自动提交功能 每一个 SqlSession 默认都是不自动提交事务. session.commit()提...

KingFightingAn
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部