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

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

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

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

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

靠山和必要性

靠山

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

目〖的〗

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

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

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

二叉树知识回首

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

二叉树〖的〗界说

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

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

二叉树〖的〗存储方式

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

我们把根节点储存在下标为i=1〖的〗位置，那么左子节点储存在2*i=2〖的〗位置，右子节点储存在下标为2*i+1=2〖的〗位置。依此类推，完成树〖的〗存储。借助下标运算，我们可以很轻松〖的〗从父节点跳转到左子节点和（右子节点或者从）随便一个子节点{找}到它〖的〗父节点。若是X〖的〗位置为i，则它〖的〗两个子节点〖的〗下标划分为2i和2i+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.key和key〖的〗巨细对照不停向下寻{找}。循环竣事时一定会{找}到 一个空位置，这时我们就建立一个新〖的〗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手机版下载等业务。