Version: Next

二叉搜索树

Binary Search Tree

思考：
在n个动态的整数中，搜索某个整数（检查其是否存在）

假设使用动态数组存放元素，从第0个位置开始遍历搜索，平均时间复杂度为O(n)

0	1	2	3	4	5	6	7	8	9
31	66	17	15	28	20	59	88	45	56

如果维护一个有序的动态数组，使用二分搜索，最坏时间复杂度O(logn)
但添加、删除的平均时间复杂度为O(n)

0	1	2	3	4	5	6	7	8	9
15	17	20	28	31	45	56	59	66	88

使用二叉搜索树，添加、删除、搜索的最坏时间复杂度都可以优化到O(logn)

二叉搜索树Binary Search Tree是二叉树的一种，应用非常广泛，简称BST
又称：二叉查找树、二叉排序树
任意一个节点的值都大于其左子树所有节点的值
任意一个节点的值都小于其右子树所有节点的值
它的左右子树也是一颗二叉搜索树
二叉搜索树可以大大提高查找效率
二叉搜索树存储的元素必须具备可比较性

接口设计

方法	功能
`int size()`	元素的数量
`boolean isEmpty()`	是否为空
`void clear()`	清空
`void add(E element)`	添加元素
`void remove(E element)`	删除元素
`boolean contains(E element)`	是否包含元素
`*void elementNotNullCheck(E element)`	可选：判断传入值是否为空，二叉搜索树不允许插入空节点

对比线性表，可见它没有索引

树节点类

维护成员变量
存储的内容，E element
左节点
右节点
父节点

/**
 * 节点类
 */
private static class Node<E> {
    E element;
    Node<E> leftNode;
    Node<E> rightNode;
    Node<E> parentNode; // 父节点

    /**
     * 构造方法
     * 传入节点值并制定父节点，不适用左右节点，因为左右节点是否存在的情况比较复杂，
     * 而一颗树中，只有根节点没有父节点，其余节点都有父节点
     *
     * @param element    节点值
     * @param parentNode 父节点
     */
    public Node(E element, Node<E> parentNode) {
        this.element = element;
        this.parentNode = parentNode;
    }
  
    public boolean isLeaf() {
        return leftNode == null && rightNode == null;
    }

    /**
     * 返回节点是否有两个孩子
     */
    public boolean hasTwoChildren() {
        return leftNode != null && rightNode != null;
    }
}

节点非空检查

private void elementNotNullCheck(E element) {
    if (element == null) throw new IllegalArgumentException("节点值不能为空");
}

节点比较方法

方法1：Comparable

二叉搜索树泛型E强制为实现了排序接口Comparable的类
之后，可以调用排序接口Comparable的compareTo(...)方法
对于自定义的类，必须实现排序接口Comparable，重写compareTo方法，才能存储到二叉搜索树中

强制二叉搜索树元素实现排序接口

public class MyBinarySearchTree<E extends Comparable<E>> {
  ...
}

调用排序接口中的compareTo方法

/**
 * 比较两个元素的大小
 *
 * @param element1 元素1
 * @param element2 元素2
 * @return 0: 表示 element1等于element2; 大于0 代表 element1 > element2; 小于0: element1 < element2
 */
private int compare(E element1, E element2) {
    return element1.compareTo(element2);
}

对于自定义类，必须实现排序接口才能存储到二叉搜索树中

// 以Person类举例
public class Person implements Comparable<Person> {
    public int age;

    public Person(int age) {
        this.age = age;
    }

    @Override
    public int compareTo(Person o) {
        return this.age - o.age;
    }
}

方法2：Comparator

Comparable的弊端

实现Comparable接口，重写compareTo方法，直接将一个类的排序规则写死了，不够灵活
使用Comparator，每次都可以定义不同的排序规则，在创建二叉搜索树时，将具体的Comparator传入，从而使其排序规则生效，更加灵活

二叉搜索树泛型直接写E即可
在二叉搜索树内部添加一个成员变量Comparator<E> comparator
添加一个有参构造函数，支持在创建二叉搜索树时，传入一个Comparator的实现类，一般使用匿名内部类或lambda

不再强制内容实现排序接口，提供有参构造器接收外部比较器

public class MyBinarySearchTree<E> {
    private int size;
    private Node<E> rootNode;
    private Comparator<E> comparator;

    public MyBinarySearchTree() { // 使用泛型E中默认的排序规则
        this(null); // 调用有参构造函数，传入一个null比较器
    }

    public MyBinarySearchTree(Comparator<E> comparator) { // 从外部接收个性化排序规则
        this.comparator = comparator;
    }
  
        ...
}  

在二叉搜索树的比较方法中，使用比较器中的compare方法进行比较

/**
 * 比较两个元素的大小
 *
 * @param element1 元素1
 * @param element2 元素2
 * @return 0: 表示 element1等于element2; 大于0 代表 element1 > element2; 小于0: element1 < element2
 */
private int compare(E element1, E element2) {
    return this.comparator.compare(element1, element2);
}

构建二叉搜索树时，传入不同内容的比较器，实现个性化比较

@Test
public void mainTest() {
    // 定义两种比较规则，lambda重写Comparator接口的compare方法
    Comparator<Person> personComparator1 = (p1, p2) -> p1.age - p2.age;
    Comparator<Person> personComparator2 = (p1, p2) -> p2.age - p1.age;

    MyBinarySearchTree<Person> bst1 = new MyBinarySearchTree<>(personComparator1);
    MyBinarySearchTree<Person> bst2 = new MyBinarySearchTree<>(personComparator2);
}

最佳实践

新问题

这样一来，在创建二叉搜索树时，必须传入一个外部的比较器

应当想办法兼容不传入比较器的使用方式，即使用二叉搜索树的无参构造方法
- 不用外部比较器Comparator，则需要强制E指代的类实现Comparable接口
- 但如果使用外部比较器Comparator，那么上一条中的强制实现Comparable接口就多余了
- 因此，不要在二叉搜索树的泛型E上强制要求实现任何排序接口
在二叉搜索树中的比较方法compare中进行判断
- 如果存在外部传入的比较器，优先使用外部比较器Comparator
- 否则，就是没有外部传入的比较器Comparator，那么强制必须使用Comparable，否则树中元素就失去了可比较性，如果没有实现Comparable，则抛出异常

二叉搜索树

public class MyBinarySearchTree<E> {
    private int size;
    private Node<E> rootNode;
    private Comparator<E> comparator;

    public MyBinarySearchTree() { // 使用泛型E中默认的排序规则
        this(null); // 调用有参构造函数，传入一个null比较器
    }

    public MyBinarySearchTree(Comparator<E> comparator) { // 从外部接收个性化排序规则
        this.comparator = comparator;
    }
  ...
}

二叉搜索树的比较方法，优先使用外部Comparator，否则使用Comparable

/**
 * 比较两个元素的大小
 *
 * @param element1 元素1
 * @param element2 元素2
 * @return 0: 表示 element1等于element2; 大于0 代表 element1 > element2; 小于0: element1 < element2
 */
private int compare(E element1, E element2) {
    if (this.comparator != null) // 存在外部传入的比较器
        return this.comparator.compare(element1, element2);
    else // 没有外部比较器，强制使用Comparable
        return ((Comparable<E>) element1).compareTo(element2); // 强制类型转换为Comparable实现类，强转失败说明没实现接口，抛出异常
}

调用示例

@Test
public void mainTest() {
    // 定义两种比较规则，lambda重写Comparator接口的compare方法
    Comparator<Person> personComparator1 = (p1, p2) -> p1.age - p2.age;
    Comparator<Person> personComparator2 = (p1, p2) -> p2.age - p1.age;
    // 传入外部比较器
    MyBinarySearchTree<Person> bst1 = new MyBinarySearchTree<>(personComparator1);
    MyBinarySearchTree<Person> bst2 = new MyBinarySearchTree<>(personComparator2);
    // 使用Person自己实现的Comparable
    MyBinarySearchTree<Person> bst3 = new MyBinarySearchTree<>();
}

添加方法

插入元素非空检查，二叉搜索树不允许插入空值
判断根节点是否存在，如果不存在则插入的是根节点，size++之后直接返回；如果根节点已经存在，根据二叉搜索树的定义规则进行插入
插入元素与根元素比大小，比根大找右节点，比根小找左节点，以此类推，直到叶子节点，即按照这个规则找到了null
找到父节点parent
创建新节点node
parent.left = node或parent.right = node

遇到相等节点怎么办？

直接返回
创建一个等值新节点，覆盖旧节点

建议直接覆盖旧节点，主要是针对自定义的类，除了比较的属性以外，可能在其他属性上存在区别，为了反映其他属性的变化，建议进行覆盖

public void add(E element) {
    // 非空判断
    elementNotNullCheck(element);

    // 判断根节点是否存在
    if (this.rootNode == null) {
        this.rootNode = new Node<>(element, null);
        size++;
        return;
    }

    // 根节点已经存在
    // 1. 找到父节点
    Node<E> currentNode = rootNode; // 当前正在比较的树节点
    Node<E> parentNode = null; // 记录当前节点的父节点
    int compareResult = 0; // 比较大小的结果
    // 一直往下找
    while (currentNode != null) {
        compareResult = compare(element, currentNode.element); // 比较大小
        // 在currentNode向下迭代之前，先记录它，等current迭代之后，这个记录值就成了current的parent
        parentNode = currentNode;

        if (compareResult < 0) { // element < 当前节点
            // 找左节点
            currentNode = currentNode.leftNode;
        } else if (compareResult > 0) { // element > 当前节点
            // 找右节点
            currentNode = currentNode.rightNode;
        } else { // 相等 覆盖旧节点
            currentNode.element = element;
            return;
        }
    }
    // 跳出循环，已经走到了树的叶子节点，此时currentNode一定指向null，parent就是current的爸爸
    // 2. 创建新节点
    Node<E> newNode = new Node<>(element, parentNode);
    // 3. parent.left 或 parent.right指向创建的节点
    if (compareResult > 0) // 插入到父节点的右
        parentNode.rightNode = newNode;
    else // 插入到父节点的左
        parentNode.leftNode = newNode;

    size++;
}

无等值测试

整型：添加节点，并打印树

测试

private static void integerTest() {
    Integer[] data = new Integer[]{
            7, 4, 9, 2, 5, 8, 11, 3
    };

    // 不传入外部比较器，使用Integer的Comparable比较，而Integer默认实现了Comparable接口
    MyBinarySearchTree<Integer> bst = new MyBinarySearchTree<>();
    // 添加
    for (int i = 0; i < data.length; i++) {
        bst.add(data[i]);
    }

    BinaryTrees.println(bst);
}

public static void main(String[] args) {
    integerTest();
}

运行结果

  ┌──7──┐
  │     │
┌─4─┐ ┌─9─┐
│   │ │   │
2─┐ 5 8   11
  │
  3

自定义类Person

private static void personTest() {
    Integer[] ages = new Integer[]{
            7, 4, 9, 2, 5, 8, 11, 3
    };

    // 定义两种比较规则，lambda重写Comparator接口的compare方法
    Comparator<Person> personComparator1 = (p1, p2) -> p1.age - p2.age;
    Comparator<Person> personComparator2 = (p1, p2) -> p2.age - p1.age;
    // 传入外部比较器
    MyBinarySearchTree<Person> bst1 = new MyBinarySearchTree<>(personComparator1);
    MyBinarySearchTree<Person> bst2 = new MyBinarySearchTree<>(personComparator2);
    // 使用Person自己实现的Comparable
    MyBinarySearchTree<Person> bst3 = new MyBinarySearchTree<>();

    for (Integer age : ages) {
        Person person = new Person(age);
        bst1.add(person);
        bst2.add(person);
        bst3.add(person);
    }

    BinaryTrees.println(bst1);
    BinaryTrees.println(bst2);
    BinaryTrees.println(bst3);
}

public static void main(String[] args) {
//        integerTest();
    personTest();
}

运行结果：注意先重写Person类的toString方法

  ┌──7──┐
  │     │
┌─4─┐ ┌─9─┐
│   │ │   │
2─┐ 5 8   11
  │
  3
   ┌──7──┐
   │     │
 ┌─9─┐ ┌─4─┐
 │   │ │   │
11   8 5 ┌─2
         │
         3
  ┌──7──┐
  │     │
┌─4─┐ ┌─9─┐
│   │ │   │
2─┐ 5 8   11
  │
  3

等值测试

修改Person类
添加name属性
重写toString方法

修改Person类，添加name属性，重写toString

public class Person implements Comparable<Person> {
    public int age;
    public String name;

    public Person(int age, String name) {
        this.age = age;
        this.name = name;
    }

    @Override
    public int compareTo(Person o) {
        return age - o.age;
    }

    @Override
    public String toString() {
        return this.name + " : " + this.age;
    }
}

等值插入

private static void sameAgePersonTest() {
    MyBinarySearchTree<Person> bst = new MyBinarySearchTree<>((p1, p2) -> p1.age - p2.age);

    bst.add(new Person(2,"Second Person"));
    bst.add(new Person(1,"First Person"));
    bst.add(new Person(3,"Third Person"));

    BinaryTrees.println(bst);

    bst.add(new Person(3,"3rd Person"));

    BinaryTrees.println(bst);
}

public static void main(String[] args) {
    //        integerTest();
    // personTest();
    sameAgePersonTest();
}

运行结果

        ┌─Second Person : 2─┐
        │                   │
First Person : 1     Third Person : 3

        ┌─Second Person : 2─┐
        │                   │
First Person : 1      3rd Person : 3

插入了两次age = 3的Person对象，虽然年龄一样，但是具有不同的名字，可见结果中，名字发生了改变Third Person -> 3rd Person

不作处理，直接返回，不能体现相同年龄的两个人名字上去的别
只有进行替换，才能反映名字的改变

前驱节点

前驱节点：中序遍历时的前一个节点
某节点的前驱结点，一定是该节点左子树中最大的节点，对于二叉搜索树，即前一个比该节点小的节点
node.left != null，左子树不为空，即前驱节点一定在左子树中，找到左子树中的最大节点，即一直找右节点，直到右节点为空
node.left == null && node.parent != null，如果左子树为空，父节点不为空，那么前驱结点为父节点的父节点的父节点....node.parent.parent.parent...，直到当前node在parent的右子树中为止
上一条可以理解为找到某节点右子树最小节点的逆过程，本身的过程为1. 向右走一下，2. 一直左子左子左子左子，现在倒过来1. 一直爸爸爸爸，直到节点为父节点的右节点
node.left == null && node.parent == null，肯定是根节点，并且根节点没有左子树，此时节点没有前驱结点

求前驱节点

/**
 * 传入一个节点，返回该节点的前驱节点
 *
 * @param node 传入节点
 * @return node的前驱节点
 */
private Node<E> predecessor(Node<E> node) {
    if (node == null) return null;
    // 1. node.left != null
    if (node.leftNode != null) {
        node = node.leftNode;
        while (node.rightNode != null)
            node = node.rightNode;
        return node;
    }
    // 2. node.left == null && node.parent != null
    while (node.parentNode != null && node == node.parentNode.leftNode) {
        node = node.parentNode;
    }
    
   /* if (node.parentNode != null) return node.parentNode;
    // 3. node.left == null && node.parent == null
    return null;*/
    // 故简化为
    return node.parentNode;
}

后继节点

info

与前驱节点的逻辑相反

后继节点

/**
 * 传入一个节点，返回该节点的后继节点
 *
 * @param node 传入节点
 * @return node的后继节点
 */
private Node<E> successor(Node<E> node) {
    if (node == null) return null;
    // 1. node.right != null
    if (node.rightNode != null) {
        node = node.rightNode;
        while (node.leftNode != null)
            node = node.leftNode;
        return node;
    }
    // 2. node.right == null && node.parent != null
    while (node.parentNode != null && node == node.parentNode.rightNode) {
        node = node.parentNode;
    }

   /* if (node.parentNode != null) return node.parentNode;
    // 3. node.right == null && node.parent == null
    return null;*/
    // 故简化为
    return node.parentNode;
}

删除方法

删除叶子节点

直接删除节点即可
若node == node.parent.left，则令node.parent.left = null，垃圾回收器自动回收
若node == node.parent.right，则令node.parent.right = null，垃圾回收器自动回收
若node.parent == null，一定是根节点，则令root = null

删除度为1的节点

用子节点替换原节点的位置即可
如果节点的左子树不为空，则child为节点的左节点；若节点的右子树不为空，则child为节点的右节点
child = node.left或node.right
情况一：child是node.left
child替换原节点的子节点：node.parent.left = child
维护child的父节点，当前它的父节点指向要删除的节点node，我们让他指向要删除节点的父节点node.parent即可：child.parent = node.parent
情况二：child是node.right
child替换原节点的子节点：node.parent.right = child
维护child的父节点，当前它的父节点指向要删除的节点node，我们让他指向要删除节点的父节点node.parent即可：child.parent = node.parent
情况三：node.parent为空，要删除节点没有父节点
node必是根节点root，则令根节点为当前node的子节点即可，即root = child
维护child的父节点，现在child成为了根节点，它没有父节点，则child.parent = null

删除度为2的节点

从左右子树中寻找一个节点来替换原节点的位置
这个节点显然用前驱节点或后继节点最为合适，因为这样不会破坏二叉树的基本性质
用前驱节点或者后继节点的值覆盖原节点的值
删除相应的前驱节点或后继节点
成立的原因：重要性质：度为2的节点，其前驱、后继节点的度只可能是1或0

info

调用时，传入的是要删除的值
需要一个方法，根据值找到对应的节点
在树中删除这个节点

根据值，找到对应节点

/**
 * 根据元素值，找到对应节点并返回
 *
 * @param element 节点元素值
 * @return 对应的节点
 */
private Node<E> node(E element) {
    Node<E> node = rootNode;
    while (node != null) {
        int compareResult = compare(element, node.element);
        if (compareResult == 0) return node; // 相等返回节点
        // element > node.element，向右搜索
        if (compareResult > 0) node = node.rightNode;
            // element < node.element，向左搜索
        else
            node = node.leftNode;
    }
    return null;
}

删除时，要求传入节点对应的值，在方法内部，根据值找到对应的节点并删除该节点

对外暴露的删除方法，参数为要删除节点对应的值

/**
 * 根据传入元素，删除指定节点
 *
 * @param element 要删除的元素
 */
public void remove(E element) {
    remove(node(element)); // 根据值找到节点并删除
}

删除方法

/**
 * 删除指定节点
 *
 * @param node 要删除的节点
 */
private void remove(Node<E> node) {
    if (node == null) return;
    // 3. 删除度为2的节点
    if (node.hasTwoChildren()) { // 度为2
        // 找到前驱节点
        Node<E> predecessor = predecessor(node);
        // 前驱节点的值覆盖到要删除节点
        node.element = predecessor.element;
        // 删除前驱节点，先让引用node指向前驱节点predecessor
        // 之后再删除node即可
        node = predecessor;
    }
    // 删除node节点，node度必然为0或1
    // 找到子节点
    Node<E> replacementNode = node.leftNode != null ? node.leftNode : node.rightNode;
    // 2. 删除度为1的节点
    if (replacementNode != null) {
        replacementNode.parentNode = node.parentNode; // 更改parent
        // 更改node.parent的左或右子节点
        if (node.parentNode == null) { // node为度为1 的 根 节点
            // 根节点指向replacement
            rootNode = replacementNode;
        } else if (node == node.parentNode.leftNode)
            node.parentNode.leftNode = replacementNode;
        else
            node.parentNode.rightNode = replacementNode;

    } else if (node.parentNode == null) { // 是根节点的叶子节点
        rootNode = null;
    } else { // 1. 删除叶子节点 度为0, 但不是根节点
        if (node.parentNode.rightNode == node)
            node.parentNode.rightNode = null;
        else
            node.parentNode.leftNode = null;
    }

    size--;
}

测试

删除节点测试

private static void treeNodeDeleteTest() {
    Integer[] data = new Integer[]{
            7, 4, 9, 2, 5
    };

    MyBinarySearchTree<Integer> bst = new MyBinarySearchTree<>();
    // 添加
    for (int i = 0; i < data.length; i++) {
        bst.add(data[i]);
    }

    BinaryTrees.println(bst);

    bst.remove(4);

    BinaryTrees.println(bst);
}

运行结果

  ┌─7─┐
  │   │
┌─4─┐ 9
│   │
2   5
┌─7─┐
│   │
2─┐ 9
  │
  5

clear方法

删除整棵二叉搜索树

将根节点设置为空，同时将size设置为0

/**
 * 删除整棵二叉搜索树
 */
public void clear() {
    rootNode = null;
    size = 0;
}

contains方法

调用node方法，根据返回结果决定是否包含

public boolean contains(E element) {
    return node(element) != null;
}

二叉搜索树#

接口设计#

树节点类#

节点非空检查#

节点比较方法#

方法1：Comparable#

方法2：Comparator#

Comparable的弊端

最佳实践#

新问题

添加方法#

遇到相等节点怎么办？

无等值测试#

等值测试#

前驱节点#

后继节点#

info

删除方法#

删除叶子节点#

删除度为1的节点#

删除度为2的节点#

info

clear方法#

contains方法#

二叉搜索树

接口设计

树节点类

节点非空检查

节点比较方法

方法1：Comparable

方法2：Comparator

最佳实践

添加方法

无等值测试

等值测试

前驱节点

后继节点

删除方法

删除叶子节点

删除度为1的节点

删除度为2的节点

clear方法

contains方法