数据结构 | 二叉搜索树BinarySearchTree

数据结构 | 二叉搜索树BinarySearchTree

二叉搜索树 Binary Search Tree

  • 任意一个节点的值都大于其左子树所有节点的值
  • 任意一个节点的值都小于其右子树所有节点的值
  • 任意一个节点的左右子树也是一棵二叉搜索树
  • 要求二叉搜索树所存储的值必须具备可比较性
    • 例如 int,double,String等
    • 如果是自定义类型,需要指定比较方式(实现 Comparable 接口或者传入 Comparator对象)
    • 不循序存储 null 值

二叉搜索树

实现 Binary Search Tree

1. 属性

  • BST 并不需要索引属性
  • 为了提高代码的适应性,这里不强制要求存储的元素 E 必须实现 Comparable 接口
public class BinarySearchTree<E> {
    // 存储元素的数量
    private int size;

    // 根节点
    private Node<E> root;

    // 添加元素时使用的比较器
    private Comparator<E> comparator;

    // 节点内部类,除了存储的元素,还保存父节点和左右子节点
    private static class Node<E> {
        E ele;
        Node<E> right;
        Node<E> left;
        Node<E> parent;

        // Node 的构造方法传入存储的元素值和其父节点,因为一般来说节点都会有父节点,但是不一定有子节点
        public Node (E ele,Node<E> parent) {
            this.ele = ele;
            this.parent = parent;
        }

        public boolean hasTwoChildren() {
            return left!=null && right!=null;
        }
    }
}

2. 构造器

// 不传入 Comparator 比较器时的构造方法
public BinarySearchTree() {
    this(null);
}

// 传入 Comparator 比较器的构造方法
public BinarySearchTree(Comparator<E> comparator) {
    this.comparator = comparator;
}

3. 添加元素

注意,具体的比较值大小的逻辑不可以在 BST 内写死,而是交给使用 BST 的人去处理

//添加元素的方法
public void add(E ele) {
    // 先进行判空,BST不允许存储 null
    elementNotNullCheck(ele);
    // 如果添加的是第一个节点
    if(root==null) {
        root = new Node<>(ele,null);
        size++;
        return;
    }
    // 添加的不是第一个节点
    Node<E> parent = root;
    Node<E> node = root;
    // 比较的结果值
    int cmp = 0;
    // 循环直到找到可以存放新元素的节点,即 node==null时
    while(node!=null) {
        // 记录比较的结果值
        cmp = compare(ele,node.ele);
        // 在转向左右子节点之前先记录父节点
        parent = node;
        if(cmp>0) {
            node = node.right;
        }else if(cmp<0) {
            node = node.left;
        }else {
            // 如果相等,覆盖之前的元素
            node.ele = ele;
            return;
        }
    }
    // 根据最后一次比较的结果,插入到父节点的左或右子节点
    if(cmp>0) {
        parent.right = new Node<>(ele,parent);
    }else {
        parent.left = new Node<>(ele,parent);
    }
    size++;
}

// 判空方法,如果存入 null 则抛异常
private void elementNotNullCheck(E ele) {
    if(ele==null) {
        throw new IllegalArgumentException("element must not be null!");
    }
}

// 比较两个元素,如果ele1>ele2返回正整数,如果ele1<ele2返回负整数,如果相等返回0
private int compare(E ele1,E ele2) {
    // 如果创建BST时传入了指定的比较器
    if(comparator!=null) {
        // 直接返回比较器的 ccompare() 方法的结果
        return comparator.compare(ele1,ele2);
    }
    // 创建BST时没有传入指定的比较器,则默认使用所存储元素实现的 Comparable 接口的 compareTo() 方法
    // 这里先将 ele1 强制转换成 Comparable 类型,若果 E 类没有实现 Comparable 接口则会抛出类型转换异常
    // 提醒用户要存储的元素必须是可比较的
    return ((Comparable<E>)ele1).compareTo(ele2);
}

删除元素

  • 删除元素需要找到节点的前驱(predecessor)或者后继(successor)
  • 根据删除元素所在节点的情况,可以分为:删除度为 0 的节点(叶子)、删除度为 1 的节点、删除度为 2 的节点
  • 删除度为 0 的节点:直接删除并修改父节点指向子节点的指针
  • 删除度为 1 的节点:不可以直接删除,因为不可以改变二叉搜索树的结构和性质,需要用子节点代替要删除的节点
  • 删除度为 2 的节点
    • 用前驱(或后继)节点的值覆盖要删除节点的值(注意是值覆盖,而不是直接直接删除该节点)
    • 删除前驱(或后继)节点
    • 注意:对于度为 2 的节点,其前驱或后继节点的度必然为 0 或 1
// 对于外部调用者,删除的是元素
public void remove(E ele) {
    // 对于BST内部是删除节点
    remove(node(ele));
}

// 根据元素找到节点
private Node<E> node(E ele) {
    Node<E> node = root;
    int cmp;
    while(node!=null) {
        cmp = compare(ele,node.ele);
        if(cmp==0) return node;
        if(cmp>0) {
            node = node.right;
        }else {
            node = node.left;
        }
    }
    return null;
}

private void remove(Node<E> node) {
    if(node==null) return;
    // 必然要删除一个节点
    size--;

    // 对于度为0或1的节点直接跳过
    if(node.hasTwoChildren()) { // 度为2
        // 找到前驱节点,也可以找后继节点
        Node<E> p = predecessor(node);
        // 值覆盖
        node.ele = p.ele;
        // 将实际要删除的前驱或后继(度为0或1)的节点赋给node变量
        node = p;
        // 之后的代码负责删除node节点即可
    }

    // 此时node节点的度必然为 0 或 1

    Node<E> replacement = node.left!=null ? node.left : node.right;

    if(replacement!=null) { // node度为1
        replacement.parent = node.parent;
        if(node.parent==null) { // node是度为1的根节点
            root = replacement;
        }else if(node==node.parent.left) { // node度为1、不是根节点、是左子节点
            node.parent.left = replacement;
        }else { // node度为1、不是根节点、是右子节点
            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.parent.right = null;
        }
    }
}

其他方法

public int size() {
    return size;
}

public boolean isEmpty() {
    return size==0;
}

public void clear() {
    root = null;
    size = 0;
}

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

二叉搜索树的复杂度分析

二叉搜索树的搜索、添加、删除操作的复杂度与树的高度相关,复杂度可以表示为 $O(h)$,如果一棵二叉搜索树按照合理的顺序添加元素,例如按照 7、4、9、2、5、8、11的顺序,此时二叉搜索树是一棵满二叉树,搜索、添加、删除操作的复杂度为 $O(logN)$ 级别

二叉搜索树的复杂度

但是,一些添加、删除操作可能使二叉搜索树退化为链表,此时的复杂度上升到 $O(N)$,对于 $N$ 很大的情况,二者性能差异会很大

二叉树的遍历

  • 遍历操作不是二叉搜索树特有的,而是针对所有二叉树
  • 前中后序遍历可以使用递归或者迭代两种方式实现,层序遍历一般借助队列实现(非递归)

递归函数会到达一个节点三次,会记录整个过程中的状态

非递归为什么使用栈,遍历二叉树实际上是从上至下的过程,但是过程中需要回到上面,需要一个栈记录

前序遍历

前序遍历的访问顺序为:根节点、前序遍历整棵左子树、前序遍历整棵右子树

前序遍历

递归实现

// 前序遍历的对外接口
public void preorderTraversal() {
    preorderTraversal(root);
}
// 前序遍历打印二叉树节点的内容
private void preorderTraversal(Node<E> node) {
    if(node==null) return;
    // 先访问根节点
    System.out.println(node.ele);
    // 前序遍历访问左子树
    preorderTraversal(node.left);
    // 前序遍历访问右子树
    preorderTraversal(node.right);
}

非递归实现

public void preorderTraversalWithStack2() {
    Stack<Node<E>> stack = new Stack<>();
    // 先将根节点入栈
    if(root!=null) stack.push(root);
    // 循环至栈空
    while(!stack.isEmpty()) {
        // 弹栈并操作
        Node<E> node = stack.pop();
        System.out.println(node.ele);
        // 右不为空,先压右
        if(node.right!=null) stack.push(node.right);
        // 左不为空,再压左
        if(node.left!=null) stack.push(node.left);
    }
}

中序遍历

  • 中序遍历的访问顺序为:中序遍历整棵左子树、根节点、中序遍历整棵右子树
  • 对于二叉搜索树,如果进行中序遍历打印,则打印顺序是按元素升序(先左后右)或降序(先右后左)的

中序遍历

递归实现

// 中序遍历的对外接口
public void inorderTraversal() {
    inorderTraversal(root);
}
// 中序遍历打印二叉树节点的内容
private void inorderTraversal(Node<E> node) {
    if(node==null) return;
    // 先中序遍历左子树
    inorderTraversal(node.left);
    // 访问根节点
    System.out.println(node.ele);
    // 最后中序遍历右子树
    inorderTraversal(node.right);
}

非递归实现

public void inorderTraversalWithStack() {
    Stack<Node<E>> stack = new Stack<>();
    Node<E> node = root;
    while(!stack.isEmpty() || node!=null) {
        if(node!=null) {
            // 一路向左,将节点压入栈中
            stack.push(node);
            node = node.left;
        }else {
            // 取出栈顶访问
            node = stack.pop();
            System.out.println(node.ele);
            // 向右
            node = node.right;
        }
    }
}

后序遍历

  • 后序遍历的访问顺序为:后序遍历整棵左子树、后序遍历整棵右子树、根节点
  • 对于一些需要先子后父的操作,可以使用后序遍历

后序遍历

递归实现

// 后序遍历的对外接口
public void postorderTraversal() {
    postorderTraversal(root);
}
// 后序遍历打印二叉树节点的内容
private void postorderTraversal(Node<E> node) {
    if(node==null) return;
    // 先后序遍历左子树
    postorderTraversal(node.left);
    // 再后序遍历右子树
    postorderTraversal(node.right);
    // 最后访问根节点
    System.out.println(node.ele);
}

非递归实现

使用两个栈实现后序遍历:修改前序遍历的顺序根节点->右子树->左子树,然后访问节点的行为(例如打印)修改为将节点压入另外一个辅助栈,最后将辅助栈中的节点弹出进行访问,最终的访问顺序即左子树->右子树->根节点

public void postorderTraversalWithTwoStack() {
    Stack<Node<E>> s1 = new Stack<>();
    Stack<Node<E>> s2 = new Stack<>();
    if(root!=null) s1.push(root);
    while(!s1.isEmpty()) {
        Node<E> node = s1.pop();
        // 弹出栈顶节点,压入辅助栈
        s2.push(node);
        // 先左后右,与前序遍历相反
        if(node.left!=null) s1.push(node.left);
        if(node.right!=null) s1.push(node.right);
    }
    while(!s2.isEmpty()) {
        System.out.println(s2.pop().ele);
    }
}

层序遍历

  • 层序遍历即对二叉树从上到下、从左到右依次访问每一个节点
// 层序遍历打印二叉树节点的内容
public void levelOrderTraversal() {
    if(root==null) return;
    Queue<Node<E>> queue= new LinkedList<>();
    queue.offer(root);
    while(!queue.isEmpty()) {
        // 队头节点出队,打印,再将其左右子节点依次入队
        Node<E> node = queue.poll();
        System.out.println(node.ele);
        if(node.left!=null) queue.offer(node.left);
        if(node.right!=null) queue.offer(node.right);
    }
}

优化遍历接口

以上对四种遍历的实现仅仅是在访问节点时打印存储的内容,实际应用中,需求不仅仅局限于打印节点,可能会有对节点的各种操作,但是这些操作不能写死在数据结构内部,而是由外部,也就是数据结构的调用者实现。所以,可以考虑对外提供一个访问器接口或抽象类,外部调用者如果要使用不同的二叉树遍历方式对节点进行操作,必须传入一个访问器实例并实现 visit() 方法以指明如和操作。

实现访问器

public static abstract class Visitor<E> {
    // 接受并记录 visit() 方法的返回值
    private boolean stop;
    public abstract boolean visit(E ele);
}

public void preorderTraversal(Visitor<E> visitor) {
    if(visitor==null) return;
    preorderTraversal(visitor,root);
}

private void preorderTraversal(Visitor<E> visitor,Node<E> node) {
    if(node==null || visitor.stop) return;
    visitor.stop = visitor.visit(node.ele);
    preorderTraversal(visitor,node.left);
    preorderTraversal(visitor,node.right);
}

public void inorderTraversal(Visitor<E> visitor) {
    if(visitor==null) return;
    inorderTraversal(visitor,root);
}

private void inorderTraversal(Visitor<E> visitor,Node<E> node) {
    if(node==null || visitor.stop) return;
    inorderTraversal(visitor,node.left);
    if(visitor.stop) return;
    visitor.stop = visitor.visit(node.ele);
    inorderTraversal(visitor,node.right);
}

public void postorderTraversal(Visitor<E> visitor) {
    if(visitor==null) return;
    postorderTraversal(visitor,root);
}

private void postorderTraversal(Visitor<E> visitor,Node<E> node) {
    if(node==null || visitor.stop) return;
    postorderTraversal(visitor,node.left);
    postorderTraversal(visitor,node.right);
    if(visitor.stop) return;
    visitor.stop = visitor.visit(node.ele);
}

public void levelOrderTraversal(Visitor<E> visitor) {
    if(root==null || visitor==null) return;
    Queue<Node<E>> queue = new LinkedList<>();
    queue.offer(root);
    while(!queue.isEmpty()) {
        Node<E> node = queue.poll();
        if(visitor.visit(node.ele)) return;
        if(node.left!=null) queue.offer(node.left);
        if(node.right!=null) queue.offer(node.right);
    }
}

外界调用访问器

// 构建一棵二叉搜索树
BinarySearchTree<Integer> bst = new BinarySearchTree<>();
Integer[] testArr = {7,4,2,1,3,5,9,8,11,10,12};
for(int i=0;i<testArr.length;i++) {
    bst.add(testArr[i]);
}
// 匿名内部类实现visit()方法
bst.preorderTraversal(new BinarySearchTree.Visitor<Integer>() {
    @Override
    public boolean visit(Integer ele) {
        System.out.println(ele);
        // 停止遍历的条件:存储元素为5时
        return ele.equals(5);
    }
});

二叉树节点的前驱和后继

前驱节点 predecessor

前驱节点即中序遍历时该节点的前一个节点。所以,对于二叉搜索树,前驱节点必定为前一个比该节点小的节点。

前驱节点

确定前驱节点需要分不同的情况

  1. 左子树不为空

    • predecessor = node.left.right.right....
    • 终止条件:right 为空
    • 先向左,再一路向右
    • 例如节点6,13,8
  2. 左子树为空,父节点不为空

    • predecessor = node.parent.parent.parent....
    • 终止条件:parent 为空或已确定 node 在父节点或祖父节点的右子树中
    • 这种情况也可能无前驱节点(例如节点1,不在任一祖父节点的右子树中)
    • 例如节点7,11,9
  3. 左子树为空,父节点为空

    • 无前驱节点
    • 例如无左子树的根节点
protected Node<E> predecessor (Node<E> node) {
    if(node == null) return null;
    if(node.left!=null) {
        Node<E> p = node.left;
        // 有左子树,先向左,再一路向右
        while(p.right!=null) {
            p = p.right;
        }
        return p;
    }else {
        // 从父节点、祖父节点中寻找前驱节点
        Node<E> p = node.parent;
        // 对于无左子树且无父节点的node不会进入循环,直接返回parent,即null,相当于合并了情况2和3
        while(p.parent!=null && p==p.parent.left) {
            p = p.parent;
        }
        return p.parent;
    }
}

后继节点 successor

后继节点即中序遍历时该节点的后一个节点。所以,对于二叉搜索树,后继节点必定为后一个比该节点大的节点。

后继节点.png

确定后继节点需要分不同的情况

  1. 右子树不为空
    • successor = node.right.left.left.left....
    • 终止条件:left为空
    • 先向右,再一路向左
    • 例如节点1,4
  2. 右子树为空,父节点不为空
    • successor = node.parent.parent.parent....
    • 终止条件:parent 为空或已确定 node 在父节点或祖父节点的左子树中
    • 这种情况也可能无后继节点(例如节点11)
    • 例如节点3,6,7
  3. 右子树为空,父节点为空
    • 无后继节点
      *例如无右子树的根节点
protected Node<E> successor (Node<E> node) {
    if(node==null) return null;
    if(node.right!=null) {
        Node<E> p = node.right;
        // 有右子树,先向右,再一路向左
        while(p.left!=null) {
            p = p.left;
        }
        return p;
    }else {
        // 从父节点、祖父节点中寻找后继节点
        Node<E> p = node.parent;
        // 对于无右子树且无父节点的node不回进入循环,直接返回parent,即null,相当于合并了情况2和3
        while(p.parent!=null && p==p.parent.right) {
            p = p.parent;
        }
        return p;
    }
}

参考