二分搜索树拾遗

二分搜索树拾遗

假设我们需要在一个有序的数组内，查找一个数，那么首先想到使用二分搜索的方法。二分搜索具有非常优秀的时间复杂度O(logN)，这在许多算法中都会优先使用。
如果情况变得再复杂些，有一个无序的数组，我们应该使用什么样的算法来查找其中某一项呢？

这时，可以考虑二分搜索树，一个符合期望的二分搜索树，其最小的深度为O(logN)，也就是说，我们同样可以用过O(logN)的时间复杂度来实现搜索操作。但这时不能忽略建立二分搜索树的时间复杂度O(n)，同样地，一颗平衡的二分搜索树才可以达到这种理想的时间复杂度。如果是最糟糕的情况，一颗二分搜索树会退化成一个链表，这种情况下，搜索的时间复杂度为增加为O(n)。但实际上，我们并不会在平凡地搜索上面考虑二分搜索树，但会运用在top-k情况中。

top-k情况，即从一组数组中，找出第k个大/小的元素。这里以找出第k个大的元素为例，由于二分搜索树右子树比root小，右子树的节点数量为m，那么root节点就是第m+1个大的元素。这可以用二分搜索树很好的完成。为了方便起见，需要在TreeNode中存放一个整数，用来保存整个以他为根结点的子树的个数。

具体算法代码如下：

public class KthLargest {
    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        int count = 1;
        public TreeNode(int val){
            this.val = val;
        }
    }
    private TreeNode root;
    private int rank;

    private void insertNode(TreeNode root, int val){
        if(root==null){
            root = new TreeNode(val);
            this.root = root;
            return;
        }

        //root must not be null
        if(root.val>val){
            if(root.left==null){
                root.left = new TreeNode(val);
                root.count++;
                return;
            }else{
                insertNode(root.left, val);
                root.count++;
            }
        }else if(root.val<=val){
            if(root.right==null){
                root.right = new TreeNode(val);
                root.count++;
                return;
            }else{
                insertNode(root.right, val);
                root.count++;
            }
        }
    }

    public KthLargest(int k, int[] nums) {
        this.rank = k;
        for(int i = 0; i<nums.length;i++){
            insertNode(root, nums[i]);
        }
    }
    private int findK(TreeNode root, int k){
        int count = 0;
        if(root.right!=null){
            count = root.right.count;
        }
        if(count<k){
            if(count+1==k){
                return root.val;
            }else{
                return findK(root.left, k-count-1);
            }
        }else{
            return findK(root.right, k);
        }
    }
    
    public int add(int val) {
        insertNode(root, val);
        var res = findK(root, rank);
        return res;
    }
}