Allbet
热门标签

联博开奖:一文彻底掌握二叉查找树(多组动图)(史上最全总结)

时间:3周前   阅读:287   评论:11

这是查{找}算法系列文章〖的〗第二篇,助你彻底掌握 二叉查{找}树[

在数据结构中, 二叉查{找}树[无疑是极为主要〖的〗,然则初学者明白起来却有些吃力,网上〖的〗文章讲得也不太周全。本文希望连系多组动图、图片以及详细〖的〗代码实现,力争让人人完全掌握 二叉查{找}树[(BST)〖的〗种种观点和操作。 相信你看完一定会有收获。

先看一下本文〖的〗目录吧!每个操作都配有动图和详细实现代码(Java)

首先,<若是你对树和二>叉树〖的〗界说不是很领会〖的〗话,建议先去看一下这个系列〖的〗第一篇文章一文入门二叉树,力图对树有一个基本〖的〗熟悉,再来学习!

靠山和必要性

靠山

现代计算机和网络使我们能够接触和接见海量〖的〗信息,以是高效〖的〗检索这些信息将是一个伟大〖的〗挑战。这包罗信息〖的〗存储、处置和查{找}。这一问题促使我们去研究经典查{找}算法,即若何高效〖的〗存储和查{找}数据?

目〖的〗

实现一个符号表,我们将信息(『键』-值)储存在符号内外,凭据响应〖的〗『键』去查{找}它所对应〖的〗值。你可以把它想象成一个字典,我们在字典中存储了大量〖的〗词语〖的〗释义,我们应该能够凭据词语(索引)去查{找}这个词语对应〖的〗意思。

{如}下图所示,就是一个很简朴〖的〗符号表,我们可以很轻松〖的〗通过『键』来查{找}值,然则,基于《数组》或者链表〖的〗这种数据结构并不高效,而且不能较好〖的〗维持一定〖的〗性子(好比我用《数组》存储了许多数据,你让我{找}到最大〖的〗谁人,我该怎么办呢?先在内部排序再输出,然则,不高效!你是不是会想有没有一种数据结构自然就知足这种性子?)


〖总结一下〗,我们希望实现一个高效〖的〗符号表,它支持插入、查{找}、求最大『键』和最小『键』、求前驱节点(我们一会再说)和后驱节点等等,它〖的〗时间庞大度呢?我们只管向O(logN)看齐。这就是我们今天〖的〗主角-- 二叉查{找}树[

二叉树知识回首

首先,<若是你对树和二>叉树〖的〗界说不是很领会〖的〗话,建议先去看一下这个系列〖的〗第一篇文章一文入门二叉树,力图对树有一个基本〖的〗熟悉,再来学习

二叉树〖的〗界说

直接上几组图,你只需要记着<每个节点至多有两个子>节点即可。


这几张图险些代表了所有类型〖的〗二叉树,你会发现,最后两个着实就是链表,没错,二叉树成功地退化成了链表,那性能上一定会下降,然则关于这个问题若何制止却不在本文〖的〗范围内,这是下一期文章要解决〖的〗问题--[红黑树]。我们在这里只是熟悉一“下二叉树〖的〗界说就好了”。

二叉树〖的〗存储方式

上一篇文章我们就已经先容过,这里再重复一遍。二叉树〖的〗存储方式主要《有两种》:链式存储法和线性存储法,它们划分对应着链表和《数组》。完全二叉树最好用《数组》存放,由于《数组》下标和父子节点之间存在着完善〖的〗对应关系,而且也能够尽最大可能〖的〗节约内存,如图一所示。

我们把根节点储存在下标为i=1〖的〗位置,那么左子节点储存在2*i=2〖的〗位置,右子节点储存在下标为2*i+1=2〖的〗位置。依此类推,完成树〖的〗存储。借助下标运算,我们可以很轻松〖的〗从父节点跳转到左子节点和(右子节点或者从)随便一个子节点{找}到它〖的〗父节点。若是X〖的〗位置为i,则它〖的〗两个子节点〖的〗下标划分为2i2i+1,它〖的〗父节点〖的〗位置为i/2(这里效果向下取整)。


相比用《数组》存储数据,链式存储规则响应〖的〗加倍天真,我们使用自界说类型Node来示意每一个节点。

class Node{
	int data;
	Node left,right;
}

每个节点都是一个Node工具,它包罗我们所需要存储〖的〗数据,指向左子节点〖的〗引用,直向右子节点〖的〗引用,就像链表一样将整个树串起来。若是该节点没有左子节点,则Node.left==null或者Node.right==null,如图二所示。能明白就行,别在意它〖的〗雅观度了:)

二叉树〖的〗遍历

二叉树〖的〗遍历有三种方式:前序遍历,『中序遍历和后序遍历』。在这里我只媾和本文我们实现 二叉查{找}树[相关〖的〗中序遍历,若是你希望领会更多,请看上一篇文章吧,那里我给出了详细〖的〗代码和图示。

所谓中序遍历,就是指:对于树中〖的〗随便节点来说,<先打印>它〖的〗左子树,然后再打印它本身,最后打印它〖的〗右子树。详细〖的〗代码是用递归实现〖的〗,对照容易明白。

public void inOrder(Node root){
	if(root==null) return;
	inOrder(root.left);
	Systrm.out.println(root.data);
	inOrder(root.right);
}

你可以连系下面这张图明白一下


以上,我们回首了二叉树〖的〗基本知识,请确保你已经完全掌握。接下来我们将先容今天〖的〗主角 二叉查{找}树[(Binary Search Tree),它是一种符号表,成功地将链表插入〖的〗天真性和【有序】《数组》查{找}〖的〗高效性连系起来。听起来是不是很完善?

二叉查{找}树[

一起来看一下它〖的〗界说吧,着实只是在二叉树〖的〗界说上做了一个小小〖的〗限制:

一棵 二叉查{找}树[是一棵二叉树,其中每个节点〖的〗『键』都大于它〖的〗左子树上〖的〗随便节点〖的〗『键』,而且小于右子树上随便节点〖的〗『键』

只要根据这个规则,我们组织出来〖的〗树就是 二叉查{找}树[。现在,请仔细看一下上文所有带数字〖的〗树,它们都是 二叉查{找}树[。
你可能会发现若是我们对 二叉查{找}树[举行中序遍历〖的〗话,获得〖的〗序列是【有序】〖的〗,这是 二叉查{找}树[天生〖的〗天真性。详细也可以看一下下面这幅图:

准备完热身运动,接下来我们就正式进入 二叉查{找}树[〖的〗解说:)。

  • 数据示意
  • 查{找}数据
  • 插入数据
  • 查{找}最大值与最小值
  • 查{找}前驱节点和后继节点
  • 查{找}向下取整和向上取整
  • 删除操作

数据示意

完全等同于二叉树〖的〗链式存储法,我们界说一个节点类Node来示意 二叉查{找}树[上〖的〗一个节点,每个节点含有一个『键』,一个值,一个左链接,一个有链接。其中『键』和值是为了储存和查{找},一般来说,给定『键』,我们能够快速〖的〗{找}到它所对应〖的〗值。

private class Node{
    private int key;//『键』
    private String value;//值,我这里把数据设为String,为了和key区离开
    private Node left,right;//指向子树〖的〗链接
    public Node(int key,String value);//Java中〖的〗组织函数
}

查{找}数据

查{找}操作接受一个『键』值(key),返回该『键』值对应〖的〗值(value),若是{找}不到就返回 null
大致思绪是:若是树是空〖的〗,则查{找}未掷中,返回null;若是被查{找}〖的〗『键』和根节点〖的〗『键』相等,查{找}掷中,返回根节点对应〖的〗值;若是被查{找}〖的〗『键』较小,则在左子树中继续查{找};若是被查{找}〖的〗『键』较大,则在右子树中继续查{找}。我们用递归来实现这个操作,详细〖的〗代码如下:

public String find(int key){
    return find(root,key);
}
private String find(Node x,int key){
    //在以x为根结点〖的〗子树中查{找}并返回『键』key所对应〖的〗值
    //若是{找}不到,就返回null
    if(x==null) return null;
    if(key<x.key) return find(x.left,key);
    else if(key>x.left) return find(x.right,key);
    else return x.value;
}
// 注重这里用了两个方式,一个私有一个公然,私有〖的〗用来递归,公然〖的〗对外开放

递归代码〖的〗实现是很简练〖的〗,对照容易明白,我们来看你一下动图:

好比我们想查{找}32,首先,32小于41,以是对41〖的〗左子树举行查{找},32大于20,再对20〖的〗右子树举行查{找},紧接着对29〖的〗右子树查{找},正好掷中32,若是查{找}不到〖的〗话就返回null

插入数据

我们首先判断根节点是不是空节点,若是是空节点,就直接建立一个新〖的〗Node工具作为根节点即可;
若是根节点非空,就通过while循环以及p.keykey〖的〗巨细对照不停向下寻{找}。循环竣事时一定会{找}到 一个空位置,这时我们就建立一个新〖的〗Node工具并把它接在这里。固然另有一种情形,若是p.key==key,就更新这个『键』『键』对应〖的〗值,竣事。

来一起看下面这个例子,向树中插入31,可以连系着实现方式一(非递归)明白一下:


实现方式一(非递归实现):

public void insert(int key,String value) {
    //若是根节点为空节点
    if (root == null) {
        root = new Node(key,value);
        return;
    }

    //根节点不是空节点
    Node p = root;
    while (p != null) {
      if (key > p.key) { //向右走
        if (p.right == null) {
          p.right = new Node(key,value);
          return;
        }
        p = p.right;
       } 
       else if { // key < p.key,向左走
         if (p.left == null) {
           p.left = new Node(key,value);
           return;
         }
        p = p.left;
      }
      else p.value=value;//若是原来树中就含有value『键』,则更新它〖的〗值
    }
  }

实现方式二(递归实现):

public void insert(int key,String value){
    root=insert(root,key,value);
}
private Node insert(Node x,int key,String value){
    //若是key存在于以x为根节点〖的〗子树中则更新它〖的〗值;
    //若是不在就建立新节点插入到合适〖的〗位置;
    if(x==null) return new Node(key,value);
    if(key<x.key) x.left=insert(x.left,key,value);
    else if(key>x.key) x.right=insert(x.right,key,value);
    else x.value=value;
    return x;
}

这个递归〖的〗代码只管很简练,但却不是那么容易明白。
我先说一下写递归算法需要注重〖的〗问题:

  • 1.一个问题〖的〗解可以剖析为几个子问题〖的〗解作甚子问题
  • 这个问题与剖析之后〖的〗子问题,除了数据规模差别,求解思绪完全一样
  • 3.存在递归终止条件

PS:关『键』在于写出递推公式{找}到终止条件

在这里,递推公式就是凭据条件判断。然后将根节点对应〖的〗树转化为规模小一点〖的〗左子树或右子树,终止条件就是遇到空链接

若是着实绕脑子,你只需要明白第一种非递归〖的〗方式就行了:)。

查{找}最大值和最小值

这个操作应该是最简朴〖的〗了。凭据 二叉查{找}树[〖的〗界说,最小值就是最左边〖的〗元素,直接从根节点一直向左查{找}即可。它也《有两种》实现方式,详细〖的〗代码如下:

实现一(递归实现)

public int min(){
    return min(root).key;
}
private Node min(Node x){
    // 返回以x为根节点〖的〗树〖的〗最小节点
    if(x.left==null) return x;
    return min(x.left);
}

实现二(非递归实现)

public int min()
    if(root==null) return -1; //示意不存在最小值
    Node x=root;
    //沿着左子树一直深入搜索下去,直到遇到左子树为空〖的〗节点,此时当前节 点为最小值
    while(x.left !=null)
        x = x.left
    return x.key;
}

以下是动图演示:


查{找}最大元素〖的〗原理类似,只需把left换成right即可,在这里就不再多说了,就当给你留〖的〗一个作业了:)。

查{找}前驱节点和后继节点

前驱节点指〖的〗是小于该『键』〖的〗最大『键』,后继节点指〖的〗是大于该『键』〖的〗最小『键』。你可以连系中序遍历明白,通过中序遍历,在获得〖的〗序列中位于该点左侧〖的〗就是前驱节点,右侧〖的〗就是后驱节点。

举个例子,如图所示:

我们首先先容以下前驱节点〖的〗性子:

1.若一个节点有左子树,那么该节点〖的〗前驱节点是其左子树中最大〖的〗节点(也就是左子树中最右边〖的〗谁人节点),示例如下:

2.若一个节点没有左子树,那么判断该节点和其父节点〖的〗关系

  • 2.1 若该节点是其父节点〖的〗右子节点,那么该节点〖的〗前驱结点即为其父节点。 示例如下:

  • 2.2 若该节点是其父节点〖的〗左子节点,那么需要沿着其父亲节点一直向树〖的〗顶端寻{找},直到{找}到一个节点P,P节点是其父节点Q〖的〗右子节点,那么Q就是该节点〖的〗后继节点,示例如下:

以上就是寻{找}〖的〗思绪,不外实际上我们另有一步操作,就是{找}到这个给定〖的〗节点,在这个历程中,我们同时纪录最近〖的〗一个向右走〖的〗节点first_parent。详细〖的〗代码如下(‘已测试’):

    public int get_prenode(int key)
    {
        if (root==null)
            return -1;//-1示意{找}不到给定〖的〗节点
        if (root.key==key)
            return -1;
        Node p = root;
        Node pp = null;
        Node  first_parent=null;
        while (p != null) {
            if (key>p.key) {
                pp = p;
                first_parent=p;
                p = p.right;

            } else if (key<p.key) {
                pp = p; 
                p = p.left;
            } else {

                break;
            }
        }
        if(p==null) return -1;
        else if(p.left!=null) return max(p.left).key;//对应了第1种情形,若是左子树不为空,则前驱一定是左子树〖的〗最大值,即小于p〖的〗最大值(左子树〖的〗值都小于p节点)
        //以下是左子树为空〖的〗情形2.1
        else if(pp.right==p) return pp.key;
        //以下是左子树为空〖的〗情形2.2
        else if(pp.left==p) return first_parent.key;
        return -1;
    }

向上取整和向下取整

向上取整是指大于即是该『键』〖的〗最小『键』,向下取整是指小于即是该『键』〖的〗最小值

向下取整与前驱后继节点〖的〗区别在于查{找}前驱后继节点对应〖的〗参数是树中〖的〗某一个节点『键』,而向下取整则允许接受随便〖的〗『键』作为参数,另一方面,向下取整可以包罗即是自己〖的〗『键』,是小于即是

关于向上取整与向下取整这两个操作,我只在算法(第四版)上面见到过,在其他〖的〗相关文章中没有遇到,不外我感受咱们可以体会一下它〖的〗头脑,究竟我感受这个操作也蛮主要〖的〗。

我们拿上图中查{找}19前驱节点为例说明一下流程:首先,在以41为根节点〖的〗树中查询,由于19<41,在41〖的〗左子树查询,即在以20为根节点〖的〗树中查询。接着由于19<20,继续向左,在以11为根结点〖的〗树中查询。集中注重力,由于19>11,以是11『有可能是』19〖的〗前驱节点,然则条件是11〖的〗右子树中没有比19小〖的〗元素。也就是说我们应该先在11〖的〗右子树中寻{找},然后判断寻{找}〖的〗情形(掷中或未掷中),若是掷中,那就自动返回效果了,若是没有掷中,则说明11就是19〖的〗前驱节点!,这其中查{找}〖的〗历程是一个递归〖的〗历程!希望你仔细体会:)

我只能说到这里了,欠好明白:(。详细实现如下:

public int floor(int key){
    Node x=floor(root,key);
    if(x==null) return -1;//未查{找}到
    return x.key;
}
private Node floor(Node x,int key){
    if(x==null) return null;//示意在以x为根节点〖的〗树中没有查{找}到
    if(key=x.key) return x;//掷中,且恰幸亏根节点x
    if(key<x.key) return floor(x.left,key);//在x〖的〗左子树中查询,根节点有x变为x〖的〗子节点,数据规模减小
    //往下走说明key>x.key,这个时刻要去x〖的〗右子树去寻{找}
    Node  t=floor(x.right,key);//在右子树中寻{找}
    if(t!=null) return t;//在右子树中{找}到了
    else return x;//在右子树中没有{找}到,那就说明x节点就是要求〖的〗前驱节点
}

向上取整〖的〗代码类似,我这里就不详细说了,你可以自己实现一下。

删除操作

二叉树〖的〗删除操作就相对对照庞大了。希望你打起十二分〖的〗精神!删除一个结点只会对一颗 二叉查{找}树[〖的〗局部发生一定〖的〗影响,以是,我们〖的〗义务就是恢复删除这个结点所带来〖的〗影响。

删除操作也有递归算法,不外我很迷,而且我见许多地方也不是用递归实现〖的〗,以是这里就不再先容了,感兴趣〖的〗话可以看一下算法(第四版),上面有详细〖的〗先容。好了,不烦琐了,咱们继续~

针看待删除结点〖的〗子节点个数〖的〗差别,我们将它分为三种情形加以处置。

1.若是要删除〖的〗结点没有子节点,此时〖的〗操作时十分容易〖的〗,我们只需要将父节点中指向该节点〖的〗链接设置为null就可以了。请看下图,我们〖的〗义务是删除结点27,{找}到这个节点后直接抹去就 OK 了。

2.若是要删除〖的〗节点只有一个子节点(只有左子节点或只有右子节点),这种情形也不庞大。我们只需要更新父节点中〖的〗指向待删除结点〖的〗链接即可,让它指向待删除结点〖的〗子节点即可。请看下图,我们〖的〗目〖的〗是删除节点50:

3.若是要删除〖的〗节点有两个子节点,这时就变得庞大了。你听我仔细形貌以下这个历程:我们需要{找}到这个节点〖的〗右子树上〖的〗最小结点【记为H】(由于它没有左子节点),把【H】替换到我们设计删除〖的〗节点上;然后,再删除这个最小〖的〗节点【H】(由于它没有左子节点,以是可以转化成之前〖的〗两种情形之一),而且,你会发现, 二叉查{找}树[〖的〗性子被完善〖的〗保留了下来,惊不惊喜!

接下来请看下面这三个例子,它们划分能够转化为情形一和情形二:

第一幅图,想要删除节点20,它〖的〗右子树〖的〗最小节点【H】没有子节点

第二幅图,想要删除节点20,它〖的〗右子树〖的〗最小节点【H】存在右节点

注重:【H】不能能有左节点,由于它是最小〖的〗

详细〖的〗代码如下:

    public void delete(int key){
        //若是{找}到『键』为key〖的〗结点,就将它删除,{找}不到不做处置
        Node p=root;//p指向需要删除〖的〗结点,这里初始化为根节点
        Node pp=null;//pp纪录〖的〗是p〖的〗父节点
        
        //通过while循环查{找}Key结点
        while(p!=null&&p.key!=Key){
            pp=p;
            if(Key>p.Key) p=p.right;
            else p=p.left;
        }
        if(p==null) return;//没有{找}到

        //情形一:要删除〖的〗结点有两个子结点
        if(p.left!=null&&p.right!=null){
            //查{找}右子树〖的〗最小结点
            Node minP=p.right;//minP是右子树〖的〗最小结点
            Node minPP=p;//minPP示意minP〖的〗父结点
            while(minP.left!=null){
                minPP=minP;
                minP=minP.left;
            }
            p.Key=minP.Key;p.val=minP.val;//替换p(将被删除〖的〗结点)〖的〗『键』和值
            
            //转化,以下问题只需要将minP删除即可
            //由于minP作为右子树最小〖的〗结点,一定没有左子结点,可以转化为情形二处置
            p=minP;//使p指向右子树〖的〗最小结点
            pp=minPP;//使被删除结点〖的〗父结点指向右子树最小结点〖的〗父结点
            
        }

        //情形二:待删除结点是叶子结点(即没有子结点)或者仅有一个子结点

        Node child;//p〖的〗子结点
        if(p.left!=null) child=p.left;
        else if(p.right!=null) child=p.right;
        else child=null;

        //执行删除操作
        if(pp==null) root=child;//删除〖的〗是根结点
        else if(pp.left==p) pp.left=child;
        else pp.right=child;
    }

可以再凭据下面这幅图明白一下:)

理论剖析

我们前面用了那么大〖的〗气力来解说 二叉查{找}树[,那么它〖的〗性能怎么样呢?

着实,对于 二叉查{找}树[来说,不管是插入、删除照样查{找}操作,时间庞大度都和树〖的〗高度成正比,也就是O(H),由于每次操作都对应了一条从根节点向下〖的〗一条路径。而对于树〖的〗高度,却很可能因树〖的〗形状〖的〗差别而差别。

理想情形下, 二叉查{找}树[是一颗完全二叉树,每层〖的〗节点依次为 1、2、4、8、16…………,不难发现,树〖的〗高度为log(N),以是时间庞大度为 O(logN),这是一个相当高效〖的〗算法了。下面是一张表格,对常见〖的〗符号表〖的〗耗时成本做了一个简朴〖的〗对比。

据此可见 二叉查{找}树[〖的〗性能,它能够在O(logN)〖的〗时间庞大度内完成查{找}和插入操作,我们花这么大气力学习它是值得〖的〗!

然则,你有没有注重到,它〖的〗最坏情形依旧是O(logN)。 二叉查{找}树[在一定条件下可能会退化成链表,就像下图所示,这明显就是一个弯曲〖的〗链表!

我们希望{找}到一种数据结构,它能保证无论『键』〖的〗插入顺序若何,树〖的〗高度将总是总『键』数〖的〗对数,这就是平衡 二叉查{找}树[,更正确一点,我们在下一篇文章中先容红黑树!((预告一下))

好了,今天〖的〗内容就到这里了,希望你能够对 二叉查{找}树[有一个更深〖的〗明白,『另外』,记得一定要着手敲代码!咱们下期见红黑树。

码字绘图不易,若是以为本文对你有辅助,点赞支持一下作者!

『另外』,迎接人人关注我〖的〗民众号:小超说,之后我会继续创作算法与数据结构以及计算机基础知识〖的〗文章。也可以加我微信chao_hey,我们一起交流,一起提高!

,

Allbet客户端下载

欢迎进入Allbet客户端下载(Allbet Game):www.aLLbetgame.us,欧博官网是欧博集团〖的〗官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。

上一篇:太原房产信息网:【攻略】《联盟战棋》10.6-宇宙之始三套强势阵容大战星际

下一篇:上饶招聘网:亲人武肺病逝 家属坚持参加葬礼!一家17口全染疫

网友评论

  • 2020-08-29 00:02:23

    联博以太坊www.326681.com采用以太坊区块链高度哈希值作为统计数据,联博以太坊统计数据开源、公平、无任何作弊可能性。联博统计免费提供API接口,支持多语言接入。喜欢这样的

  • 2021-01-24 00:00:45

    最近十周星「“ 期[”」四( 《『第』》[2019149「“ 期[”」-2020025「“ 期[”」)没有泛起的红球:03 04 07 13 16 18;再继续啊

  • 2022-05-20 00:01:51

    在被主持人问及台湾问题引发冲突的可能性是否在增添时,达顿示意:“我以为它(台海冲突)不应该被忽视。” 不赞了,直接评论

  • 2023-01-18 00:33:10

    FORMER MIC deputy president S. Subramaniam died this evening after being in coma for more than 10 years. He was 78.看得心动