重温数据结构:二叉排序树的查找、插入、删除

我们知道,二分查找可以缩短查找的时间,但是有个要求就是 查找的数据必须是有序的。每次查找、操作时都要维护一个有序的数据集,于是有了二叉排序树这个概念。

上篇文章 我们介绍了 二叉树 的概念,二叉树有左右子树之分,想必在区分左右子树时有一定的规则。

现在我们来介绍二叉树的一种特殊形式 — 二叉排序树,了解它的区分策略及常用操作。

什么是二叉排序树 Binary Sort Tree, BST

二叉排序树,又称二叉查找树、二叉搜索树、B树。

二叉排序树是具有下列性质的二叉树:

  • 若左子树不空,则左子树上所有结点的值均小于它的根结点的值;
  • 若右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值;
  • 左、右子树也分别为二叉排序树。

也就是说,二叉排序树中,左子树都比节点小,右子树都比节点大,递归定义。

根据二叉排序树这个特点我们可以知道,二叉排序树的中序遍历一定是从小到大的,比如上图,中序遍历结果是:

1 3 4 6 7 8 10 13 14

二叉排序树的关键操作

1.查找

根据二叉排序树的定义,我们可以知道在查找某个元素时:

  • 先比较它与根节点,相等就返回;或者根节点为空,说明树为空,也返回;
  • 如果它比根节点小,就从根的左子树里进行递归查找;
  • 如果它比根节点大,就从根的右子树里进行递归查找。

可以看到,这就是一个 二分查找

代码实现:

public class BinarySearchTree {
    private BinaryTreeNode mRoot;   //根节点

    public BinarySearchTree(BinaryTreeNode root) {
        mRoot = root;
    }

    /**
     * 在整个树中查找某个数据
     *
     * @param data
     * @return
     */
    public BinaryTreeNode search(int data) {
        return search(mRoot, data);
    }

    /**
     * 在指定二叉排序树中查找数据
     *
     * @param node
     * @param data
     * @return
     */
    public BinaryTreeNode search(BinaryTreeNode node, int data) {
        if (node == null || node.getData() == data) {    //节点为空或者相等,直接返回该节点
            return node;
        }
        if (data < node.getData()) {    //比节点小,就从左子树里递归查找
            return search(node.getLeftChild(), data);
        } else {        //否则从右子树
            return search(node.getRightChild(), data);
        }
    }
}

可以看到,在二叉排序树中查找是十分简单的,但是这依赖于每次插入、删除元素时对整个 排序树 结构的维护。

2.插入

二叉树中的插入,主要分两步:查找、插入:

  • 先查找有没有整个元素,有的话就不用插入了,直接返回;
  • 没有就插入到之前查到(对比)好的合适的位置。

插入时除了设置数据,还需要跟父节点绑定,让父节点意识到有你这个孩子:比父节点小的就是左孩子,大的就是右孩子。

代码实现:

/**
 * 插入到整个树中
 *
 * @param data
 */
public void insert(int data) {
    if (mRoot == null) {     //如果当前是空树,新建一个
        mRoot = new BinaryTreeNode();
        mRoot.setData(data);
        return;
    }

    searchAndInsert(null, mRoot, data);     //根节点的父亲为 null

}

/**
 * 两步走:查找、插入
 *
 * @param parent 要绑定的父节点
 * @param node   当前比较节点
 * @param data   数据
 */
private BinaryTreeNode searchAndInsert(BinaryTreeNode parent, BinaryTreeNode node, int data) {
    if (node == null) {  //当前比较节点为 空,说明之前没有这个数据,直接新建、插入
        node = new BinaryTreeNode();
        node.setData(data);
        if (parent != null) {    //父节点不为空,绑定关系
            if (data < parent.getData()) {
                parent.setLeftChild(node);
            } else {
                parent.setRightChild(node);
            }
        }
        return node;
    }
    //对比的节点不为空
    if (node.getData() == data) {    //已经有了,不用插入了
        return node;
    } else if (data < node.getData()) {   //比节点小,从左子树里查找、插入
        return searchAndInsert(node, node.getLeftChild(), data);
    } else {
        return searchAndInsert(node, node.getRightChild(), data);
    }
}

3.删除 *

插入操作和查找比较类似,而删除则相对复杂一点,需要根据删除节点的情况分类来对待:

  • 如果要删除的节点正好是叶子节点,直接删除就 Ok 了;
  • 如果要删除的节点还有子节点,就需要建立父节点和子节点的关系:
    • 如果只有左孩子或者右孩子,直接把这个孩子上移放到要删除的位置就好了;
    • 如果有两个孩子,就需要选一个合适的孩子节点作为新的根节点,该节点称为 继承节点

新节点要求要比所有左子树大,比所有右子树小,怎么选择呢?

**要比所有左子树的值大、右子树小,就从右子树里找最小的好了; 同样也可以从左子树里找最大的。**

两种选择方法都可以,本文选用右子树里最小的节点,也就是右子树中最左边的节点。

代码实现:

/**
 * 在整个树中 查找指定数据节点的父亲节点
 *
 * @param data
 * @return
 */
public BinaryTreeNode searchParent(int data) {
    return searchParent(null, mRoot, data);
}

/**
 * 在指定节点下 查找指定数据节点的父亲节点
 *
 * @param parent 当前比较节点的父节点
 * @param node   当前比较的节点
 * @param data   查找的数据
 * @return
 */
public BinaryTreeNode searchParent(BinaryTreeNode parent, BinaryTreeNode node, int data) {
    if (node == null) { //比较的节点为空返回空
        return null;
    }
    if (node.getData() == data) {    //找到了目标节点,返回父节点
        return parent;
    } else if (data < node.getData()) {   //数据比当前节点小,左子树中递归查找
        return searchParent(node, node.getLeftChild(), data);
    } else {
        return searchParent(node, node.getRightChild(), data);
    }
}

/**
 * 删除指定数据的节点
 *
 * @param data
 */
public void delete(int data) {
    if (mRoot == null || mRoot.getData() == data) {  //根节点为空或者要删除的就是根节点,直接删掉
        mRoot = null;
        return;
    }
    //在删除之前需要找到它的父亲
    BinaryTreeNode parent = searchParent(data);
    if (parent == null) {        //如果父节点为空,说明这个树是空树,没法删
        return;
    }

    //接下来该找要删除的节点了
    BinaryTreeNode deleteNode = search(parent, data);
    if (deleteNode == null) {    //树中找不到要删除的节点
        return;
    }
    //删除节点有 4 种情况
    //1.左右子树都为空,说明是叶子节点,直接删除
    if (deleteNode.getLeftChild() == null && deleteNode.getRightChild() == null) {
        //删除节点
        deleteNode = null;
        //重置父节点的孩子状态,告诉他你以后没有这个儿子了
        if (parent.getLeftChild() != null && parent.getLeftChild().getData() == data) {
            parent.setLeftChild(null);
        } else {
            parent.setRightChild(null);
        }
        return;
    } else if (deleteNode.getLeftChild() != null && deleteNode.getRightChild() == null) {
        //2.要删除的节点只有左子树,左子树要继承位置
        if (parent.getLeftChild() != null && parent.getLeftChild().getData() == data) {
            parent.setLeftChild(deleteNode.getLeftChild());
        } else {
            parent.setRightChild(deleteNode.getLeftChild());
        }
        deleteNode = null;
        return;
    } else if (deleteNode.getRightChild() != null && deleteNode.getRightChild() == null) {
        //3.要删除的节点只有右子树,右子树要继承位置
        if (parent.getLeftChild() != null && parent.getLeftChild().getData() == data) {
            parent.setLeftChild(deleteNode.getRightChild());
        } else {
            parent.setRightChild(deleteNode.getRightChild());
        }

        deleteNode = null;
    } else {
        //4.要删除的节点儿女双全,既有左子树又有右子树,需要选一个合适的节点继承,这里使用右子树中最左节点
        BinaryTreeNode copyOfDeleteNode = deleteNode;   //要删除节点的副本,指向继承节点的父节点
        BinaryTreeNode heresNode = deleteNode.getRightChild(); //要继承位置的节点,初始为要删除节点的右子树的树根
        //右子树没有左孩子了,他就是最小的,直接上位
        if (heresNode.getLeftChild() == null) {
            //上位后,兄弟变成了孩子
            heresNode.setLeftChild(deleteNode.getLeftChild());
        } else {
            //右子树有左孩子,循环找到最左的,即最小的
            while (heresNode.getLeftChild() != null) {
                copyOfDeleteNode = heresNode;       //copyOfDeleteNode 指向继承节点的父节点
                heresNode = heresNode.getLeftChild();
            }
            //找到了继承节点,继承节点的右子树(如果有的话)要上移一位
            copyOfDeleteNode.setLeftChild(heresNode.getRightChild());
            //继承节点先继承家业,把自己的左右孩子变成要删除节点的孩子
            heresNode.setLeftChild(deleteNode.getLeftChild());
            heresNode.setRightChild(deleteNode.getRightChild());
        }
        //最后就是确认位置,让要删除节点的父节点认识新儿子
        if (parent.getLeftChild() != null && parent.getLeftChild().getData() == data) {
            parent.setLeftChild(heresNode);
        } else {
            parent.setRightChild(heresNode);
        }
    }
}

运行代码测试

可以看到,二叉排序树的查找、添加较简单,删除逻辑比较多,我们以下图为例:

测试代码:

@Test
public void delete() throws Exception {
    //乱序插入到二叉排序树中
    BinarySearchTree binarySearchTree = new BinarySearchTree(null);
    binarySearchTree.insert(8);
    binarySearchTree.insert(3);
    binarySearchTree.insert(1);
    binarySearchTree.insert(6);
    binarySearchTree.insert(4);
    binarySearchTree.insert(7);
    binarySearchTree.insert(10);
    binarySearchTree.insert(13);
    binarySearchTree.insert(14);

    //中序遍历
    binarySearchTree.iterateMediumOrder(binarySearchTree.getRoot());
    System.out.println("");
    //查找某个数据
    System.out.println(binarySearchTree.search(10).getData());
    //删除某个数据对应的元素
    binarySearchTree.delete(6);
    //中序遍历删除后的二叉排序树
    binarySearchTree.iterateMediumOrder(binarySearchTree.getRoot());
}

运行结果:

一道面试题

输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点,只调整指针的指向。 比如将二元查找树: 10 / \ 6 14 / \ /  \ 4 8 12   16 转换成双向链表后为:4=6=8=10=12=14=16 解析: 这题据说是微软的面试题,乍看起来貌似很麻烦,又是二叉排序树又是双向链表的,其实考察的都是很基础的东西,明眼人一看就发现只要将这棵树中序遍历后就是将二叉树节点排序(不然它为啥叫二叉排序树呢…),那么我们只要将这棵树中序遍历,遍历到一个节点就将该节点的左指针指向上一个遍历的节点,并将上一个遍历的节点的右指针指向现在正在遍历的节点,那么当我们遍历完整棵树后,我们的双向链表也改好啦!这样既不用添加多余节点,也不用添加多余的指针变量。 该题转自:http://blog.renren.com/share/249404913/6219142584 你可以写下代码试试。

总结

  二叉排序树的性能取决于二叉树的层数:

  • 最好的情况是 O(logn),存在于完全二叉排序树情况下,其访问性能近似于折半查找;
  • 最差时候会是 O(n),比如插入的元素是有序的,生成的二叉排序树就是一个链表,这种情况下,需要遍历全部元素才行(见下图 b)。

Thanks

《轻松学算法》

http://blog.csdn.net/v_JULY_v/article/details/6530142/ http://blog.csdn.net/v_july_v/article/details/6543438

http://baike.baidu.com/link?url=gGnlVdkdSIFg9RINW2I9PC-H26Vonbo4yOH0wiCgGzBoVb540EBqF2-5ho1Sx2ImSckufU8WeiFjTRnL0Mu648kVIJHhaIfiOx5CKgKtDPrNhiAJ5lQ0CFhWoe-CWRAf-sIQJZHZdAysqGIgHfsga_

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏日常分享

Java 通过先序中序序列生成二叉树

  二叉树的前序以及后续序列,以空格间隔每个元素,重构二叉树,最后输出二叉树的三种遍历方式的序列以验证。

761
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题23从上往下打印二叉树

本题的详细分析过程均在代码注释中: import java.util.Queue; import java.util.concurrent.LinkedBloc...

2788
来自专栏用户画像

4.5.1 二叉排序树

二叉排序树的查找时从根结点开始,沿着某一分支逐层向下进行比较比较的过程。若二叉排序树非空,将给定值与根结点的关键字比较,若相等,则查找成功;若不等,则当根结点的...

803
来自专栏青蛙要fly的专栏

Android技能树 — 树基础知识小结(一)

现在安卓面试,对于数据结构的问题也越来越多了,也经常看到别人发的面试题都是问什么红黑树,二叉树查找等,所以我们虽然不会马上就会各种难的面试题,但起码树的基础知识...

663
来自专栏琯琯博客

PHP二叉树(二):二叉搜索树

2474
来自专栏开发 & 算法杂谈

前序遍历中序遍历求后序遍历-数组篇

如果已知前序遍历和中序遍历,那么肯定能够求出后序遍历。正常的思路就是,根据前序遍历和中序遍历,我们把二叉树的结构给描述出来,然后再使用后序遍历。

461
来自专栏nnngu

算法08 五大查找之:二叉排序树(BSTree)

上一篇总结了索引查找,这一篇要总结的是二叉排序树(Binary Sort Tree),又称为二叉查找树(Binary Search Tree) ,即BSTree...

3416
来自专栏我是业余自学C/C++的

二叉树 原

对高度为h的满二叉树的元素,从第一层到最后一层,在每一次中从左至右,顺序编号,从1到2^h-1.假设从满二叉树中删除k个其编号为2^h-i元素,1<=i<=k<...

722
来自专栏Java3y

二叉树就这么简单

一、二叉树就是这么简单 本文撇开一些非常苦涩、难以理解的概念来讲讲二叉树,仅入门观看(或复习)…. 首先,我们来讲讲什么是树: 树是一种非线性的数据结构,相对于...

3858
来自专栏用户画像

6.3.1 B树及其基本操作

B树,又称多路平衡查找树,B树中所有节点的孩子结点数的最大值成为B树的阶,通常用m表示。一棵m阶B树或为空树,或为满足如下特性的m叉树:

621

扫码关注云+社区