1 Binary Search Tree

1.1 概念

二叉查找树，又称二叉排序树（Binary Sort Tree）即BST

二叉搜索树作为一种经典的数据结构
它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；
所以应用十分广泛，例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作

定义如下：
一棵空树，或者是具有下列性质的二叉树：

• 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
• 左、右子树也分别为二叉排序树；
• 没有键值相等的结点。

二叉查找树示例如下：

1.2 原理

一棵二叉搜索树是以二叉树来组织的，可以使用一个链表数据结构来表示，其中每一个结点就是一个对象。
一般地，除了key和位置数据之外，每个结点还包含属性lchild、rchild和parent，分别指向结点的左孩子、右孩子和双亲（父结点）
如果某个孩子结点或父结点不存在，则相应属性的值为空（null）。
根结点是树中唯一父指针为null的结点，而叶子结点的孩子结点指针也为null

1.3 时间复杂度

不论哪一种操作，所花的时间都和树的高度成正比。因此，如果共有n个元素，那么平均每次操作需要O(logⁿ)的时间

1.4 操作

查找

查找操作和二分查找类似，实现代码参见 contains

• 将key和节点的key比较，
• 如果小于，那么就在Left Node节点查找【递归查找】
• 如果大于，则在Right Node节点查找【递归查找】
• 如果相等，直接返回Value
• 如果找不到，则返回null或一个默认值

插入

插入和查找类似，首先查找有没有和key相同的，如果有，更新；如果没有找到，那么创建新的节点，
实现代码参见 insert

查找最大/最小值

递归查找根节点的右/左节点，直到最后一个右/左节点，
实现代码参见 findMax / findMin

Floor和Ceiling

查找floor(key) 的值 即前驱节点: 所有<=key的最大值，
查找ceiling(key) 的值 即 后驱节点: 所有>=key的最小值
实现代码参见 floor、ceiling

删除

分为以下几种情况：

• 叶子节点：直接删除，不影响原树
• 仅仅有左或右子树的节点：节点删除后，将它的左子树或右子树整个移动到删除节点的位置就可以，子承父业
• 既有左又有右子树的节点：找到须要删除的节点p的直接前驱或者直接后继s，用s来替换节点p，然后再删除节点s
  • 前驱结点:在中序遍历中，一个节点的前驱结点，先找到该节点的左孩子节点，再找左孩子节点的最后一个右孩子节点。向左走一步，然后向右走到头。最后一个右孩子节点即为前驱节点
  • 后继节点：在中序遍历中，一个节点的后继结点，先找到该节点的右孩子节点，再找右孩子节点的最后一个左孩子节点。向右走一步，然后向左走到头。最后一个左孩子节点即为前驱节点

代码参见 remove

toString函数

使用递归，先打印根节点，然后打印左节点，再打印右节点，节点以 (父节点的值)节点的值 形式表示

源码示例

测试示例

class Main{
    public static void main(String[] args) throws Exception {
        BinarySearchTree<Integer> tree = new BinarySearchTree<Integer>();
        tree.insert(10);
        tree.insert(5);
        tree.insert(14);
        tree.insert(4);
        tree.insert(1);
        tree.insert(6);
        tree.insert(11);
        tree.insert(18);

        System.out.println(tree.findMax());
        System.out.println(tree.findMin());
        System.out.println(tree.contains(5));
        System.out.println(tree.floor(9));
        System.out.println(tree.ceiling(12));
        System.out.println(tree);
        tree.remove(10);
        System.out.println(tree);
        tree.remove(5);
        System.out.println(tree);
    }
}

程序运行结果如下，符合预期
18
1
true
6
14
10 ,(10)5 ,(5)4 ,(4)1 ,(5)6 ,(10)14 ,(14)11 ,(14)18
11 ,(11)5 ,(5)4 ,(4)1 ,(5)6 ,(11)14 ,(14)18
11 ,(11)6 ,(6)4 ,(4)1 ,(11)14 ,(14)18

完整二叉搜索树代码

public class BinarySearchTree<T extends Comparable> {

    BinaryNode root = null;

    /**
     * 插入数据
     *
     * @param data
     */
    public void insert(T data) {
        root = insert(data, root);
    }

    /**
     * 删除数据
     *
     * @param data
     * @throws Exception
     */
    public void remove(T data) throws Exception {
        if (root != null) {
            root = remove(data, root);
        }
    }

    /**
     * 查找数据，如果存在，返回true,否则返回false
     *
     * @param data
     * @return
     */
    public boolean contains(T data) {
        return contains(data, root);
    }

    /**
     * 找最小值
     *
     * @return
     * @throws Exception
     */
    public T findMin() throws Exception {
        if (isEmpty()) {
            throw new Exception();
        }
        BinaryNode<T> node = findMin(root);
        return node.data;
    }

    /**
     * 找最大值
     *
     * @return
     * @throws Exception
     */
    public T findMax() throws Exception {
        if (isEmpty()) {
            throw new Exception();
        }
        BinaryNode<T> node = findMax(root);
        return node.data;
    }

    /**
     * 查找Floor(key)的值就是所有<=key的最大值
     *
     * @param key
     * @return
     */
    public T floor(T key) {
        BinaryNode<T> node = floor(root, key);
        if (node != null) {
            return node.data;
        } else {
            return null;
        }
    }

    /**
     * 查找Ceiling(key)的值就是所有>=key的最小值
     *
     * @param key
     * @return
     */
    public T ceiling(T key) {
        BinaryNode<T> node = ceiling(root, key);
        if (node != null) {
            return node.data;
        } else {
            return null;
        }
    }

    @Override
    public String toString() {
        return toString(root);
    }

    private String toString(BinaryNode<T> node) {
        if (node == null) {
            return "";
        } else {
            StringBuffer sb = new StringBuffer();
            sb.append(node.data);
            if (node.left != null) {
                sb.append("," + toString(node.left));
            }

            if (node.right != null) {
                sb.append("," + toString(node.right));
            }
            return sb.toString();
        }
    }

    private boolean isEmpty() {
        return root == null ? true : false;
    }

    private BinaryNode<T> insert(T data, BinaryNode<T> node) {
        if (node == null) {
            return new BinaryNode(data, null, null);
        }
        int compareResult = data.compareTo(node.data);
        if (compareResult < 0) {
            node.left = insert(data, node.left);
        } else if (compareResult > 0) {
            node.right = insert(data, node.right);
        } else {
            // 值相等，do nothing
        }
        return node;
    }

    private boolean contains(T data, BinaryNode<T> node) {
        if (node == null) {
            return false;
        }
        int compareResult = data.compareTo(node.data);
        if (compareResult < 0) {
            return contains(data, node.left);
        } else if (compareResult > 0) {
            return contains(data, node.right);
        } else {
            return true;
        }
    }

    //递归实现
    private BinaryNode<T> findMin(BinaryNode<T> node) {
        if (node == null) {
            return null;
        } else if (node.left == null) {
            return node;
        } else {
            return findMin(node.left);
        }
    }

    private BinaryNode<T> findMax(BinaryNode<T> node) {
        if (node != null) {
            while (node.right != null) {
                node = node.right;
            }
        }
        return node;
    }

    /**
     * 查找Floor(key)的值就是所有<=key的最大值
     *
     * @param node
     * @param key
     * @return
     */
    private BinaryNode floor(BinaryNode<T> node, T key) {
        if (node == null) {
            return null;
        }
        int cmp = key.compareTo(node.data);
        if (cmp == 0) {
            return node;
        } else if (cmp < 0) {
            return floor(node.left, key);
        } else {
            BinaryNode<T> right = floor(node.right, key);
            if (right == null) {
                return node;
            } else {
                return right;
            }
        }
    }

    /**
     * 查找Ceiling(key)的值就是所有>=key的最小值
     *
     * @param node
     * @param key
     * @return
     */
    private BinaryNode ceiling(BinaryNode<T> node, T key) {
        if (node == null) {
            return null;
        }
        int cmp = key.compareTo(node.data);
        if (cmp == 0) {
            return node;
        }
        if (cmp > 0) {
            return ceiling(node.right, key);
        } else {
            BinaryNode<T> left = ceiling(node.left, key);
            if (left == null) {
                return node;
            } else {
                return left;
            }
        }
    }

    private BinaryNode<T> remove(T data, BinaryNode<T> node) {
        int res = data.compareTo(node.data);
        //查找节点
        if (res < 0) {
            node.left = remove(data, node.left);
        } else if (res > 0) {
            node.right = remove(data, node.right);
        } else {
            //找到节点进行处理
            if (node.left != null && node.right != null) {
                //找到右节点的最小节点
                node.data = findMin(node.right).data;
                //移除右节点的最小节点
                node.right = remove(node.data, node.right);
            } else {
                //待删除节点，不存在左节点时，直接将待删除节点置为左节点
                node = (node.left != null) ? node.left : node.right;
            }
        }
        return node;
    }

    private static class BinaryNode<T extends Comparable> {
        T data;
        BinaryNode<T> left;
        BinaryNode<T> right;

        public BinaryNode(T data) {
            this(data, null, null);
        }

        public BinaryNode(T data, BinaryNode<T> left, BinaryNode<T> right) {
            this.data = data;
            this.left = left;
            this.right = right;
        }
    }
}