二叉搜索树：中序遍历序列是有序的。
二叉查找树，也称有序二叉树，是指一棵空树或者具有以下性质的二叉树：
左子节点的值比父节点小右子节点的值比父节点大任意节点的左右字树也分别为二叉查找树没有键值相等的点
在理想情况下，二叉查找树增删改查的时间复杂度为O(logN)；
二叉搜索树的查找
使用递归！如果key小于当前节点，向当前节点的左子树往下进行递归查找！如果key大于当前节点，向当前节点的右子树往下进行递归查找！临界条件是，当递归到节点为null都没有找到时则返回。
二叉搜索树的插入
插入时首先看当前key存不存在，存在的话返回，不存在的话插入！
将一个数组转换成二叉搜索树的结构！
首先数组第一个节点作为根节点！后面的节点小于根节点则向作为根节点的左孩子，反之作为右孩子。
二叉树的删除
难点在于：查找到要删除的key之后，删除！但是删除之后如何依旧保持二叉搜索树的特性！？
如果要删除的节点只有左子树或者右子树的话，那很容易，直接将删除节点的字树填补到删除节点！结果依然是BST！
如果要删除的节点既有左子树又有右子树，怎么办？
思路是：在左右子树中找到能够代替删除节点的节点，填补到删除位之后，依然保持BST特性！！！
其实也就是找到删除节点在BST中序遍历的直接前驱节点或者直接后继节点！！！用此两个节点中的一个来替换删除节点！
因此：分为3种情况！
1）删除的节点是叶子节点
2）删除的节点只有左子树或者右子树
3）删除的节点既有左子树又有右子树
//伪代码Status Delete(TreeNode root){TreeNode q = new TreeNode ();TreeNode s = new TreeNode ();//只有左子树if(root.right == null){q = root;root = root.left;q.clear();}//只有右子树else if(root.left == null){q = root;root = root.right;q.clear();} //既有左子树又有右子树else{q = p;s = p.left;while(s.right!=null){q = s;s = s.right;}p.val = s.val;//走到这里，s已经没有右子树了if(q!=p) q.right = s.left;//s左子节点即为叶子节点else q.left = s.left;s.clear();}return true;}
二叉树的查找复杂度
但是若是二叉树极度不平衡，形成了一个线性链后（左斜树或者右斜树），就会产生最坏运行情况O(N)。
基于BST存在的问题，平衡二叉树产生了，典型的有AVL树和红黑树，因为AVL是严格的平衡二叉树，但是插入和删除的性能较差，所以在实际生产环境中不如红黑树应用广泛。
平衡二叉树 AVL
维持BST的logn复杂度
定义：
平衡二叉树定义(AVL)：它或者是一颗空树，或者具有以下性质的二叉树：
前提，平衡二叉树是一个二叉搜索树
它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树。
平衡因子(bf)：结点的左子树的深度减去右子树的深度，那么显然-1<=bf<=1
平衡二叉树的实现原理
在构建二叉搜索树的过程中，每当我们插入一个新的节点的时候，先检查插入节点是否破坏了树的平衡性！如果破坏了，找出最小不平衡树，在保证二叉搜索树的的前提下，调整最小不平衡字树种各节点的连接关系，进行相应的旋转，使之成为新的平衡树！
BF 平衡因子
当最小不平衡树的根节点和其子节点的BF符号相同时：BF为负，左旋，BF为正，右旋。一次旋转！
当最小不平衡树的根节点和其子节点的BF符号不同时：先将他们的BF符号统一，再遵循 BF为负，左旋，BF为正，右旋。也即是进行两次旋转！
