二叉搜索树的定义

二叉搜索树（二叉排序树）的定义：根节点比左子树的所有节点都大，比右节点的所有节点的值都小
插入有序节点，退化成单支树
1.查找效率最好O(logn)，最坏O(n)
2.插入效率和查找效率相同（只插入叶子节点）
3.删除效率最好O(logn)+O(1)->只有左子树或者右子树
最差O(logn)+O(logn)->左子树和右子树同时存在
将一个有序的数组，构建为一颗二叉搜索树

public class BinarySearchTree<T> {
    TreeNode<T> root;
    public BinarySearchTree(T[] arr){
        root=createBinarySearchTree(arr,0,arr.length-1);
    }
    
    /**
     * 
     * @param arr
     * @param left
     * @param right
     * @return
     *<p>Description:从有序的数组中构造一颗二叉搜索树 </p>
     */
    public TreeNode<T> createBinarySearchTree(T[] arr,int left,int right){
        if(left>right){
            return null;
        }
        
        int mid=left+(right-left)/2;
        
        //int mid=(left+right)/2;
        TreeNode<T> root=new TreeNode(arr[mid]);
        
        root.left=createBinarySearchTree(arr, left, mid-1);
        root.right=createBinarySearchTree(arr, mid+1, right);
        return root;
        
    }
}