现在你知道如何使用二叉搜索树了，如果愿意的话，可以继续去学习更多关于树的知识。
BST存在一个问题：取决于你添加的节点数，树的一条边可能会非常深；也就是说，树的一条分支会有很多层，而其他的分支却只有几层，如下图所示：
这会在需要在某条边上添加、移除和搜索某个节点时引起一些性能问题。为了解决这个问题，有一种树叫作Adelson-Velskii-Landi树（AVL树）。AVL树是一种自平衡二叉搜索树，意思是任何一个节点左右两侧子树的高度之差最多为1。也就是说这种树会在添加或移除节点时尽量试着成为一棵完全树。
8.6.1 Adelson-Velskii-Landi树（AVL树）
AVL树是一种自平衡树。添加或移除节点时，AVL树会尝试自平衡。任意一个节点（不论深度）的左子树和右子树高度最多相差1。添加或移除节点时，AVL树会尽可能尝试转换为完全树。
在AVL树中插入节点
在AVL树中插入或移除节点和BST完全相同。然而，AVL树的不同之处在于我们需要检验它的平衡因子，如果有需要，则将其逻辑应用于树的自平衡。
下面的代码是向AVL树插入新节点的例子：
var insertNode = function(node, element) { if (node === null) { node = new Node(element); } else if (element < node.key) { node.left = insertNode(node.left, element); if (node.left !== null) { // 确认是否需要平衡 {1} } } else if (element > node.key) { node.right = insertNode(node.right, element); if (node.right !== null) { // 确认是否需要平衡 {2} } } return node;};然而，插入新节点时，还要检查是否需要平衡树（行
{1}和行{2}）。计算平衡因子
在AVL树中，需要对每个节点计算右子树高度（hr）和左子树高度（hl）的差值，该值（hr－hl）应为0、1或-1。如果结果不是这三个值之一，则需要平衡该AVL树。这就是平衡因子的概念。
下图举例说明了一些树的平衡因子（所有的树都是平衡的）：
计算节点高度的代码如下：
var heightNode = function(node) { if (node === null) { return -1; } else { return Math.max(heightNode(node.left), heightNode(node.right)) + 1; }};因此，向左子树插入新节点时，需要计算其高度；如果高度大于1（即不为-1、0和1之一），就需要平衡左子树。代码如下：
// 替换insertNode方法的行{1}if ((heightNode(node.left) - heightNode(node.right)) > 1) { // 旋转 {3}}向右子树插入新节点时，应用同样的逻辑，代码如下：
// 替换insertNode方法的行{2}if ((heightNode(node.right) - heightNode(node.left)) > 1) { // 旋转 {4}}AVL旋转
向AVL树插入节点时，可以执行单旋转或双旋转两种平衡操作，分别对应四种场景。
右-右（RR）：向左的单旋转
左-左（LL）：向右的单旋转
左-右（LR）：向右的双旋转
右-左（RL）：向左的双旋转
我们依次看看它们是如何工作的。
**右-右（RR）：向左的单旋转**如下图所示：假设向AVL树插入节点90，这会造成树失衡（节点50 -Y高度为-2），因此需要恢复树的平衡。下面是我们执行的操作：* 与平衡操作相关的节点有三个（X、Y、Z），将节点X置于节点Y（平衡因子为-2）所在的位置（行`{1}`）；* 节点X的右子树保持不变；* 将节点Y的右子节点置为节点X的左子节点Z（行`{2}`）；* 将节点X的左子节点置为节点Y（行`{3}`）。下面的代码举例说明了整个过程：
var rotationRR = function(node) { var tmp = node.right; // {1} node.right = tmp.left; // {2} tmp.left = node; // {3} return tmp; };**左-左（LL）：向右的单旋转**如下图所示：假设向AVL树插入节点5，这会造成树失衡（节点50 -Y高度为+2），需要恢复树的平衡。下面是我们执行的操作：* 与平衡操作相关的节点有三个（X、Y、Z），将节点X置于节点Y（平衡因子为+2）所在的位置（行`{1}`）；* 节点X的左子树保持不变；* 将节点Y的左子节点置为节点X的右子节点Z（行`{2}`）；* 将节点X的右子节点置为节点Y（行`{3}`）。下面的代码举例说明了整个过程：
var rotationLL = function(node) { var tmp = node.left; // {1} node.left = tmp.right; // {2} tmp.right = node; // {3} return tmp; };**左-右（LR）：向右的双旋转**如下图所示：假设向AVL树插入节点35，这会造成树失衡（节点50 -Y高度为+2），需要恢复树的平衡。下面是我们执行的操作：* 将节点X置于节点Y（平衡因子为+2）所在的位置；* 将节点Y的左子节点置为节点X的右子节点；* 将节点Z的右子节点置为节点X的左子节点；* 将节点X的右子节点置为节点Y；* 将节点X的左子节点置为节点Z。基本上，就是先做一次RR旋转，再做一次LL旋转。
下面的代码举例说明了整个过程： var rotationLR = function(node) { node.left = rotationRR(node.left); return rotationLL(node); };**右-左（RL）：向左的双旋转**如下图所示：假设向AVL树插入节点75，这会造成树失衡（节点70 -Y高度为-2），需要恢复树的平衡。下面是我们执行的操作：* 将节点X置于节点Y（平衡因子为-2）所在的位置；* 将节点Z的左子节点置为节点X的右子节点；* 将节点Y的右子节点置为节点X的左子节点；* 将节点X的左子节点置为节点Y；* 将节点X的右子节点置为节点Z。基本上，就是先做一次LL旋转，再做一次RR旋转。
下面的代码举例说明了整个过程： var rotationRL = function(node) { node.right = rotationLL(node.right); return rotationRR(node); };完成
insertNode方法确认树需要平衡后，就需要对每种情况分别应用正确的旋转。
向左子树插入新节点，且节点的值小于其左子节点时，应进行LL旋转。否则，进行LR旋转。该过程的代码如下：
// 替换insertNode方法的行{1}if ((heightNode(node.left) - heightNode(node.right)) > 1){ // 旋转 {3} if (element < node.left.key){ node = rotationLL(node); } else { node = rotationLR(node); }}向右子树插入新节点，且节点的值大于其右子节点时，应进行RR旋转。否则，进行RL旋转。该过程的代码如下：
// 替换insertNode方法的行{2}if ((heightNode(node.right) - heightNode(node.left)) > 1){ // 旋转 {4} if (element > node.right.key){ node = rotationRR(node); } else { node = rotationRL(node); }}
8.6.2 更多关于二叉树的知识
尽管AVL树是自平衡的，其插入或移除节点的性能并不总是最好的。更好的选择是红黑树。
红黑树可以高效有序地遍历其节点（http://goo.gl/OxED8K）。本书不打算讲解红黑树，但也提供了它的源代码。
如果感兴趣的话，你还可以了解堆积树（http://goo.gl/SFlhW6）。