二分搜索树_Java

一、概念及其介绍

二分搜索树（Binary Search Tree），也称为二叉查找树、二叉搜索树、有序二叉树或排序二叉树。满足以下几个条件：

若它的左子树不为空，左子树上所有节点的值都小于它的根节点。
若它的右子树不为空，右子树上所有的节点的值都大于它的根节点。

它的左、右子树也都是二分搜索树。

如下图所示：

二、适用说明

二分搜索树有着高效的插入、删除、查询操作。

平均时间的时间复杂度为 O(log n)，最差情况为 O(n)。二分搜索树与堆不同，不一定是完全二叉树，底层不容易直接用数组表示故采用链表来实现二分搜索树。

	查找元素	插入元素	删除元素
普通数组	O(n)	O(n)	O(n)
顺序数组	O(logn)	O(n)	O(n)
二分搜索树	O(logn)	O(logn)	O(logn)

下面先介绍数组形式的二分查找法作为思想的借鉴，后面继续介绍二分搜索树的查找方式。

三、二分查找法过程图示

二分查找法的思想在 1946 年提出，查找问题是计算机中非常重要的基础问题，对于有序数列，才能使用二分查找法。如果我们要查找一元素，先看数组中间的值V和所需查找数据的大小关系，分三种情况：

等于所要查找的数据，直接找到
若小于 V，在小于 V 部分分组继续查询
若大于 V，在大于 V 部分分组继续查询

using System;


public class BinarySearch where T : IComparable
{
    // 二分查找法,在有序数组arr中,查找target
    // 如果找到target,返回相应的索引index
    // 如果没有找到target,返回-1
    public static int Find(T[] arr, T target)
    {
        // 在arr[l...r]之中查找target
        int l = 0, r = arr.Length - 1;
        while (l <= r)
        {
            //int mid = (l + r)/2;
            // 防止极端情况下的整形溢出，使用下面的逻辑求出mid
            int mid = l + (r - l) / 2;

            if (arr[mid].CompareTo(target) == 0)
                return mid;

            if (arr[mid].CompareTo(target) > 0)
                r = mid - 1;
            else
                l = mid + 1;
        }

        return -1;
    }
}

二分搜索树节点的插入

首先定义一个二分搜索树

public class BST where TKey : IComparable
{
    // 树中的节点为私有的类, 外界不需要了解二分搜索树节点的具体实现
    public class Node
    {
        public TKey Key;
        public TValue Value;
        public Node Left, Right;

        public Node(TKey key, TValue value)
        {
            Key = key;
            Value = value;
            Left = Right = null;
        }
    }

    // 根节点
    private Node _root;

    // 树种的节点个数
    private int _count;

    // 构造函数, 默认构造一棵空二分搜索树
    public BST()
    {
        _root = null;
        _count = 0;
    }

    // 返回二分搜索树的节点个数
    public int Size => _count;

    // 返回二分搜索树是否为空
    public bool IsEmpty => _count == 0;
}

Node 表示节点，count 代表节点的数量。

以下实例向如下二分搜索树中插入元素 61 的步骤：

（1）需要插入的元素 61 比 42 大，比较 42 的右子树根节点。

（2）61 比 59 大，所以需要把 61 移动到 59 右子树相应位置，而此时为空，直接插入作为 59 的右子节点。

插入操作也是一个递归过程，分三种情况，等于、大于、小于。

    //向二分搜索树中插入一个新的(key, value)数据对
    public void Insert(TKey key, TValue value)
    {
        _root = Insert(_root, key, value);
    }

    //核心代码---开始
    // 向以node为根的二分搜索树中, 插入节点(key, value), 使用递归算法
    // 返回插入新节点后的二分搜索树的根
    private Node Insert(Node node, TKey key, TValue value)
    {
        if (node == null)
        {
            _count++;
            return new Node(key, value);
        }

        if (key.CompareTo(node.Key) == 0)
        {
            node.Value = value;
        }
        else if (key.CompareTo(node.Key) < 0)
        {
            node.Left = Insert(node.Left, key, value);
        }
        else // key > node->key
        {
            node.Right = Insert(node.Right, key, value);
        }

        return node;
    }
    //核心代码---结束

二分搜索树节点的查找

二分搜索树没有下标, 所以针对二分搜索树的查找操作, 这里定义一个 contain 方法, 判断二分搜索树是否包含某个元素, 返回一个布尔型变量, 这个查找的操作一样是一个递归的过程, 具体代码实现如下:

    // 查看以node为根的二分搜索树中是否包含键值为key的节点, 使用递归算法
    private bool Contains(Node node, TKey key)
    {
        if (node == null)
            return false;

        if (key.CompareTo(node.Key) == 0)
            return true;
        else if (key.CompareTo(node.Key) < 0)
            return Contains(node.Left, key);
        else // key > node->key
            return Contains(node.Right, key);
    }

以下实例在二分搜索树中寻找 43 元素

(1) 元素 43 比根节点 42 大，需要在右子节点继续比较。

(2) 元素 43 比 59 小，需要在左子节点继续比较。

(3) 元素 43 比 51 小，需要在左子节点继续比较。

(4) 查找 51 的左子节点 43，正好和相等，结束。

如果需要查找 key 对应的 value，代码如下所示:

    // 在以node为根的二分搜索树中查找key所对应的value, 递归算法
    // 若value不存在, 则返回NULL
    private TValue Search(Node node, TKey key)
    {
        if (node == null)
            return null;

        if (key.CompareTo(node.Key) == 0)
            return node.Value;
        else if (key.CompareTo(node.Key) < 0)
            return Search(node.Left, key);
        else // key > node->key
            return Search(node.Right, key);
    }

二分搜索树深度优先遍历

二分搜索树遍历分为两大类，深度优先遍历和层序遍历。

深度优先遍历分为三种：先序遍历（preorder tree walk）、中序遍历（inorder tree walk）、后序遍历（postorder tree walk），分别为：

前序遍历：先访问当前节点，再依次递归访问左右子树。
中序遍历：先递归访问左子树，再访问自身，再递归访问右子树。
后序遍历：先递归访问左右子树，再访问自身节点。

前序遍历结果图示：

对应代码示例：

    // 对以node为根的二叉搜索树进行前序遍历, 递归算法
    private void PreOrder(Node node)
    {
        if (node != null)
        {
            Debug.Log(node.Key);
            PreOrder(node.Left);
            PreOrder(node.Right);
        }
    }

中序遍历结果图示：

对应代码示例：

    // 对以node为根的二叉搜索树进行中序遍历, 递归算法
    private void InOrder(Node node)
    {
        if (node != null)
        {
            InOrder(node.Left);
            Debug.Log(node.Key);
            InOrder(node.Right);
        }
    }

后序遍历结果图示：

对应代码示例：

    // 对以node为根的二叉搜索树进行后序遍历, 递归算法
    private void PostOrder(Node node)
    {
        if (node != null)
        {
            PostOrder(node.Left);
            PostOrder(node.Right);
            Debug.Log(node.Key);
        }
    }

二分搜索树层序遍历

二分搜索树的层序遍历，即逐层进行遍历，即将每层的节点存在队列当中，然后进行出队（取出节点）和入队（存入下一层的节点）的操作，以此达到遍历的目的。

通过引入一个队列来支撑层序遍历：

如果根节点为空，无可遍历；
如果根节点不为空：
- 先将根节点入队；
- 只要队列不为空：
  - 出队队首节点，并遍历；
  - 如果队首节点有左孩子，将左孩子入队；
  - 如果队首节点有右孩子，将右孩子入队；

下面依次演示如下步骤：

（1）先取出根节点放入队列

（2）取出 29，左右孩子节点入队

（3）队首 17 出队，孩子节点 14、23 入队。

（4）31 出队，孩子节点 30 和 43 入队

（5）最后全部出队

核心代码示例：

    // 二分搜索树的层序遍历
    public void LevelOrder()
    {
        // 我们使用linkedList来作为我们的队列
        Queue q = new Queue();
        q.Enqueue(_root);
        while (q.Count > 0)
        {
            Node node = q.Dequeue();

            Debug.Log(node.Key);

            if (node.Left != null)
                q.Enqueue(node.Left);
            if (node.Right != null)
                q.Enqueue(node.Right);
        }
    }

二分搜索树节点删除

本小节介绍二分搜索树节点的删除之前，先介绍如何查找最小值和最大值，以及删除最小值和最大值。

以最小值为例（最大值同理）：

查找最小 key 值代码逻辑，往左子节点递归查找下去：

    // 返回以node为根的二分搜索树的最小键值所在的节点
    private Node Minimum(Node node)
    {
        if (node.Left == null)
            return node;

        return Minimum(node.Left);
    }

删除二分搜索树的最小 key 值，如果该节点没有右子树，那么直接删除，如果存在右子树，如图所示：

删除节点 22，存在右孩子，只需要将右子树 33 节点代替节点 22。

这个删除最小值用代码表示:

    // 删除掉以node为根的二分搜索树中的最小节点
    // 返回删除节点后新的二分搜索树的根
    private Node RemoveMin(Node node)
    {
        if (node.Left == null)
        {
            Node rightNode = node.Right;
            node.Right = null;
            _count--;
            return rightNode;
        }

        node.Left = RemoveMin(node.Left);
        return node;
    }

现在讨论二分搜索树节点删除分以下三种情况：

1、删除只有左孩子的节点，如下图节点 58。

删除掉元素 58，让左子树直接代替 58 的位置，整个二分搜索树的性质不变。

2、删除只有右孩子的节点，如下图节点 58。

删除掉元素 58，让右子树直接代替 58 的位置，整个二分搜索树的性质不变。

3、删除左右都有孩子的节点，如下图节点 58。

（1）找到右子树中的最小值，为节点 59

（2）节点 59 代替待删除节点 58

综合以上规律，删除以 node 为根的二分搜索树中键值为 key 的节点，核心代码示例：

    // 删除掉以node为根的二分搜索树中键值为key的节点, 递归算法
    // 返回删除节点后新的二分搜索树的根
    Node Remove(Node node, TKey key)
    {
        if (node == null)
            return null;

        if (key.CompareTo(node.Key) < 0)
        {
            node.Left = Remove(node.Left, key);
            return node;
        }
        else if (key.CompareTo(node.Key) > 0)
        {
            node.Right = Remove(node.Right, key);
            return node;
        }
        else
        {
            // key == node->key

            // 待删除节点左子树为空的情况
            if (node.Left == null)
            {
                Node rightNode = node.Right;
                node.Right = null;
                _count--;
                return rightNode;
            }

            // 待删除节点右子树为空的情况
            if (node.Right == null)
            {
                Node leftNode = node.Left;
                node.Left = null;
                _count--;
                return leftNode;
            }

            // 待删除节点左右子树均不为空的情况

            // 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
            // 用这个节点顶替待删除节点的位置
            Node successor = new Node(Minimum(node.Right));
            _count++;

            successor.Right = RemoveMin(node.Right);
            successor.Left = node.Left;

            node.Left = node.Right = null;
            _count--;

            return successor;
        }
    }

所有代码附上：

using System;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.Assertions;

public class BST where TKey : IComparable where TValue : class
{
    // 树中的节点为私有的类, 外界不需要了解二分搜索树节点的具体实现
    public class Node
    {
        public TKey Key;
        public TValue Value;
        public Node Left, Right;

        public Node(TKey key, TValue value)
        {
            Key = key;
            Value = value;
            Left = Right = null;
        }

        public Node(Node node)
        {
            Key = node.Key;
            Value = node.Value;
            Left = node.Left;
            Right = node.Right;
        }
    }

    // 根节点
    private Node _root;

    // 树种的节点个数
    private int _count;

    // 构造函数, 默认构造一棵空二分搜索树
    public BST()
    {
        _root = null;
        _count = 0;
    }

    // 返回二分搜索树的节点个数
    public int Size => _count;

    // 返回二分搜索树是否为空
    public bool IsEmpty => _count == 0;

    // 向二分搜索树中插入一个新的(key, value)数据对
    public void Insert(TKey key, TValue value)
    {
        _root = Insert(_root, key, value);
    }

    // 查看二分搜索树中是否存在键key
    public bool Contain(TKey key)
    {
        return Contains(_root, key);
    }

    // 在二分搜索树中搜索键key所对应的值。如果这个值不存在, 则返回null
    public TValue Search(TKey key)
    {
        return Search(_root, key);
    }

    // 二分搜索树的前序遍历
    public void PreOrder()
    {
        PreOrder(_root);
    }

    // 二分搜索树的中序遍历
    public void InOrder()
    {
        InOrder(_root);
    }

    // 二分搜索树的后序遍历
    public void PostOrder()
    {
        PostOrder(_root);
    }

    // 二分搜索树的层序遍历
    public void LevelOrder()
    {
        // 我们使用linkedList来作为我们的队列
        Queue q = new Queue();
        q.Enqueue(_root);
        while (q.Count > 0)
        {
            Node node = q.Dequeue();

            Debug.Log(node.Key);

            if (node.Left != null)
                q.Enqueue(node.Left);
            if (node.Right != null)
                q.Enqueue(node.Right);
        }
    }

    // 寻找二分搜索树的最小的键值
    public TKey Minimum()
    {
        Assert.IsTrue(_count > 0, $"Empty BST");
        Node minNode = Minimum(_root);
        return minNode.Key;
    }

    // 寻找二分搜索树的最大的键值
    public TKey Maximum()
    {
        Assert.IsTrue(_count > 0, $"Empty BST");
        Node maxNode = Maximum(_root);
        return maxNode.Key;
    }

    // 从二分搜索树中删除最小值所在节点
    public void RemoveMin()
    {
        if (_root != null)
            _root = RemoveMin(_root);
    }

    // 从二分搜索树中删除最大值所在节点
    public void RemoveMax()
    {
        if (_root != null)
            _root = RemoveMax(_root);
    }

    // 从二分搜索树中删除键值为key的节点
    public void Remove(TKey key)
    {
        _root = Remove(_root, key);
    }

    //********************
    //* 二分搜索树的辅助函数
    //********************

    //核心代码---开始
    // 向以node为根的二分搜索树中, 插入节点(key, value), 使用递归算法
    // 返回插入新节点后的二分搜索树的根
    private Node Insert(Node node, TKey key, TValue value)
    {
        if (node == null)
        {
            _count++;
            return new Node(key, value);
        }

        if (key.CompareTo(node.Key) == 0)
        {
            node.Value = value;
        }
        else if (key.CompareTo(node.Key) < 0)
        {
            node.Left = Insert(node.Left, key, value);
        }
        else // key > node->key
        {
            node.Right = Insert(node.Right, key, value);
        }

        return node;
    }
    //核心代码---结束

    // 查看以node为根的二分搜索树中是否包含键值为key的节点, 使用递归算法
    private bool Contains(Node node, TKey key)
    {
        if (node == null)
            return false;

        if (key.CompareTo(node.Key) == 0)
            return true;
        else if (key.CompareTo(node.Key) < 0)
            return Contains(node.Left, key);
        else // key > node->key
            return Contains(node.Right, key);
    }

    // 在以node为根的二分搜索树中查找key所对应的value, 递归算法
    // 若value不存在, 则返回NULL
    private TValue Search(Node node, TKey key)
    {
        if (node == null)
            return null;

        if (key.CompareTo(node.Key) == 0)
            return node.Value;
        else if (key.CompareTo(node.Key) < 0)
            return Search(node.Left, key);
        else // key > node->key
            return Search(node.Right, key);
    }


    // 对以node为根的二叉搜索树进行前序遍历, 递归算法
    private void PreOrder(Node node)
    {
        if (node != null)
        {
            Debug.Log(node.Key);
            PreOrder(node.Left);
            PreOrder(node.Right);
        }
    }

    // 对以node为根的二叉搜索树进行中序遍历, 递归算法
    private void InOrder(Node node)
    {
        if (node != null)
        {
            InOrder(node.Left);
            Debug.Log(node.Key);
            InOrder(node.Right);
        }
    }

    // 对以node为根的二叉搜索树进行后序遍历, 递归算法
    private void PostOrder(Node node)
    {
        if (node != null)
        {
            PostOrder(node.Left);
            PostOrder(node.Right);
            Debug.Log(node.Key);
        }
    }


    // 返回以node为根的二分搜索树的最小键值所在的节点
    private Node Minimum(Node node)
    {
        if (node.Left == null)
            return node;

        return Minimum(node.Left);
    }

    // 返回以node为根的二分搜索树的最大键值所在的节点
    private Node Maximum(Node node)
    {
        if (node.Right == null)
            return node;

        return Maximum(node.Right);
    }

    // 删除掉以node为根的二分搜索树中的最小节点
    // 返回删除节点后新的二分搜索树的根
    private Node RemoveMin(Node node)
    {
        if (node.Left == null)
        {
            Node rightNode = node.Right;
            node.Right = null;
            _count--;
            return rightNode;
        }

        node.Left = RemoveMin(node.Left);
        return node;
    }

    // 删除掉以node为根的二分搜索树中的最大节点
    // 返回删除节点后新的二分搜索树的根
    private Node RemoveMax(Node node)
    {

        if (node.Right == null)
        {

            Node leftNode = node.Left;
            node.Left = null;
            _count--;
            return leftNode;
        }

        node.Right = RemoveMax(node.Right);
        return node;
    }

    // 删除掉以node为根的二分搜索树中键值为key的节点, 递归算法
    // 返回删除节点后新的二分搜索树的根
    Node Remove(Node node, TKey key)
    {
        if (node == null)
            return null;

        if (key.CompareTo(node.Key) < 0)
        {
            node.Left = Remove(node.Left, key);
            return node;
        }
        else if (key.CompareTo(node.Key) > 0)
        {
            node.Right = Remove(node.Right, key);
            return node;
        }
        else
        {
            // key == node->key

            // 待删除节点左子树为空的情况
            if (node.Left == null)
            {
                Node rightNode = node.Right;
                node.Right = null;
                _count--;
                return rightNode;
            }

            // 待删除节点右子树为空的情况
            if (node.Right == null)
            {
                Node leftNode = node.Left;
                node.Left = null;
                _count--;
                return leftNode;
            }

            // 待删除节点左右子树均不为空的情况

            // 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
            // 用这个节点顶替待删除节点的位置
            Node successor = new Node(Minimum(node.Right));
            _count++;

            successor.Right = RemoveMin(node.Right);
            successor.Left = node.Left;

            node.Left = node.Right = null;
            _count--;

            return successor;
        }
    }
}

二分搜索树的特性一、顺序性

二分搜索树可以当做查找表的一种实现。

我们使用二分搜索树的目的是通过查找 key 马上得到 value。minimum、maximum、successor（后继）、predecessor（前驱）、floor（地板）、ceil（天花板、rank（排名第几的元素）、select（排名第n的元素是谁）这些都是二分搜索树顺序性的表现。

二、局限性

二分搜索树在时间性能上是具有局限性的。

如下图所示，元素节点一样，组成两种不同的二分搜索树，都是满足定义的：

二叉搜索树可能退化成链表，相应的，二叉搜索树的查找操作是和这棵树的高度相关的，而此时这颗树的高度就是这颗树的节点数 n，同时二叉搜索树相应的算法全部退化成 O(n) 级别。

二分搜索树

Java相关栏目本月热门文章