二叉查找树，也称二叉搜索树，或二叉排序树。其定义也比较简单，要么是一颗空树，要么就是具有如下性质的二叉树：
（1）若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2） 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3） 任意节点的左、右子树也分别为二叉查找树；
（4） 没有键值相等的节点。
如上图所示，是不同形态的二叉查找树。二叉查找树是对要查找的数据进行生成树，左支的值小于右支的值。在查找的时候也是一样的思路，从根节点开始，比节点大进入右支，比节点小进入左支，直到查找到目标值。
二叉查找树的插入算法比较简单：空树，就首先生成根节点；不是空树就按照查找的算法，找到父节点，然后作为叶子节点插入，如果值已经存在就插入失败。
删除操作稍微复杂一点，有如下几种情况：
（1）如果删除的是叶节点，可以直接删除；
（2）如果被删除的元素有一个子节点，可以将子节点直接移到被删除元素的位置；
（3）如果有两个子节点，这时候就采用中序遍历，找到待删除的节点的后继节点，将其与待删除的节点互换，此时待删除节点的位置已经是叶子节点，可以直接删除。如下图：
将待删除节点与后继节点互换，变成如下图所示：
将待删除元素删除，如下图所示：
另外，二叉查找树还有一个性质，即对二叉查找树进行中序遍历，即可得到有序的数列。
二叉查找树的查询复杂度，和二分查找一样，插入和查找的时间复杂度均为 O(logn) ，但是在最坏的情况下仍然会有 O(n) 的时间复杂度。原因在于插入和删除元素的时候，树没有保持平衡（如上不同形态的二叉树图中的b）。
平衡二叉树
平衡二叉搜索树，又被称为AVL树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。 —-来自百度百科
由于普通的二叉查找树会容易失去”平衡“，极端情况下，二叉查找树会退化成线性的链表，导致插入和查找的复杂度下降到 O(n) ，所以，这也是平衡二叉树设计的初衷。那么平衡二叉树如何保持”平衡“呢？根据定义，有两个重点，一是左右两子树的高度差的绝对值不能超过1，二是左右两子树也是一颗平衡二叉树。
如下图所示，左图是一棵平衡二叉树，根节点10，左右两子树的高度差是1，而右图，虽然根节点左右两子树高度差是0，但是右子树15的左右子树高度差为2，不符合定义，所以右图不是一棵平衡二叉树。
由此可以看出平衡二叉树是一棵高度平衡的二叉查找树。所以，要构建跟维系一棵平衡二叉树就比普通的二叉树要复杂的多。在构建一棵平衡二叉树的过程中，当有新的节点要插入时，检查是否因插入后而破坏了树的平衡，如果是，则需要做旋转去改变树的结构。
关于旋转，这东西不拿动态图将还真很难讲明白。所以我就借一下 最容易懂得红黑树 这篇文章中左旋右旋的图来讲。
左旋：
右旋：
不同于顺时针跟逆时针变换这种方式去记忆，上面两个动态图特别方便记忆跟理解：
左旋就是将节点的右支往左拉，右子节点变成父节点，并把晋升之后多余的左子节点出让给降级节点的右子节点；
而右旋就是反过来，将节点的左支往右拉，左子节点变成了父节点，并把晋升之后多余的右子节点出让给降级节点的左子节点。
即左旋就是往左变换，右旋就是往右变换。不管是左旋还是右旋，旋转的目的都是将节点多的一支出让节点给另一个节点少的一支。