二叉搜索树

【数据结构与算法】二叉搜索树

二叉搜索树也叫二叉排序树，它是二叉树中的一个变种，为什么叫做搜索树呢？是因为它的查询效率更高一些，二叉树的特点如下：

首先它肯定是一个二叉树
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树。

比如下图就是一个二叉搜索树：

二叉搜索树

普通二叉树的查找性能时间复杂度是O(n)，二叉搜索树的查询时间复杂度是O(longN)，其实就是二分查找，不过其最坏情况的时间复杂度是O(N)，也就是树形退化为单链表的形式。

结构定义

在二叉树搜索树的结构中，要增加key属性，该属性用来判断大小，key是不可以重复的，对于任意一个树节点，它的key比左子树都大，比右子树都小，通常在Java语言中，可以使用泛型定义该key，而且要继承Comparable接口。

首先我们要定义一个二叉搜索树的节点载体BSTNode:

public class BSTNode<T extends Comparable<T>> {
    /**
     * 键，用于比较，唯一
     */
    T key;
    /**
     * 存储的具体值
     */
    Object value;
    /**
     * 左节点
     */
    BSTNode<T> left;
    /**
     * 右节点
     */
    BSTNode<T> right;

    public BSTNode() {
    }

    public BSTNode(T key) {
        this.key = key;
    }

    public BSTNode(T key, Object value) {
        this.key = key;
        this.value = value;
    }

    public BSTNode(T key, Object value, BSTNode<T> left, BSTNode<T> right) {
        this.key = key;
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

此外我们还有提供一个类BSTree，该类是主要是提供二叉搜索树的一些方法，比如加入节点、查询节点等操作，通常可以将两个类合并，也就是将BSTNode作为BSTree的内部类，同时在BSTree内部提供一个BSTNode的属性。

/**
 * 二叉搜索树
 */
public class BSTree<T extends Comparable<T>> {
    // 根节点
    BSTNode<T> root;


    /**
     * 节点类
     *
     * @param <T>
     */
    static class BSTNode<T extends Comparable<T>> {
        /**
         * 键，用于比较，唯一
         */
        T key;
        /**
         * 存储的具体值
         */
        Object value;
        /**
         * 左节点
         */
        BSTNode<T> left;
        /**
         * 右节点
         */
        BSTNode<T> right;

        public BSTNode() {
        }

        public BSTNode(T key) {
            this.key = key;
        }

        public BSTNode(T key, Object value) {
            this.key = key;
            this.value = value;
        }

        public BSTNode(T key, Object value, BSTNode<T> left, BSTNode<T> right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
}

通过Key获取值

接下来需要给二叉搜索树提供多种方法，先看通过key获取值的方法。

二叉搜索树

比如要查找key=3的节点值，其实就是二分查找的思想，从根节点4进入，首先判断是否等于传入的key=3，发现不是，并且key < 4，那么就去左子树查询，跟节点2比较，发现key > 2，再跟节点3比较，发现相等，返回这个值。

首先使用递归的方式实现。

/**
 * 实现通过key获取值 
 */
public Object get(T key) {
    // 递归
    return doGetRecursion(root, key);
}
/**
 * 递归实现通过key获取值 
 */
private Object doGetRecursion(BSTNode<T> node, T key) {
    if (key == null) {
        return null;
    }
    if (node == null) {
        return null;
    }
    int c = node.key.compareTo(key);
    if (c < 0) {
        return doGetRecursion(node.right, key);
    } else if (c > 0) {
        return doGetRecursion(node.left, key);
    } else {
        return node.value;
    }
}

测试下：

public static void main(String[] args) {
    // 生成一个树
    BSTree<Integer> bsTree = new BSTree<>();
    BSTNode<Integer> n1 = new BSTNode<>(1, 1);
    BSTNode<Integer> n2 = new BSTNode<>(2, 2);
    BSTNode<Integer> n3 = new BSTNode<>(3, 3);
    BSTNode<Integer> n4 = new BSTNode<>(4, 4);
    BSTNode<Integer> n5 = new BSTNode<>(5, 5);
    BSTNode<Integer> n6 = new BSTNode<>(6, 6);
    BSTNode<Integer> n7 = new BSTNode<>(7, 7);
    BSTNode<Integer> n8 = new BSTNode<>(8, 8);
    n4.left = n2;
    n4.right = n7;
    n2.left = n1;
    n2.right = n3;
    n7.left = n6;
    n7.right = n8;
    n6.left = n5;
    bsTree.root = n4;
    System.out.println(bsTree.get(3)); // 3
}

运行结果如下：

public static void main(String[] args) {
    // 生成一个树
    BSTree<Integer> bsTree = new BSTree<>();
    BSTNode<Integer> n1 = new BSTNode<>(1, 1);
    BSTNode<Integer> n2 = new BSTNode<>(2, 2);
    BSTNode<Integer> n3 = new BSTNode<>(3, 3);
    BSTNode<Integer> n4 = new BSTNode<>(4, 4);
    BSTNode<Integer> n5 = new BSTNode<>(5, 5);
    BSTNode<Integer> n6 = new BSTNode<>(6, 6);
    BSTNode<Integer> n7 = new BSTNode<>(7, 7);
    BSTNode<Integer> n8 = new BSTNode<>(8, 8);
    n4.left = n2;
    n4.right = n7;
    n2.left = n1;
    n2.right = n3;
    n7.left = n6;
    n7.right = n8;
    n6.left = n5;
    bsTree.root = n4;
    System.out.println(bsTree.get(3)); // 3
    System.out.println(bsTree.get(4)); // 4
    System.out.println(bsTree.get(5)); // 5
}

运行结果如下：

运行结果

可以通过非递归的方式实现

/**
 * 实现通过key获取值
 */
public Object get(T key) {
    // 递归
//        return doGetRecursion(root, key);
    // 非递归
    return doGetIter(root, key);
}

/**
 * 迭代实现通过key获取值
 */
private Object doGetIter(BSTNode<T> node, T key) {
    if (key == null) {
        return null;
    }
    while (node != null) {
        int c = node.key.compareTo(key);
        if (c < 0) {
            node = node.right;
        } else if (c > 0) {
            node = node.left;
        } else {
            return node.value;
        }
    }
    return null;
}

再次测试运行结果是正确的。

查找最小key节点值

二叉搜索树

在上图中，最小key就是节点1对应的值，那么如何找呢？

根据二叉搜索树的特点，我们可以很容易想到，最小key一定在左子树中，在上图中，就是节点1，如果节点1是空的，那么就是节点2，肯定不会是节点3，如果节点2也不存在，那么最小key一定是根节点4，肯定不会在节点4的右子树中。

我们可以通过递归来实现：

/**
 * 获取二叉搜索树中最小的key的值
 * @return
 */
public Object min() {
    return doMinRecursion(root);
}

/**
 * 递归获取二叉搜索树中最小的key的值
 * @param node
 * @return
 */
private Object doMinRecursion(BSTNode<T> node) {
    if (node == null) { // 如果节点是空的，直接返回空即可。
        return null;
    }
    if (node.left == null) { //如果节点没有左子树，那么当前节点就是最小key节点
        return node.value;
    }
    return doMinRecursion(node.left); // 如果节点存在左子树，那么就继续向左查找。
}

编写代码测试下：

public static void main(String[] args) {
    // 生成一个树
    BSTree<Integer> bsTree = new BSTree<>();
    BSTNode<Integer> n1 = new BSTNode<>(1, 1);
    BSTNode<Integer> n2 = new BSTNode<>(2, 2);
    BSTNode<Integer> n3 = new BSTNode<>(3, 3);
    BSTNode<Integer> n4 = new BSTNode<>(4, 4);
    BSTNode<Integer> n5 = new BSTNode<>(5, 5);
    BSTNode<Integer> n6 = new BSTNode<>(6, 6);
    BSTNode<Integer> n7 = new BSTNode<>(7, 7);
    BSTNode<Integer> n8 = new BSTNode<>(8, 8);
    n4.left = n2;
    n4.right = n7;
    n2.left = n1;
    n2.right = n3;
    n7.left = n6;
    n7.right = n8;
    n6.left = n5;
    bsTree.root = n4;
    System.out.println(bsTree.min()); // 1
}

运行结果如下：

最小key的值

也可以使用非递归来实现：

/**
 * 非递归获取二叉搜索树中最小的key的值
 *
 * @param node
 * @return
 */
private Object doMinIter(BSTNode<T> node) {
    if (node == null) {
        return null;
    }
    while (node.left != null) {
        node = node.left;
    }
    return node.value;
}

查找最大key节点值

最大key对应的节点值，肯定在右子树中，逻辑与上面的最小key节点值获取方式类似。

首先看递归的方法。

/**
 * 获取二叉搜索树中最大的key的节点值
 * @return
 */
public Object max() {
    // 递归
    return doMaxRecursion(root);
}

/**
 * 递归获取二叉搜索树中最大的key的节点值
 *
 * @param node
 * @return
 */
private Object doMaxRecursion(BSTNode<T> node) {
    if (node == null) {
        return null;
    }
    if (node.right == null) {
        return node.value;
    }
    return doMaxRecursion(node.right);
}

当然也能够修改为非递归的代码：

/**
 * 非递归获取二叉搜索树中最大的key的节点值
 *
 * @param node
 * @return
 */
private Object doMaxIter(BSTNode<T> node) {
    if (node == null) {
        return node;
    }
    while (node.right != null) {
        node = node.right;
    }
    return node.value;
}

插入或者更新值

二叉树中的key是唯一的，我们添加一个元素的时候首先要查看该key的节点是否存在，如果存在则更新节点值，不存在就添加进去。

我们先看找到的情况：

/**
 * 插入或者更新值
 *
 * @param key
 * @param value
 */
public void put(T key, Object value) {
    BSTNode<T> node = root;
    if (key == null) {
        return;
    }
    while (node != null) {
        int c = node.key.compareTo(key);
        if (c < 0) {
            node = node.right;
        } else if (c > 0) {
            node = node.left;
        } else {
            // 找到了，就更新
            node.value = value;
        }
    }
    // 没找到，则需要新增，首先要创建一个新的节点
    BSTNode<T> newNode = new BSTNode<>(key, value);
    // TODO 接下来就需要将新节点加入到二叉搜索树中，如果想加进去，只需要找到它的父节点即可。
}

接下来就需要将新节点加入到二叉搜索树中，如果想加进去，只需要找到它的父节点即可，那么如何找到它的父亲呢？其实在迭代的过程中，肯定是到过这个父节点，我们可以使用一个变量记录下来。

/**
 * 插入或者更新值
 *
 * @param key
 * @param value
 */
public void put(T key, Object value) {
    BSTNode<T> node = root;
    if (key == null) {
        return;
    }
    BSTNode<T> parent = null; // 记录上父节点
    while (node != null) {
        parent = node;
        int c = node.key.compareTo(key);
        if (c < 0) {
            node = node.right;
        } else if (c > 0) {
            node = node.left;
        } else {
            // 找到了，就更新
            node.value = value;
        }
    }
    // 没找到，则需要新增，首先要创建一个新的节点
    BSTNode<T> newNode = new BSTNode<>(key, value);
    // TODO 接下来就需要将新节点加入到二叉搜索树中，如果想加进去，只需要找到它的父节点即可
    
}

找到父节点后，有如下三种情况：

如果父节点为空（树就是空的），那么就将跟新节点作为根节点
否则，如果新节点的值大于父节点的值，那么新节点作为父节点的右孩子。
否则，作为左孩子。

/**
 * 插入或者更新值
 *
 * @param key
 * @param value
 */
public void put(T key, Object value) {
    BSTNode<T> node = root;
    if (key == null) {
        return;
    }
    BSTNode<T> parent = null; // 记录上父节点
    while (node != null) {
        parent = node;
        int c = node.key.compareTo(key);
        if (c < 0) {
            node = node.right;
        } else if (c > 0) {
            node = node.left;
        } else {
            // 找到了，就更新
            node.value = value;
            return;
        }
    }
    // 没找到，则需要新增，首先要创建一个新的节点
    BSTNode<T> newNode = new BSTNode<>(key, value);
    // 接下来就需要将新节点加入到二叉搜索树中，如果想加进去，只需要找到它的父节点即可。
    if (parent == null) { // 树是空的
        root = newNode;
        return;
    }
    int c = parent.key.compareTo(key);
    if (c < 0) { // 新节点的值大于父节点
        parent.right = newNode;
    } else { // 新节点的值小于于父节点
        parent.left = newNode;
    }
}

测试结果我就不粘贴了。

查找key的前任节点值

二叉搜索树

比如传入key=3返回2，传入5返回4，传入key=6返回5，什么意思呢？因为是个二叉搜索树，那么key肯定是有大小顺序的，从小到大排列key，如上图[1, 2, 3, 4, 5, 6, 7, 8]，返回传入key的前一个key对应的节点值。

第一个想到的方法肯定是排序，如何排序呢？其实对于二叉搜索树，中序遍历就是结果就是一个从小到大的排序，因此我们可以使用中序遍历得到这个数组，也就能获得前任节点，但是这种算法时间复杂度和空间复杂度都是O(N)。

可以使用其他方法：

上图中节点2、4、6、7都是有左子树的，这种情况下，前任节点值就是左子树的最大值，只需要使用二分查找法即可得到。

其他的节点1、3、5、8则没有左子树，那么就应该寻找最近的、自左而来的祖先节点，那么这个自左而来是什么意思呢？

我们可以将节点分出来多个列，如下图所示：

自左而来

比如节点5的祖先节点有4、6、7，但是只有4在左边，而5和7在右边。

那么找到这个节点呢？其实当遍历寻找key对应的节点的时候，已经经历过节点，自左而来就是说如果有node = node.right的代码，那么这个节点就是自左而来的，我们只需要记录左右一个满足上述条件的即可。

完整代码如下：

/**
 * key对应节点的前任节点值
 * @param key
 * @return
 */
public Object predecessor(T key) {
    BSTNode<T> node = root;
    BSTNode<T> parent = null;
    while(node != null) {
        int c = key.compareTo(node.key);
        if (c < 0) {
            // 向左找
            node = node.left;
        } else if (c > 0) { // 向右找
            parent = node; // 一定是自左而来
            node = node.right;
        } else {
            // 找到了
            break;
        }
    }
    // 如果通过key都没找到节点，直接返回空
    if (node == null) {
        return null;
    }
    // 找到了对应的key的节点
    // 1.节点有左子树
    if (node.left != null) {
        return doMaxIter(node.left);
    }
    // 2. 如果没有左子树，那么就需要找自左而来最近的祖先节点
    return parent == null ? null : parent.value;
}

查找key的节点的后任节点值

这个跟上面查找前任值就是正好对称的，就不分析了，直接上代码：

public Object successor(T key) {
    BSTNode<T> node = root;
    BSTNode<T> parent = null;
    while (node != null) {
        int c = key.compareTo(node.key);
        if (c < 0) {
            // 向左找
            parent = node;
            node = node.left;
        } else if (c > 0) { // 向右找
            node = node.right;
        } else {
            // 找到了
            break;
        }
    }
    // 如果通过key都没找到节点，直接返回空
    if (node == null) {
        return null;
    }
    // 找到了对应的key的节点
    // 1.节点有右子树
    if (node.right != null) {
        return doMaxIter(node.right);
    }
    // 2. 如果没有右子树，那么就需要找自右而来最近的祖先节点
    return parent == null ? null : parent.value;
}

删除节点

删除节点比较复杂，具体介绍下。

①：删除节点没有左孩子也没有有孩子，直接删除即可，比如下图中的红色节点。

没有孩子的节点

②：删除节点有左孩子没有右孩子，只需要将左子树提升即可，比如下图中的红色节点。

③：删除节点有右孩子没有左孩子，只需要将右子树提升即可，比如下图中的红色节点。

④：有左子树也有右子树

有左子树也有右子树

前三种比较简单，先看下前三种情况的编码：

/**
 * 删除节点
 */
public Object delete(T key) {
    BSTNode<T> node = root;
    BSTNode<T> parent = null;
    while (node != null) {
        int c = key.compareTo(node.key);
        if (c < 0) {
            // 向左找
            parent = node;
            node = node.left;
        } else if (c > 0) {
            parent = node;
            // 向右找
            node = node.right;
        } else {
            // 找到了
            break;
        }
    }
    if (node == null) { // 未能通过key查找到节点
        return null;
    }
    // ①：删除节点没有左孩子也没有有孩子，直接删除即可
    else if (node.left == null && node.right == null) {
        shift(parent, node, null);
    }
    // ②：删除节点有左孩子没有右孩子，只需要将左子树提升即可
    else if (node.right == null) {
        shift(parent, node, node.left);
    }
    // ③：删除节点有右孩子没有左孩子，只需要将右子树提升即可
    else if (node.left == null) {
        shift(parent, node, node.right);
    }
    return node.value;
}

/**
 * 托孤方法
 *
 * @param parentNode  父节点
 * @param deletedNode 待删除节点
 * @param childNode   子节点
 */
private void shift(BSTNode<T> parentNode, BSTNode<T> deletedNode, BSTNode<T> childNode) {
    // 如果被删除的是根节点
    if (parentNode == null) {
        root = deletedNode;
        return;
    }
    if (parentNode.left == deletedNode) {
        parentNode.left = childNode;
        return ;
    }
    if (parentNode.right == deletedNode) {
        parentNode.right = childNode;
    }
}

其实上面①②③中的情况①是一种特殊情况，可以归到②和③中，代码可以修改为：

/**
 * 删除节点
 */
public Object delete(T key) {
    BSTNode<T> node = root;
    BSTNode<T> parent = null;
    while (node != null) {
        int c = key.compareTo(node.key);
        if (c < 0) {
            // 向左找
            parent = node;
            node = node.left;
        } else if (c > 0) {
            parent = node;
            // 向右找
            node = node.right;
        } else {
            // 找到了
            break;
        }
    }
    if (node == null) { // 未能通过key查找到节点
        return null;
    }

    // ①：删除节点没有左孩子也没有有孩子，直接删除即可
    // ②：删除节点有左孩子没有右孩子，只需要将左子树提升即可
    else if (node.right == null) {
        shift(parent, node, node.left);
    }
    // ③：删除节点有右孩子没有左孩子，只需要将右子树提升即可
    else if (node.left == null) {
        shift(parent, node, node.right);
    } else {

    }
    return node.value;
}

第④种情况比较复杂，不过核心思想是使用待删除节点的后任节点顶替，主要分为两种情况：

情况一：

删除情况1

如上图，节点7是待删除节点，它有左右两个节点，这种情况下，如果删除7，那么节点6和节点8就成了孤儿了，根据二叉搜索树的特点，此时我们可以将节点8提升为4的右节点（因为8是待删除节点的后任节点），然后长兄如父，将节点6作为节点8的左孩子（原来6和8是兄弟节点）。

情况二：

情况二

如上图4是待删除节点，它的后任是5，但是如果像情况一那种方法直接将4替换为5则不行，因为5是有右子树的，而4也是有右子树的，一个节点不可能有两个右子树，如下图示不可能实现的：

错误1

怎么办呢？我们可以先将后任节点5的孩子（其实只有有孩子，不可能存在左孩子，因为如果存在左孩子，那么5肯定不是4的后任节点）先托孤给后任节点的父亲7，具体步骤如下：

首先将后任节点5的右子树托孤给节点7。

**首先将后任节点<code>5</code>的右子树托孤给节点<code>7</code>。**

然后将4替换为5，并处理5的左右孩子

最终的结果如下图：

删除后的结果

完整代码如下：

/**
 * 删除节点
 */
public Object delete(T key) {
    BSTNode<T> node = root;
    BSTNode<T> parent = null;
    while (node != null) {
        int c = key.compareTo(node.key);
        if (c < 0) {
            // 向左找
            parent = node;
            node = node.left;
        } else if (c > 0) {
            parent = node;
            // 向右找
            node = node.right;
        } else {
            // 找到了
            break;
        }
    }
    if (node == null) { // 未能通过key查找到节点
        return null;
    }

    // ①：删除节点没有左孩子也没有有孩子，直接删除即可
    // ②：删除节点有左孩子没有右孩子，只需要将左子树提升即可
    else if (node.right == null) {
        shift(parent, node, node.left);
    }
    // ③：删除节点有右孩子没有左孩子，只需要将右子树提升即可
    else if (node.left == null) {
        shift(parent, node, node.right);
    } else { // 左右子树都存在
        BSTNode<T> b = node.right; // 待删除节点的后任节点
        BSTNode<T> bParent = node; // b的父亲
        while (b.left != null) {
            bParent = b;
            b = b.left;
        }
        // 此时b就是后继节点
        // 删除节点和它的后任节点不相邻，要处理后任节点的子树，将其托孤而后任节点的父节点
        if (bParent != node) {
            shift(bParent, b, b.right);
            b.right = node.right;
        }
        // 后任节点取代被删除节点
        shift(parent, node, b);
        b.left = node.left;

    }
    return node.value;
}

/**
 * 托孤方法
 *
 * @param parentNode  父节点
 * @param deletedNode 待删除节点
 * @param childNode   子节点
 */
private void shift(BSTNode<T> parentNode, BSTNode<T> deletedNode, BSTNode<T> childNode) {
    // 如果被删除的是根节点
    if (parentNode == null) {
        root = deletedNode;
        return;
    }
    if (parentNode.left == deletedNode) {
        parentNode.left = childNode;
        return;
    }
    if (parentNode.right == deletedNode) {
        parentNode.right = childNode;
    }
}

【数据结构与算法】二叉搜索树

【数据结构与算法】二叉搜索树

结构定义

通过Key获取值

查找最小key节点值

查找最大key节点值

插入或者更新值

查找key的前任节点值

查找key的节点的后任节点值

删除节点

添加新评论

最新文章

最近回复

分类

归档

其它