动图图解二叉查找树的基本原理及其实现

二十二画程序员 等级 384 3 0

本文为系列专题【数据结构和算法:简单方法】的第 12 篇文章。

  1. 数据结构 | 顺序表
  2. 数据结构 | 链表
  3. 数据结构 | 栈
  4. 数据结构 | 队列
  5. 数据结构 | 双链表和循环链表
  6. 数据结构 | 二叉树的概念和原理
  7. 数据结构 | 二叉树的创建及遍历实现
  8. 数据结构 | 线索二叉树
  9. 数据结构 | 二叉堆
  10. 算法 | 顺序查找和二分查找

1. 是什么?

二叉查找树(Binary Search Tree)必须满足以下特点:

  • 若左子树不为空,则左子树的所有结点值皆小于根结点值
  • 若右子树不为空,则右子树的所有结点值皆大于根结点值
  • 左右子树也是二叉排序树

如下图,是一颗二叉查找树:

动图图解二叉查找树的基本原理及其实现

如果你对二叉查找树进行中序遍历,可以得到:5, 10, 12, 14, 16, 22, 30, 41, 54, 66。刚好是一个从小到大的有序序列,从这一点看,二叉查找树是可以进行排序的,所以这种树又叫二叉排序树(Binary Sort Tree)。

2. 查找

我们以上图为例,说明查找成功和失败两种过程。

先贴出代码:

int bst_search(BSTNode *root, int key, BSTNode **p, BSTNode *q)
{
    if (root == NULL) { // 空树,查找失败
        *p = q;
        return 0;
    } 
    if (key == root->data) { // 目标值相等根结点的值,查找成功
        *p = root;
        return 1;
    } else if (key < root->data) { // 目标值小于根结点的值,递归进入左子树
        return bst_search(root->left_child, key, p, root);
    } else { // 目标值大于根结点的值,递归进入右子树
        return bst_search(root->right_child, key, p, root);
    }
}

该方法中的三个指针的作用如下:

  • 指针 root 始终指向根结点, 标识了与目标值比较的结点;

  • 二级指针 p 指向最终查找的结果。如果查找成功,则指向“指向‘找到的结点’的指针”;如果查找失败,则指向“指向‘上次最后一个访问的结点’的指针”。

  • 指针 q 初始为空,以后始终指向上一个根结点。

下面是查找成功的过程动图:

动图图解二叉查找树的基本原理及其实现

下面是查找失败的过程动图:

动图图解二叉查找树的基本原理及其实现

请注意,以上过程成立的前提是:二叉树是一颗二叉排序树,必须满足二叉排序树的三个特点。

所以,二叉排序树的“排序”二字是为查找而服务的,上面两个动图足以说明,排序方便了查找,因为每次比较都在缩小范围。

二叉排序树和二分查找本质上做的事是一样的,比如以下几方面:

  1. 都是有序的。二分查找是全部有序,二叉排序数是局部有序。
  2. 都是将一组数划分成若干区域。二分查找通过三个标志位,二叉排序树通过树结构。
  3. 都是通过比较目标值和“区域分界点”的大小,从而确定目标值在哪个区域中。在二分查找中与中间标志位比较,在二叉查找树中与根结点比较。

我们在二分查找中说过:当涉及到频繁地插入和删除操作时,二分查找就不合适了。原因之一是二分查找要求元素是有序的(从小到大或从大到小),插入、删除破坏顺序后,需要额外精力维护有序状态。原因之二是二分查找使用顺序表实现,顺序表的插入和删除操作需要移动大量元素,也会影响效率。

但是二叉排序树是一个树,树结构通常使用链式结构来实现。链式结构对插入和删除操作很友好,也有利于我们维护二叉树的有序状态。

3. 创建和插入

现在给你一组没有顺序的数,比如 {16, 41, 14, 30, 10, 12, 54, 5, 22, 66},如何创建出一颗二叉查找树(BST)?这里为了方便起见,我们约定二叉查找树中没有重复值。

所谓创建,即向一个空树中不断插入结点,从而构成一个非空的二叉查找树。所以关键在于如何向一个二叉查找树中插入结点

所谓插入,即不断比较待插入结点和树中结点的值,使其插到合适的位置,怎么找到“合适的位置”呢?方法前面已经给出,即 bst_search

如果我们在二叉查找树中查找待插入值,一定会查找失败,即 bst_search 一定返回 0,所以bst_search 方法中的 p 指针最终指向的是最后一个访问的根结点,这个根结点的左孩子或右孩子即是“合适的位置”。

下面是创建(插入)的过程动图,和查找失败的过程动图非常相似:

动图图解二叉查找树的基本原理及其实现

插入一个结点的代码如下,可以看出,和 bst_search 的代码很相似:

int insert_bst_node(BSTNode **p_root, int key)
{
    BSTNode *p;
    if (bst_search(*p_root, key, &p, NULL) == 0) { // 没有查找到 key
        BSTNode *new = create_bst_node(key); // 创建新结点
        if (p == NULL) { // 空树,新节点直接作为根结点
            *p_root = new;
            return 1;
        }
        if (key < p->data) { // 插入值小于 p 的值,插入到左子树
            p->left_child = new;
            return 1;
        }
        if (key > p->data) {  // 插入值大于 p 的值,插入到右子树
            p->right_child = new;
            return 1;
        }
    }
    return 0; // 插入失败
}

那么,创建操作用一个 for 循环就搞定了:

void create_bst(BSTNode **root, int *array, int length)
{
    // 循环向空二叉查找树中插入若干结点
    for (int i = 0; i < length; i++) {
        insert_bst_node(root, array[i]);
    }
}

4. 删除

至此,我们已经介绍过好几种数据结构了,每种都涉及到增加(插入)和删除操作。就像加法和减法一样,插入和删除操作可以看作是一对“反操作”。这意味着,它们在原理、代码上有相似之处,能够做到触类旁通。但这不是绝对了,必须具体问题结合具体环境进行具体分析。比如删除二叉查找树中的某个结点,可能会破坏二叉查找树的结构,破坏其顺序,所以我们就需要分情况讨论。

【情况一】

待删除的结点没有孩子,即删除叶子结点。这是最简单的情况,因为删除叶子不会破坏剩下的结构,也不会破坏剩下的结点的顺序。

动图图解二叉查找树的基本原理及其实现

【情况二】

待删除的结点只有左子树或者右子树。这种情况也好做,将其左子树或右子树移动到删除结点处即可。由于二叉查找树使用了链式结构,所以删除操作的代价很小,只需要改变指针的指向。

动图图解二叉查找树的基本原理及其实现

【情况三】

待删除的结点既有左子树又有右子树。这种情况比较复杂,因为删除结点后,剩下了该结点的左子树和右子树“在风中飘荡”,一方面我们要维持树结构,另一方面我们要维持二叉查找树的结点大小顺序,所以删除结点会涉及到整个树结构的调整,即将“剩下的”左子树和右子树重新插到树结构中去。下面是过程:

动图图解二叉查找树的基本原理及其实现

从上图过程就可以看出,这有点太过打动干戈了。我们先是改变 结点 16 的右孩子指针,然后删除 结点 41,并将其右子树“摘出来”,然后把剩下的右子树中的所有结点重新插入到二叉查找树中。这样确实挺累人的。

不妨换一种思路:

动图图解二叉查找树的基本原理及其实现

我们将 32 赋值给结点 41,然后删除结点 32,同样能够达到删除结点 41 的效果。这种方式大大简化了操作,不需要移动甚至改变树的结构,代价较小。我称这种方式为——狸猫换太子。

那么为什么偏偏是把结点 32 赋值给待删除结点 41 呢?前面说过,二叉查找树的中序遍历是一个有序序列,这也是为什么叫它二叉排序树的原因。结点 32 刚好是结点 41 在中序遍历序列下的直接前驱结点,所以,将 32 赋值给结点 41 后,并不会影响二叉查找树的“左子树值小于根结点,右子树值大于根结点”的定义。

所以,如何找到待删除结点在中序序列下的直接前驱是关键。

在中序遍历序列下,根结点的直接前驱是其左子树中最右最下的那个结点,如上例中结点 41 的直接前驱是结点 32.

到此,如何写代码就很清晰了。

一、先递归地找到待删除结点:

/**
 * @description: 删除目标值结点
 * @param {BSTNode**} 二级指针,指向 指向树根结点的指针 的指针
 * @param {int} key 目标值
 * @return {int} 删除成功返回1;否则返回0
 */
int delete_bst_node(BSTNode **p_root, int key)
{
    if (*p_root == NULL) {
        return 0;
    }
    if (key == (*p_root)->data) { // 找到要删除的目标值 key
        rebuild_bst_after_delete(p_root);
    } else if (key < (*p_root)->data) { // 目标值小于根结点,递归进入左子树
        return delete_bst_node(&(*p_root)->left_child, key);
    } else { // 目标值大于右子树,递归进入右子树
        return delete_bst_node(&(*p_root)->right_child, key);
    }
}

可以看出,这段代码和删除操作的代码没有太大区别,本质仍是查找。

二、找到待删除结点后,将结点删除,然后调整以维持二叉查找树的结构:

/**
 * @description: 删除某个结点后重新调整二叉查找树
 * @param {BSTNode**} p_node 指向待删除结点的二级指针
 * @return {int} 成功返回1;失败返回0
 */
int rebuild_bst_after_delete(BSTNode **p_node)
{
    BSTNode *prev, *tmp;
    tmp = *p_node;
    if ((*p_node)->left_child == NULL) { // 左子树为空,重接右子树
        *p_node = (*p_node)->right_child;
        free(tmp);
        return 1;
    }
    if ((*p_node)->right_child == NULL) { // 右子树为空,重接左子树
        *p_node = (*p_node)->left_child;
        free(tmp);
        return 1;
    }
    // 左右子树均不为空
    if ((*p_node)->left_child != NULL && (*p_node)->right_child != NULL) {
        prev = (*p_node)->left_child;
        while (prev->right_child != NULL) { // 找到待删除结点的直接前驱
            tmp = prev;
            prev = prev->right_child;
        }
        (*p_node)->data = prev->data; // 赋值
        if (tmp != *p_node) { // 待删除结点有子孙结点
            tmp->right_child = prev->left_child;
        } else { // 待删除结点只有两个孩子结点,没有子孙结点
            tmp->left_child = prev->left_child;
        }
        free(prev);
        return 1;
    }
    return 0;
}

以上就是二叉查找树的基本原理及实现

完整代码请移步至 GitHub | Gitee 获取。

如有错误,还请指正。

如果觉得写的不错,可以点个赞和关注。后续会有更多数据结构和算法相关文章。 微信扫描下方二维码,一起学习更多计算机基础知识。

动图图解二叉查找树的基本原理及其实现

收藏
评论区

相关推荐

4.2 手写Java PriorityQueue 核心源码
上一节介绍了PriorityQueue的原理,先来简单的回顾一下 PriorityQueue 的原理 以最大堆为例来介绍 1. PriorityQueue是用一棵完全二叉树实现的。 2. 不但是棵完全二叉树,而且树中的每个根节点都比它的左右两个孩子节点元素大 3. PriorityQueue底层是用数组来保存这棵完全二叉树的。 如下图,是一棵最大堆。
前端学数据结构与算法:二叉树的四种遍历方式及其应用
前言 上一章我们从0到1的实现了一颗二叉搜索树,以及理解了二叉搜索树的特性与基本操作,这一章介绍关于二叉树的更多操作,也就是树的遍历,对树的每个节点进行访问。主要包括前序遍历、中序遍历、后序遍历、层序遍历,前面三种也叫深度优先遍历(DFS),最后的层序遍历也叫广度优先遍历(BFS),理解这四种遍历方式的不同,再遇到树相关的算法问题时,也就能更加游刃有余。这
JavaScript 中的二叉树以及二叉搜索树的实现及应用
接下来让我们一起来探讨js数据结构中的树。这里的树类比现实生活中的树,有树干,树枝,在程序中树是一种数据结构,对于存储需要快速查找的数据非有用,它是一种分层数据的抽象模型。一个树结构包含一系列存在父子关系的节点。每个节点都有一个父节点以及零个或多个子节点。如下所以为一个树结构:) (https://imghelloworld.osscnbe
彻底搞懂系列B-树、B+树、B-树、B*树
(https://blog.csdn.net/chai471793/article/details/99563704)平衡二叉树 概念 平衡二叉树是基于二分法的策略提高数据的查找速度的二叉树的数据结构; 特点 平衡二叉树是采用二分法思维把数据按规则组装成一个树形结构的数据,用这个树形结构的数据减少无关数据的检索,大大
算法笔记:B树
B树广泛应用于各种文件系统,文件系统中,数据都是按照数据块来进行读取操作。结合二叉树的优点和文件系统的特点,于是就有了B树: btree(https://imghelloworld.osscnbeijing.aliyuncs.com/imgs/ae3caa193bc4c55f0519114b15313721.png) B树当中每个节点存储
二叉树题集(持续更新中)
对于二叉搜索树,我们规定任一结点的左子树仅包含严格小于该结点的键值,而其右子树包含大于或等于该结点的键值。 1\. 求二叉搜索树最大深度输入格式:输入给出一行整数序列作为二叉搜索树的键值,数字间以空格分隔,输入0结束(0不计入该二叉树键值)。输入样例:8 6 8 5 10 9 11 0输出样例:4常规的求二叉搜索树深度的做法是递
天池比赛数据挖掘心电图模型调参
Task4 建模与调参 4.1 学习目标 学习机器学习模型的建模过程与调参流程 完成相应学习打卡任务 4.2 内容介绍 逻辑回归模型: 理解逻辑回归模型; 逻辑回归模型的应用; 逻辑回归的优缺点; 树模型: 理解树模型; 树模型的应用; 树模型的优缺点; 集成模型 基于bagging思想的集成
【Flutter实战】布局类组件简介
4.1 布局类组件简介布局类组件都会包含一个或多个子组件,不同的布局类组件对子组件排版(layout)方式不同。我们在前面说过Element树才是最终的绘制树,Element树是通过Widget树来创建的(通过Widget.createElement()),Widget其实就是Element的配置数据。在Flutter中,根据Widget是否
二叉树创建后,如何使用递归和栈遍历二叉树?
0. 前言前文主要介绍了树的相关概念和原理,本文主要内容为二叉树的创建及遍历的代码实现,其中包括递归遍历和栈遍历。 1. 二叉树的实现思路 1.0. 顺序存储——数组实现前面介绍了满二叉树和完全二叉树,我们对其进行了编号——从 0 到 n 的不中断顺序编号,而恰好,数组也有一个这样的编号 —— 数组下标,只要我们把二者联合起来,数组就能存储二叉树了。那么非满
js实现二叉树、二叉查找树
树是一种数据结构,该章节讨论二叉树(二叉树的每个节点的子节点不允许超过两个),二叉树中有又分为完全二叉树和不完全二叉树..... 不在本章节赘述相关概念,感兴趣可以去查阅《数据结构》。 你将会获得: 1.如何使用js实现二叉查找树。 2.学会前、中、后序遍历。 3.了解相关实现原理 阅读时长5min,可选择直接调试代码 特点    二叉查找树中序遍历后
用C语言的递归写个二叉搜索树(二叉排序树)
不会递归的程序员不是好程序员,虽然鄙人尚未毕业,是个无知的大学生。但这追去真理的上进心不可小量。二叉树的每一个节点,与其左右子树都可以组成一个二叉树,利用这思路,可以写个递归形式的二叉树。cinclude<stdio.hinclude<stdlib.htypedef struct treeNode int data; struct treeNode Left
动图图解二叉查找树的基本原理及其实现
本文为系列专题的第 12 篇文章。1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 1. 是什么?二叉查找树(Binary Search Tree)必须满足以下特点: 若左子树不为空,则左子树的所有结点值皆小于根结点值 若右子树不为空,则右子树的所有结点值皆大于根结点值 左右子树也是二叉排序树如下图,是一颗二叉查找树:如果你对二叉查找树进行中序
Vue - diff 算法
diff是什么?diff就是比较两棵树,render会生成两颗树,一棵新树newVnode,一棵旧树oldVnode,然后两棵树进行对比更新找差异就是diff,全称difference,在vue里面 diff 算法是通过patch函数来完成的,所以有的时候也叫patch算法⏳ diff 发生的时机diff发生在什么时候呢?当然我们可以说在数据更新的时候发生d
推荐程序员面试秘籍!2021年大厂Java岗面试必问
01 JAVA基础 1.1 java知识点 Hashmap 源码级掌握,扩容,红黑树,最小树化容量,hash冲突解决,有些面试官会提出发自灵魂的审问,比如为什么是红黑树,别的树不可以吗;为什么8的时候树化,4不可以吗,等等 concureentHashMap,段锁,如何分段,和hashmap在hash上的区别,性能,等等 HashTable ,同步锁,这块可
高级java面试题,附答案+考点
蚂蚁金服一面1. 两分钟的自我介绍2. 二叉搜索树和平衡二叉树有什么关系,强平衡二叉树(AVL 树)和弱平衡二叉树 (红黑树)有什么区别3. B 树和 B+树的区别,为什么 MySQL 要使用 B+树4. HashMap 如何解决 Hash 冲突5. epoll 和 poll 的区别,及其应用场景6. 简述线程池原理,FixedThreadPoo