二叉查找树

二叉查找树是二叉树中最常用的一种类型，也叫二叉查找树。
二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

查找操作

先取根节点，如果它等于要查找的数据，直接返回。
如果要查找的数据比根节点的值小，那就在左子树中递归查找；
如果要查找的数据比根节点的值大，那就在右子树中递归查找。

查找

public class BinarySearchTree {
    private Node tree;
    public Node select(int data) {
        Node p = tree;
        while(p != null) {
            if(data < p.data) 
                p = p.left;
            else if (data > p.data)
                p = p.right;
            else
                return p;
        }
        return null;
    }
    public class Node {
        private int data;
        private Node left;
        private Node right;
        public Node(int data) {
            this.data = data;
        }
    }
}

插入操作

插入类似查找，新插入的数据一般都是在叶子节点上，只需要从根节点开始，依次比较要插入的数据和节点的大小关系。

如果要插入的数据比节点的数据大，并且节点的右子树为空，就将新数据直接插到右子节点的位置；
如果不为空，就在递归遍历右子树，查找插入位置。
同理，如果要插入的数据比节点数据小，并且节点的左子树为空，就将新数据插入到左子节点的位置；
如果不为空，就再递归遍历左子树，查找插入位置。

插入

public class BinarySearchTree {
    private Node tree;
    //不考虑插入节点与已有节点相同的情况
    public void insert(int data) {
        if(tree == null) {
            tree = new Node(data);
            return;
        }
        Node p = tree;
        while (p != null) {
            if(data > p.data) {
                if(p.right == null) {
                    p.right = new Node(data);
                    return;
                }
                p = p.right;
            } else {//data < p.data
                if(p.left == null) {
                    p.left = new Node(data);
                    return;
                }
                p = p.left;
            }
        }
    }
    public class Node {
        private int data;
        private Node left;
        private Node right;
        public Node(int data) {
            this.data = data;
        }
    }
}

删除操作

针对要删除节点的子节点个数的不同，需要分为三种情况处理：

1. 要删除的节点没有子节点，只需要直接将父节点中，指向要删除节点的指针置为null。
2. 要删除的节点只有一个子节点(只有左子节点或者右子节点)，只需要更新父节点中，指向要删除节点的指针，让它指向要删除结点的子节点。
3. 要删除的节点有两个子节点。需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上，然后再删除掉这个最小节点，因为最小节点肯定没有左子节点(如果有左子节点，那就不是最小节点了)，所以可以应用这两条规则来删除这个最小节点。

删除

public class BinarySearchTree {
    private Node tree;
    public void delete(int data) {
        //p指向要删除的节点，初始化指向根节点
        Node p = tree;
        //pp记录的是p的父节点
        Node pp = null;
        while(p != null && p.data != data) {
            //更新当前节点为父节点，进而遍历子节点、子子节点
            pp = p;
            if(data > p.data)
                p = p.right;
            else //data < p.data
                p = p.left;
        }
        //没有找到
        if(p == null)
            return;
        //要删除的节点有两个子节点
        if(p.left != null && p.right != null) {
            //查找右子树中最小节点
            Node minP = p.right;
            //minPP表示minP的父节点
            Node minPP = p;
            while(minP.left != null) {
                //更新当前最小节点为当前节点的左子节点
                minPP = minP;
                minP = minP.left;
            }
            //将minP的数据替换到p中，后续通过minPP(pp)删除原minP
            p.data = minP.data;
            p = minP;
            pp = minPP;
        }
        //删除的节点是叶子节点或者仅有一个子节点
        Node child;//p的子节点
        if(p.left != null)
            child = p.left;
        else if(p.right != null)
            child = p.right;
        else
            child = null;
        //通过更新父节点的子节点来删除指定的p
        if(pp == null) //删除的节点是根节点
            tree = child;
        else if(pp.left == p)
            pp.left = child;
        else //pp.right == p
            pp.right = child;
    }
    public class Node {
        private int data;
        private Node left;
        private Node right;
        public Node(int data) {
            this.data = data;
        }
    }
}

其他操作

快速的查找最大节点和最小节点、前驱节点和后继节点。

重要特性

中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度是O(n)。

重复数据

实际开发中，二叉查找树中存储的是包含很多字段的对象，利用对象的某个字段作为键值来构建二叉查找树，对象中的其他字段叫做卫星数据。

键值相同的两个对象存储解决方案：

1. 二叉查找树中每个节点不仅存储一个数据，通过链表和支持动态扩容的数组等数据结构，把值相同的数据都存储在同一个节点上。

2. 每个节点仍然只存储一个数据。在查找插入位置的过程冲，如果 碰到一个节点的值与要插入数据的值相同，把这个新插入的数据当做大于这个节点的值来处理，将新数据放到这个节点的右子树。

   当要查找数据的时候，遇到值相同的节点，并不停止查找操作，而是继续在右子树中查找，直到遇到叶子节点才停止。这样可以把键值等于要查找值的所有节点都找出来。

   对于删除操作，也需要先查找到每个要删除的节点，然后再按之前的删除操作的方法依次删除。

时间复杂度

二叉查找树的插入、删除、查找的时间复杂度都跟树的高度成正比，为O(height)。也就是求包含n个节点的完全二叉树的高度。树的高度等于最大层数减一。

最坏情况：二叉查找树退化为链表，查找的时间复杂度为O(n)。

最好情况：二叉查找树为完全二叉查找树。
包含n个节点的完全二叉树，第一层包含1个节点，第二层包含2个节点，第三层包含4个节点，依次类推，下面一层节点个数是上一层的2倍，第k层包含的节点个数就是2^K-1。
完全二叉树最后一层的节点个数在1个到2^L-1之间(最大层数为L)。则

n >= 1+2+4+8+…+2^L-2+1
n <= 1+2+4+8+…+2^L-2+2^L-1

等比数列求和公式，L的范围是[log₂(n+1),log₂n+1]。完全二叉树的层数小于log₂n+1，完全二叉树的高度小于log₂n。平衡二叉查找树的高度接近logn，插入、删除、查找操作的时间复杂度稳定为O(logn)。

对比散列表

• 散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序。二叉查找树只需要中序遍历，就可以在O(n)的时间复杂度内输出有序的数据序列。
• 散列表扩容耗时多，遇到散列冲突时性能不稳定。二叉查找树的性能不稳定，但平衡二叉查找树的性能非常稳定，时间复杂度稳定在O(logn)。
• 散列表的查找等操作的时间复杂度是常量级的，但是哈希冲突存在&哈希函数耗时，不一定比平衡二叉查找树的效率高。
• 散列表的构造比二叉查找树要复杂，需要考虑的额东西很多，散列函数、冲突解决、扩容、缩容等。平衡二叉查找树只需要考虑平衡性。
• 为了避免散列冲突，装载因子不能太大，基于开放寻址法解决冲突的散列表，会浪费一定的存储空间。