乐趣区

关于数据结构与算法:Java数据结构与算法分析-二叉查找树BST

jiezi

GitHub 源码分享

我的项目主页：https://github.com/gozhuyinglong/blog-demos
本文源码：https://github.com/gozhuyinglong/blog-demos/tree/main/java-data-structures

1. 二叉查找树（Binary Search Tree）

二叉查找树又叫二叉排序树（Binary Sort Tree），或叫二叉搜寻树，简称 BST。BST 是一种节点值之间有秩序的二叉树。其个性是：

  • 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
  • 若任意节点的右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值；
  • 任意节点的左、右子树也别离为二叉查找树；

二叉查找树相比于其余数据结构的劣势在于查找、插入的工夫复杂度较低，为 $O(logN)$。用大 $O$ 符号示意的工夫复杂度：

算法 均匀 最差
空间 $O(N)$ $O(N)$
搜寻 $O(logN)$ $O(N)$
插入 $O(logN)$ $O(N)$
删除 $O(logN)$ $O(N)$

2. BST 的实现

二叉查找树要求所有的节点元素都可能排序，所以咱们的 Node 节点类须要实现 Comparable 接口，树中的两个元素能够应用 compareTo 办法进行比拟。
咱们节点中元素的类型为 int 型，所以该接口泛型为Comparable<Integer>，上面是具体实现：

2.1 节点类

  • element 为数据元素
  • left 为左子节点
  • right 为右子节点
class Node implements Comparable<Integer> {
    private final int element; // 数据元素
    private Node left; // 左子树
    private Node right; // 右子树

    private Node(Integer element) {this.element = element;}

    @Override
    public int compareTo(Integer o) {return o.compareTo(element);
    }
}

2.2 二叉查找树类

  • root 为树根，所有的操作均始于此

前面会在该类中减少其余办法，如增加、查找、删除等

class BinarySearchTree {private Node root; // 树根}

3. 插入节点

向二叉查找树中插入的节点总是叶子节点，插入过程如下：

  1. 若 root 为空，则将插入节点设为root
  2. 以后元素与插入元素通过 compareTo 进行比拟，若插入元素值小，并且左子节点 left 为空，则插入至以后节点左子节点；否则持续递归
  3. 若插入元素值大，且右子节点 right 为空，则插入至以后节点右子节点；否则持续递归。
  4. 若插入元素等于以后节点元素，则插入失败。注：也能够将其插入到右子节点，我这里为了不便间接放弃插入。

具体实现：
在 BinarySearchTree 类中增加两个办法：

  • public boolean add(int element) 为公开办法
  • private boolean add(Node node, int element)为公有办法，外部 递归 应用
       // 增加元素
       public boolean add(int element) {if (root == null) {root = new Node(element);
                return true;
            }
            return add(root, element);
        }
        // 增加元素（递归）private boolean add(Node node, int element) {if (node.compareTo(element) < 0) {if (node.left == null) {node.left = new Node(element);
                    return true;
                } else {return add(node.left, element);
                }
            } else if (node.compareTo(element) > 0) {if (node.right == null) {node.right = new Node(element);
                    return true;
                } else {return add(node.right, element);
                }
            } else {return false;}
        }

4. 查找节点

通过二叉查找树查找元素，其过程如下：

  1. 若 root 为空，则查找失败
  2. 将以后元素与指标元素对比，若相等则查找胜利。
  3. 若不相等，则持续递归查找：若目标值小于以后节点值，则查找左子树；否则，查找右子树。

具体实现：
在 BinarySearchTree 类中增加两个办法：

  • public Node find(int element) 为公开办法
  • private Node find(Node node, int element) 为公有办法，外部 递归 应用
      // 查找元素
      public Node find(int element) {if (root == null) {return null;}
            return find(root, element);
        }

        // 查问元素（递归）private Node find(Node node, int element) {if (node == null) {return null;}
            int compareResult = node.compareTo(element);
            if (compareResult < 0) {return find(node.left, element);
            } else if (compareResult > 0) {return find(node.right, element);
            } else {return node;}
        }

5. 遍历节点

BST 是一个有序二叉树，通过中序遍历可程序输入树中节点。
中序遍历过程如下：

  1. 递归遍历左子节点
  2. 输入以后节点
  3. 递归遍历右子节点

具体实现：
在 BinarySearchTree 类中增加两个办法：

  • public void orderPrint() 为公开办法
  • private void orderPrint(Node node) 为公有办法，外部 递归 应用
      // 遍历节点
      public void orderPrint() {orderPrint(root);
        }

        // 遍历节点（递归）private void orderPrint(Node node) {if (node == null) {return;}

            // 递归左子节点
            if (node.left != null) {orderPrint(node.left);
            }

            // 输入以后节点
            System.out.println(node.element);

            // 递归右子节点
            if (node.right != null) {orderPrint(node.right);
            }

        }

6. 删除节点

删除节点最为复查，共有三种状况：

6.1 指标元素为叶子节点

叶子节点最容易删除，过程如下：

  1. 找到指标节点的父节点
  2. 判断指标节点是父节点的左子树还是右子树
  3. 若是左子树，将父节点的 left 设为空；否则将父节点的 right 设为空

6.2 指标元素即有左子树，也有右子树

该状况删除操作最为简单，过程如下：

  1. 找到指标节点的父节点
  2. 判断指标节点是父节点的左子树还是右子树
  3. 找到右子树中最小元素（叶子节点），将其赋给长期变量minNode，再将该元素从树中删除
  4. 将指标元素的属性赋予minNode。
  5. 若指标元素是父节点的左子树，将父节点的 left 设为 minNode；否则将父节点的right 设为minNode

6.3 指标元素只有左子树，或只有右子树

删除过程如下

  1. 找到指标节点的父节点
  2. 判断指标节点是父节点的左子树还是右子树
  3. 若是左子树，将父节点的 left 设为指标节点不为空的子树；否则将父节点的 right 设为指标节点不为空的子树

具体实现
在BinarySearchTree类中增加两个办法：

  • public boolean remove(int element) 为公开办法
  • private boolean remove(Node parentNode, Node node, int element)为公有办法，外部 递归 应用
      // 删除节点
      public boolean remove(int element) {if (root == null) {return false;}
            // 如果删除的元素是 root
            if (root.compareTo(element) == 0) {if (root.right == null) {root = root.left;} else {
                    root.right.left = root.left;
                    root = root.right;
                }
                return true;
            }
            return remove(null, root, element);
        }

        // 删除节点（递归）private boolean remove(Node parentNode, Node node, int element) {if (node == null) {return false;}
            // 先找到指标元素
            int compareResult = node.compareTo(element);
            if (compareResult < 0) {return remove(node, node.left, element);
            }
            if (compareResult > 0) {return remove(node, node.right, element);
            }

            // 找到指标元素，判断该节点是父节点的左子树还是右子树
            boolean isLeftOfParent = false;
            if (parentNode.left != null && parentNode.left.compareTo(element) == 0) {isLeftOfParent = true;}

            // 删除指标元素
            if (node.left == null && node.right == null) { //（1）指标元素为叶子节点，间接删除
                if (isLeftOfParent) {parentNode.left = null;} else {parentNode.right = null;}
            } else if (node.left != null && node.right != null) { //（2）指标元素即有左子树，也有右子树
                // 找到右子树最小值（叶子节点），并将其删除
                Node minNode = findMin(node.right);
                remove(minNode.element);
                // 将该最小值替换要删除的指标节点
                minNode.left = node.left;
                minNode.right = node.right;
                if(isLeftOfParent) {parentNode.left = minNode;} else {parentNode.right = minNode;}

            } else { //（3）指标元素只有左子树，或只有右子树
                if (isLeftOfParent) {parentNode.left = node.left != null ? node.left : node.right;} else {parentNode.right = node.left != null ? node.left : node.right;}
            }
            return true;
        }
    }

7. 残缺代码

该代码依据下图二叉查找树实现，其操作包含：增加、查找、遍历、删除、查问最小值、查问最大值。

public class BinarySearchTreeDemo {public static void main(String[] args) {BinarySearchTree tree = new BinarySearchTree();

        System.out.println("---------------------- 增加元素");
        Integer[] array = {5, 2, 7, 1, 4, 3, 7, 6, 9, 8};
        for (Integer element : array) {System.out.printf("增加元素[%s] --> %s\n", element, tree.add(element));
        }

        System.out.println("---------------------- 程序输入（中序遍历）");
        tree.orderPrint();

        System.out.println("---------------------- 查找元素");
        System.out.println(tree.find(7));

        System.out.println("---------------------- 查找最小元素");
        System.out.println(tree.findMin());

        System.out.println("---------------------- 查找最大元素");
        System.out.println(tree.findMax());

        System.out.println("---------------------- 是否蕴含元素");
        System.out.println("是否蕴含[0] --> \t" + tree.contains(0));
        System.out.println("是否蕴含[2] --> \t" + tree.contains(2));

        System.out.println("---------------------- 删除指标元素");
        System.out.println("删除[0] --> \t" + tree.remove(0));
        tree.orderPrint();
        System.out.println("删除[1] --> \t" + tree.remove(1));
        tree.orderPrint();
        System.out.println("删除[4] --> \t" + tree.remove(4));
        tree.orderPrint();
        System.out.println("删除[7] --> \t" + tree.remove(7));
        tree.orderPrint();}

    private static class BinarySearchTree {
        private Node root; // 树根

        /**
         * 增加元素
         *
         * @param element
         * @return
         */
        public boolean add(int element) {if (root == null) {root = new Node(element);
                return true;
            }
            return add(root, element);
        }

        /**
         * 增加元素（递归）*
         * @param node
         * @param element
         * @return
         */
        private boolean add(Node node, int element) {if (node.compareTo(element) < 0) {if (node.left == null) {node.left = new Node(element);
                    return true;
                } else {return add(node.left, element);
                }
            } else if (node.compareTo(element) > 0) {if (node.right == null) {node.right = new Node(element);
                    return true;
                } else {return add(node.right, element);
                }
            } else {return false;}
        }

        /**
         * 查问元素
         *
         * @param element
         * @return
         */
        public Node find(int element) {if (root == null) {return null;}
            return find(root, element);
        }

        /**
         * 查问元素（递归）*
         * @param node
         * @param element
         * @return
         */
        private Node find(Node node, int element) {if (node == null) {return null;}
            int compareResult = node.compareTo(element);
            if (compareResult < 0) {return find(node.left, element);
            } else if (compareResult > 0) {return find(node.right, element);
            } else {return node;}
        }

        /**
         * 查找最大值
         *
         * @return
         */
        public Node findMax() {return findMax(root);
        }

        /**
         * 查找最大值（递归）*
         * @param node
         * @return
         */
        private Node findMax(Node node) {if (node.right == null) {return node;}
            return findMax(node.right);
        }

        /**
         * 查找最小值
         *
         * @return
         */
        private Node findMin() {return findMin(root);
        }

        /**
         * 查找最小值（递归）*
         * @param node
         * @return
         */
        private Node findMin(Node node) {if (node.left == null) {return node;}
            return findMin(node.left);
        }

        /**
         * 程序输入
         */
        public void orderPrint() {orderPrint(root);
        }


        /**
         * 程序输入（递归）*
         * @param node
         */
        private void orderPrint(Node node) {if (node == null) {return;}

            // 递归左子节点
            if (node.left != null) {orderPrint(node.left);
            }

            // 输入以后节点
            System.out.println(node.element);

            // 递归右子节点
            if (node.right != null) {orderPrint(node.right);
            }

        }

        /**
         * 是否蕴含某值
         *
         * @param element
         * @return
         */
        public boolean contains(int element) {if (find(element) == null) {return false;}
            return true;
        }

        /**
         * 删除指标元素
         *
         * @param element
         * @return
         */
        public boolean remove(int element) {if (root == null) {return false;}
            // 如果删除的元素是 root
            if (root.compareTo(element) == 0) {if (root.right == null) {root = root.left;} else {
                    root.right.left = root.left;
                    root = root.right;
                }
                return true;
            }
            return remove(null, root, element);
        }

        /**
         * 删除指标元素（递归），有三种状况：*（1）指标元素为叶子节点
         *（2）指标元素即有左子树，也有右子树
         *（3）指标元素只有左子树，或只有右子树
         *
         * @param parentNode 以后节点的父节点
         * @param node       以后节点（若以后节点上的元素与要删除的元素匹配，则删除以后节点）* @param element    要删除的元素
         * @return
         */
        private boolean remove(Node parentNode, Node node, int element) {if (node == null) {return false;}
            // 先找到指标元素
            int compareResult = node.compareTo(element);
            if (compareResult < 0) {return remove(node, node.left, element);
            }
            if (compareResult > 0) {return remove(node, node.right, element);
            }

            // 找到指标元素，判断该节点是父节点的左子树还是右子树
            boolean isLeftOfParent = false;
            if (parentNode.left != null && parentNode.left.compareTo(element) == 0) {isLeftOfParent = true;}

            // 删除指标元素
            if (node.left == null && node.right == null) { //（1）指标元素为叶子节点，间接删除
                if (isLeftOfParent) {parentNode.left = null;} else {parentNode.right = null;}
            } else if (node.left != null && node.right != null) { //（2）指标元素即有左子树，也有右子树
                // 找到右子树最小值（叶子节点），并将其删除
                Node minNode = findMin(node.right);
                remove(minNode.element);
                // 将该最小值替换要删除的指标节点
                minNode.left = node.left;
                minNode.right = node.right;
                if(isLeftOfParent) {parentNode.left = minNode;} else {parentNode.right = minNode;}

            } else { //（3）指标元素只有左子树，或只有右子树
                if (isLeftOfParent) {parentNode.left = node.left != null ? node.left : node.right;} else {parentNode.right = node.left != null ? node.left : node.right;}
            }
            return true;
        }
    }

    private static class Node implements Comparable<Integer> {
        private final Integer element; // 数据元素
        private Node left; // 左子树
        private Node right; // 右子树

        private Node(Integer element) {this.element = element;}

        @Override
        public int compareTo(Integer o) {return o.compareTo(element);
        }

        @Override
        public String toString() {
            return "Node{" +
                    "element=" + element +
                    '}';
        }
    }
}

输入后果：

---------------------- 增加元素
增加元素[5] --> true
增加元素[2] --> true
增加元素[7] --> true
增加元素[1] --> true
增加元素[4] --> true
增加元素[3] --> true
增加元素[7] --> false
增加元素[6] --> true
增加元素[9] --> true
增加元素[8] --> true
---------------------- 程序输入（中序遍历）1
2
3
4
5
6
7
8
9
---------------------- 查找元素
Node{element=7}
---------------------- 查找最小元素
Node{element=1}
---------------------- 查找最大元素
Node{element=9}
---------------------- 是否蕴含元素
是否蕴含[0] -->     false
是否蕴含[2] -->     true
---------------------- 删除指标元素
删除[0] -->     false
1
2
3
4
5
6
7
8
9
删除[1] -->     true
2
3
4
5
6
7
8
9
删除[4] -->     true
2
3
5
6
7
8
9
删除[7] -->     true
2
3
5
6
8
9
退出移动版