文档章节

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

走世界
 走世界
发布于 2017/08/31 00:00
字数 1187
阅读 3
收藏 0
点赞 0
评论 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;

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

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

© 著作权归作者所有

共有 人打赏支持
走世界
粉丝 3
博文 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
常用的排序/查找算法的时间复杂度和空间复杂度

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

xiaomin0322
04/27
0
0
数据结构与算法——常用数据结构

把数据结构与算法C++描述大致的翻了一遍,把里面大致提到的数据结构和算法的名词记录下来,逐一攻克。 Go and fight! 链表:链表由一系列不必在内存中相连的数据组成,每一个节点均包含表元素...

mettaworldpeace
2014/03/03
0
0
B树文件系统树

二叉排序树或者二叉搜索树 即二叉搜索树: 1.所有非叶子结点至多拥有两个儿子(Left和Right); 2.所有结点存储一个关键字; 3.非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其...

满小茂
2016/01/09
204
0
算法之路

最近在GitHub上看到的某位学友的算法学习规划,贴过来与各位共勉。有新的内容可以文末留言补充。 学习方法 把所有经典算法写一遍 看算法有关源码 加入算法学习社区,相互鼓励学习 看经典书籍...

李序锴
2017/11/08
0
0
查找算法总结

查找算法:顺序查找、二分查找、分块查找、二叉查找树、B树、B+树 一、二分查找(常规) 题目描述: (牛客网http://www.nowcoder.com/practice/28d5a9b7fc0b4a078c9a6d59830fb9b9?rp=1&ru=/...

阿阿阿阿阿局
2016/07/28
20
0
JavaScript 算法与数据结构 - javascript-algorithms

javascript-algorithms 包含了多种基于 JavaScript 的算法与数据结构。 每种算法和数据结构都有自己的 README 并提供相关说明以及进一步阅读和 YouTube 视频。 数据结构 数据结构是在计算机中...

匿名
05/31
0
0
JavaScript 算法与数据结构

本仓库包含了多种基于 JavaScript 的算法与数据结构。 每种算法和数据结构都有自己的 README 并提供相关说明以及进一步阅读和 YouTube 视频。 数据结构 数据结构是在计算机中组织和存储数据的...

a独家记忆
06/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Centos7通过yum安装nginx

添加源地址(直接install可能不是最新版本的) sudo rpm -Uvh http://nginx.org/packages/centos/7/noarch/RPMS/nginx-release-centos-7-0.el7.ngx.noarch.rpm 安装 sudo yum install -y ng......

iplusx
8分钟前
0
0
ef .core Dapper Helper

using System; using System.Collections.Generic; using System.Configuration; using System.Data; using System.Data.SqlClient; using System.Threading.Tasks; using Dapper; using Dap......

Lytf
9分钟前
0
0
iOS 小笔记

1.以下代码打印什么     __block int val = 10;    void (^blk)(void) = ^{        printf("val=%d\n",val);        };       val = 2;    blk(); /...

风了个1
11分钟前
0
0
【Spring Boot 系列 Spring Boot示例程序】

入门程序步骤,创建一个Maven项目。继承Spring Boot官方提供的父工程。再引入一个Web的应用启动器。 1、选择一个合适的IDEA工具 创建一个Maven工程,并添加如下配置 <parent> <...

HansonReal
13分钟前
0
0
217. Contains Duplicate - LeetCode

Question 217. Contains Duplicate Solution 题目大意:判断数组中是否有重复元素 思路:构造一个set,不重复就加进去,重复返回true,如果数据量大的话,可以用布隆过滤器 Java实现: publ...

yysue
17分钟前
0
0
istio 处理失败 (理论)

Envoy提供了一套开箱即用的选择加入故障恢复功能,可以通过应用程序中的服务进行利用。功能包括: 超时 具有超时预算和重试之间的可变抖动的有界重试 限制并发连接数和对上游服务的请求 对负...

xiaomin0322
18分钟前
0
0
eclipse解决git冲突举例

本地修改了两个文件,提交时提示有冲突,想来应该是没有从远程仓库下载最新代码导致的。通过右击项目 -> Team -> Sychronized WorkSpace,比较本地仓库和远程仓库的异同:   此时没有更好的...

Code辉
27分钟前
0
0
运行.jar后缀的文件

前提必须安装了jdk,正确配置环境变量。 在dos窗口执行以下命令即可。 java -jar C:\Users\10492\Desktop\turn.jar

haha360
29分钟前
0
0
Java程序员如何做代码压力测试?【JWordPress前台项目实战】

代码 pom.xml文件引入包 <dependency><groupId>com.taobao.stresstester</groupId><artifactId>stresstester</artifactId><version>1.0</version></dependency> 编写测试代码 /**......

迷你芊宝宝
34分钟前
0
0
面试宝典-什么是缓存穿透?

缓存穿透是说收到了一个请求,但是该请求缓存里没有,只能去数据库里查询,然后放进缓存。 这里面有两个风险,一个是同时有好多请求访问同一个数据,然后业务系统把这些请求全发到了数据库;...

suyain
40分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部