如何构造二叉排序树（平衡二叉树）
如何构造二叉排序树（平衡二叉树）按照[5 1 3 9 13 8]这样的顺序构建二叉树，顺序是这样的：二叉查找树的结构与值的插入顺序有关，同一组数，若其元素的插入顺序不同，二叉搜索树的结构是千差万别的。举个例子，给出一组数[1 3 5 8 9 13]。图1 典型的二叉查找树假设我们想要查找节点7，先到达根节点，它的值大小为6；7比6大，继续往右子树上找，到达8；7比8小，往左子树上查找，最终找到7。二叉查找树可以使插入、搜索的效率大大提高，为什么还要发明平衡二叉树这一数据结构？
平衡二叉树是在二叉查找树（二叉查找树（BST：Binary Search Tree） ）的基础上发展而来的。
平衡二叉树(AVL树)，指的是左子树上的所有节点的值都比根节点的值小，而右子树上的所有节点的值都比根节点的值大，且左子树与右子树的高度差最大为1。所以，平衡二叉树满足所有二叉排序（搜索）树的性质。而名字AVL，则是取自两个发明平衡二叉树的科学家的名字：G. M. Adelson-Velsky和E. M. Landis。
一个新的数据结构不是凭空产生的，我们先看一下二叉查找树的作用。有了二叉查找树这一数据结构，当你要查找一个值，就不需要遍历整个序列或者说遍历整棵树了，可以根据当前遍历到的结点的值来确定搜索方向。这种思维在搜索中被叫做“剪枝”，把不必要的分枝剪掉可以提高搜索效率。在二叉查找树中查找值，每次都会把搜索范围缩小，与二分搜索的思维类似。
举例看一下下图所示二叉查找树：
图1 典型的二叉查找树
假设我们想要查找节点7，先到达根节点，它的值大小为6；7比6大，继续往右子树上找，到达8；7比8小，往左子树上查找，最终找到7。
二叉查找树可以使插入、搜索的效率大大提高，为什么还要发明平衡二叉树这一数据结构？
二叉查找树的结构与值的插入顺序有关，同一组数，若其元素的插入顺序不同，二叉搜索树的结构是千差万别的。举个例子，给出一组数[1 3 5 8 9 13]。
按照[5 1 3 9 13 8]这样的顺序构建二叉树，顺序是这样的：
图2 二叉查找树的构建
如果按照[1 3 5 8 9 13]这样的顺序构建二叉树，得到的二叉树如下图：
图3 二叉树的构建
可以看出图3构建的二叉树已经变成一个链表了，想要查找节点13，时间复杂度很大，相当于遍历链表。图3 与图2 的区别在于，构建二叉树的序列接近有序了。也就是说越有序的数列构建的二叉树越像链表。
为了避免构建得 二叉树变成了链表，引入了新的数据结构，就是平衡二叉树。核心思想是让树的结构看起来尽量均匀，左右树的节点数尽量一样多。
我们的重点就是，给定一个序列，这个序列本身没有顺序，我们需要频繁的查找、插入、删除，如何保证它的效率。只要维护由它构建的二叉树是平衡二叉树即可。
如何构建一颗平衡的二叉树？先按照二叉查找树的方法构造二叉树，如果这个二叉树变得不平衡，具体表现为：左子树和右子树的高度差大于1。我们就把它调整为平衡二叉树。如何调整不平衡的二叉树为平衡二叉树：
- 找到插入导致二叉树不平衡的节点位置
- 使用四种调整方法：LL（右旋） RR（左旋） LR （先右旋再左旋）RL（先左旋再右旋）
为了方便对上面所说调整不平衡二叉树的方法的近一步研究，提取几个相关概念出来：
平衡因子（BF-Bnlance Factor）：将二叉树上节点的左子树高度减去右子树高度的值。
最小不平衡子树：距离插入节点最近的，且平衡因子绝对值大于1的节点为根的子树。
图4 最小不平衡子树
插入节点3以后，该节点的又BF = 1变为BF = 2。导致该二叉树不再平衡，找到导致该树不平衡的节点3，使用四种调整方法对它进行调整。具体调整方法下一篇文章学习。
漫谈递归、迭代、循环——人理解迭代，神理解递归
当我们说递归时，到底是在说什么
如何优雅地画好二叉树
二叉树遍历的思维导图
二叉树的层序遍历及应用
二叉查找树（BST：Binary Search Tree）
Graphviz Dot 语法介绍
