乐趣区

关于动画:看动画学算法之二叉搜索树BST

简介

树是相似于链表的数据结构,和链表的线性构造不同的是,树是具备层次结构的非线性的数据结构。

树是由很多个节点组成的,每个节点能够指向很多个节点。

如果一个树中的每个节点都只有 0,1,2 个子节点的话,这颗树就被称为二叉树,如果咱们对二叉树进行肯定的排序。

比方,对于二叉树中的每个节点,如果左子树节点的元素都小于根节点,而右子树的节点的元素都大于根节点,那么这样的树被叫做二叉搜寻树(Binary Search Tree)简称 BST。

明天咱们来探讨一下 BST 的性质和对 BST 的基本操作。

BST 的根本性质

刚刚咱们曾经讲过 BST 的基本特征了,当初咱们再来总结一下:

  1. BST 中任意节点的左子树肯定要比该节点的值要小
  2. BST 中任意节点的右子树肯定要比该节点的值要大
  3. BST 中任意节点的左右子树肯定要是一个 BST。

看一张图直观的感受一下 BST:

BST 的构建

怎么用代码来构建一个 BST 呢?

首先,BST 是由一个一个的节点 Node 组成的,Node 节点除了保留节点的数据之外,还须要指向左右两个子节点,这样咱们的 BST 齐全能够由 Node 连贯而成。

另外咱们还须要一个 root 节点来示意 BST 的根节点。

相应的代码如下:

public class BinarySearchTree {

    // 根节点
    Node root;

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

        public Node(int data) {
            this.data = data;
            left = right = null;
        }
    }
}

BST 的搜寻

先看下 BST 的搜寻,如果是下面的 BST,咱们想搜寻 32 这个节点应该是什么样的步骤呢?

先上图:

搜寻的根本步骤是:

  1. 从根节点 41 登程,比拟根节点和搜寻值的大小
  2. 如果搜寻值小于节点值,那么递归搜寻左侧树
  3. 如果搜寻值大于节点值,那么递归搜寻右侧树
  4. 如果节点匹配,则间接返回即可。

相应的 java 代码如下:

// 搜寻办法,默认从根节点搜寻
    public Node search(int data){return search(root,data);
    }

    // 递归搜寻节点
    private Node search(Node node, int data)
    {
        // 如果节点匹配,则返回节点
        if (node==null || node.data==data)
            return node;

        // 节点数据大于要搜寻的数据,则持续搜寻右边节点
        if (node.data > data)
            return search(node.left, data);

        // 如果节点数据小于要搜素的数据,则持续搜寻左边节点
        return search(node.right, data);
    }

BST 的插入

搜寻讲完了,咱们再讲 BST 的插入。

先看一个动画:

上的例子中,咱们向 BST 中插入两个节点 30 和 55。

插入的逻辑是这样的:

  1. 从根节点登程,比拟节点数据和要插入的数据
  2. 如果要插入的数据小于节点数据,则递归左子树插入
  3. 如果要插入的数据大于节点数据,则递归右子树插入
  4. 如果根节点为空,则插入以后数据作为根节点

相应的 java 代码如下:

// 插入新节点,从根节点开始插入
    public void insert(int data) {root = insert(root, data);
    }

    // 递归插入新节点
    private Node insert(Node node, int data) {

        // 如果节点为空,则创立新的节点
        if (node == null) {node = new Node(data);
            return node;
        }

        // 节点不为空,则进行比拟,从而递归进行左侧插入或者右侧插入
        if (data < node.data)
            node.left = insert(node.left, data);
        else if (data > node.data)
            node.right = insert(node.right, data);

        // 返回插入后的节点
        return node;
    }

BST 的删除

BST 的删除要比插入简单一点,因为插入总是插入到叶子节点,而删除可能删除的是非叶子节点。

咱们先看一个删除叶子节点的例子:

下面的例子中,咱们删除了 30 和 55 这两个节点。

能够看到,删除叶子节点是绝对简略的,找到之后删除即可。

咱们再来看一个比较复杂的例子,比方咱们要删除 65 这个节点:

能够看到须要找到 65 这个节点的右子树中最小的那个,替换掉 65 这个节点即可(当然也能够找到左子树中最大的那个)。

所以删除逻辑是这样的:

  1. 从根节点开始,比拟要删除节点和根节点的大小
  2. 如果要删除节点比根节点小,则递归删除左子树
  3. 如果要删除节点比根节点大,则递归删除右子树
  4. 如果节点匹配,又有两种状况
  5. 如果是单边节点,间接返回节点的另外一边
  6. 如果是双边节点,则先找出左边最小的值,作为根节点,而后将删除最小值过后的左边的节点,作为根节点的右节点

看下代码的实现:

 // 删除新节点,从根节点开始删除
    void delete(int data)
    {root = delete(root, data);
    }

    // 递归删除节点
    Node delete(Node node, int data)
    {
        // 如果节点为空,间接返回
        if (node == null)  return node;

        // 遍历左右两边的节点
        if (data < node.data)
            node.left = delete(node.left, data);
        else if (data > root.data)
            node.right = delete(node.right, data);

        // 如果节点匹配
        else
        {
            // 如果是单边节点,间接返回其上面的节点
            if (node.left == null)
                return node.right;
            else if (node.right == null)
                return node.left;

            // 如果是双边节点,则先找出左边最小的值,作为根节点,而后将删除最小值过后的左边的节点,作为根节点的右节点
            node.data = minValue(node.right);

            // 从左边删除最小的节点
            node.right = delete(node.right, node.data);
        }
        return node;
    }

这里咱们应用递归来实现的删除双边节点,大家能够考虑一下有没有其余的形式来删除呢?

本文的代码地址:

learn-algorithm

本文收录于 www.flydean.com

最艰深的解读,最粗浅的干货,最简洁的教程,泛滥你不晓得的小技巧等你来发现!

欢送关注我的公众号:「程序那些事」, 懂技术,更懂你!

退出移动版