数据结构 - 二叉搜索树(Binary Search Tree)

接上章： 二叉树简介

本章主要介绍二叉搜索树的性质以及二叉搜索树节点的增加和删除操作。

◼二叉搜索树是二叉树的一种，是应用非常广泛的一种二叉树，英文简称为 BST ,又被称为:二叉查找树、二叉排序树 。

一、【二叉搜索树】性质：

二叉搜索树性质：
◼任意一个节点的值都大于其左子树所有节点的值 ；
◼任意一个节点的值都小于其右子树所有节点的值 ；
◼它的左右子树也是一棵二叉搜索树
◼ 二叉搜索树可以大大提高搜索数据的效率
◼ 二叉搜索树存储的元素必须具备可比较性，比如 int、double 等；
◼如果是自定义类型，需要指定比较方式 ，不允许为 null

001.png

二、【二叉搜索树】节点的增加和删除。

◼1.二叉搜索树节点的添加
节点的添加分三步走策略：
1.1 找到父节点 parent
1.2 创建新节点 node
1.3 parent.left == node 或者parent.right = node
注意：遇到相等的元素，建议覆盖旧值

如添加1、11。如下图所示：

002.JPG

二叉搜索树【添加】节点核心伪代码：

public void add(E element) {
        elementNotNullCheck(element);
        
        // 添加第一个节点
        if (root == null) {
            root = new Node<>(element, null);
            size++;
            return;
        }
        
        // 添加的不是第一个节点
        // 找到父节点
        Node<E> parent = root;
        Node<E> node = root;
        int cmp = 0;
        while (node != null) {
            cmp = compare(element, node.element);
            //记录父节点
            parent = node;
            if (cmp > 0) {
                node = node.right;
            } else if (cmp < 0) {
                node = node.left;
            } else { // 相等
                node.element = element;
                return;
            }
        }

        // 看看插入到父节点的哪个位置
        Node<E> newNode = new Node<>(element, parent);
        if (cmp > 0) {
            parent.right = newNode;
        } else {
            parent.left = newNode;
        }
    }

◼2.二叉搜索树节点的删除
相对于二叉搜索树节点的添加，这里二叉搜索树的删除就相对比较麻烦一点，分为节点为三种情况，分别是叶子节点的删除，度为1节点的删除和度为2节点的删除。

◼2.二叉搜索树节点的删除

◼2.1 叶子节点的删除
◼ 直接删除
✓ node == node.parent.left
✓ node.parent.left = null

✓ node == node.parent.right
✓ node.parent.right = null

✓ node.parent == null
✓ root = null

003.jpg

◼2.2 度为1节点的删除

◼ 用 子节点【替代】原节点的位置
◼child 是 node.left 或者 child 是 node.right
◼用 child 替代 node 的位置

✓如果node 是左子节点
➢child.parent = node.parent
➢node.parent.left = child
✓如果node 是右子节点
➢child.parent = node.parent
➢node.parent.right = child
✓如果node 是根节点
➢root = child
➢child.parent = null

003-2.jpg

◼2.3 度为2节点的删除

◼ 先用前驱或者后继节点的值覆盖原节点的值
◼ 然后删除相应的前驱或者后继节点
如果一个节点的度为 2，那么,它的前驱、后继节点的度只可能是 1 和 0

003-3.jpg

二叉搜索树【删除】节点核心伪代码：

private void remove(Node<E> node) {
        if (node == null) return;
        // 度为2的节点
        if (node.hasTwoChildren()) { 
            // 找到后继节点
            Node<E> s = successor(node);
            // 用后继节点的值覆盖度为2的节点的值
            node.element = s.element;
            // 删除后继节点
            node = s;
        }
        
        // 删除node节点（node的度必然是1或者0）
        Node<E> replacement = node.left != null ? node.left : node.right;
        // node是度为1的节点
        if (replacement != null) { 
            // 更改parent
            replacement.parent = node.parent;
            // 更改parent的left、right的指向
            if (node.parent == null) { // node是度为1的节点并且是根节点
                root = replacement;
            } else if (node == node.parent.left) {
                node.parent.left = replacement;
            } else { // node == node.parent.right
                node.parent.right = replacement;
            }
        } else if (node.parent == null) { // node是叶子节点并且是根节点
            root = null;
        } else { // node是叶子节点，但不是根节点
            if (node == node.parent.left) {
                node.parent.left = null;
            } else { // node == node.parent.right
                node.parent.right = null;
            }
        }
    }

这里记录下二叉搜索树的性质以及二叉搜索树节点的添加和删除，便于以后查阅学习。