如果向一棵预先排序的树输入数据，那么一连串Insert操作将花费二次时间，而链表实现的代价会非常巨大，因为此时的树将只由哪些没有左儿子的节点组成。一种解决办法就是要有一个称为平衡（balance）的附加的结构条件：任何节点的深度均不得过深。有许多一般的算法实现平衡树，本节后面讨论最老的一种平衡查找树，即AVL树。
另外较新的方法是放弃平衡条件，允许树有任意深度，但是在每次操作之后要使用一个调整规则进行调整，使得后面的操作效率更高。这种类型的数据结构一般属于自调整（self-adjusting）类结构 。在二叉查找树的情况下，对于任意单个运算我们不在保证O(logN)的时间界，但是可以证明任意连续M次在最坏情形下花费O(MlogN)。一般这足以防止令人棘手的最坏情形。本节后面讨论的这种数据结构叫做伸展树（Splay Tree）。
AVL(Adelson Velskii和Landis)树是带有平衡条件的二叉查找树。这个平衡条件必须容易保持，而且它须保证树的深度是O(logN) 。最简单的想法如下图1所示左右子树具有相同高度。
另一种平衡条件是要求每个节点都必须要有相同高度的左子树和右子树。虽然这种平衡条件保证了树的深度小，但是它太严格，难以使用，需要放宽条件。
一棵AVL树是其每个节点的左子树和右子树的高度最多差1的二叉查找树。空树的高度定为-1。可以证明，大致上讲，一个AVL树的高度最多为1.44log(N+2) - 1.328，但是实际上高度只比logN稍微多一些。
因此，除去可能的插入外（我们将假设懒惰删除），所有的树操作都可以以时间O(logN)执行。当进行插入操作时，我们需要更新通向根节点路径上哪些节点的所有平衡信息，而插入操作隐含着困难的原因在于，插入一个节点可能破坏AVL树的特性。发生这种情况，那么就要把性质恢复以后才认为这一步插入完成。事实上，这个总可以通过对树进行简单的修正来做到，我们称为旋转（rotation）。
在插入以后，只有那些从插入点到根节点的路径上的节点的平衡可能被改变，因为只有这些节点的子树可能发生改变。当我们沿着这条路径上行到根并更新平衡信息时，我们可以找到一个节点，它的新平衡破坏了AVL条件。我们将指出如何在第一个这样的节点（即最深的节点）重新平衡这棵树，并证明，这一重新平衡保证整个树满足AVL特性。
让我们把必须重新平衡的节点叫做α 。由于任意节点最多有两个儿子，因此高度不平衡时，α 点的两棵子树的高度差2。容易看出，这种不平衡可能出现在下面四种情况中:
- 对α 的左儿子的左子树进行一次插入。
- 对α 的左儿子的右子树进行一次插入。
- 对α 的右儿子的左子树进行一次插入。
- 对α 的右儿子的右子树进行一次插入。
情形1和情形4是关于α 点的镜像对称，而2和3是关于α 节点的镜像对称。因此，理论上只有两种情况，当然从编程的角度来看还是四种情形。
第一种情况是插入发生在“外边”的情况（即左-左或者右-右的情况），该情况通过对树的一次单旋转（single rotation）而完成调整。第二种情况是插入发生在“内部”的情形（即左-右或者右-左的情况），该情况通过稍微复杂些的双旋转（double rotation）来处理。我们将会看到，这些都是对树的基本操作，它们多次用于平衡树的一些算法中。
上图显示单旋转如何调整情形1。
抽象的形容就是：把树形象的看成是柔软灵活的，抓住节点k_1 ，闭上你的双眼，使劲的摇动它，在重力的作用下，k_1 就变成了新的根。二叉查找树的性质告诉我们，在原树中k_2 > k_1 ，于是在新树中k_2 变成了k_1 的右儿子，X和Z仍然分别是k_1 的左儿子和k_2 的右儿子。
情形4代表一种对称的情形。上图指出单旋转如何使用。
上面描述的算法有一个问题：如下图所示，对于情形2和情形3上面的做法无效。问题在于子树Y太深，单旋转没有降低它的深度。解决这问题的双旋转在下图中给出。
为了重新平衡，我们看到不能再让k_3 作为根了，而图4-34所示的在k_3 和k_1 之间的旋转又解决不了问题，惟一的选择就是把k_2 用作新的根。容易看出，最后得到的树满足AVL树的特性，与单旋转的情形一样，我们也把树的高度恢复到插入以前的水平，这就保证所有的重新平衡和高度更新是完善的。
为将关键字是X的一个新节点插入到一棵AVL树中去，我们递归地将X插入到T的相应的子树（称为TLR ）中。如果TLR 的高度不变，那么插入完成。否则，如果T中出现高度不平衡，那么我们根据X以及T和TLR 中的关键字做适当的单旋转或双旋转，更新这些高度（并解决好与树的其余部分的连接），从而完成插入。由于一次旋转总能足以解决问题，因此仔细地编写非递归的程序一般来说要比编写递归程序快很多。然而，要想把非递归程序编写正确是相对困难的。
另一种效率问题涉及到高度信息的存储。。由于真正需要的实际上就是子树高度的差，应该保证它很小。
伸展树（splay tree）,它保证从空树开始任意连续M次对树的操作最多花费O（MlogN）时间。
伸展树的基本想法是，当一个节点被访问后，它就要经过一系列AVL的旋转被放到根上。注意，如果一个节点很深，那么在其路径上就存在许多的节点也相对较深，通过重新构造可以使对所有这些节点的进一步访问所花费的时间变少。因此，如果节点过深，那么我们还要求重新构造应具有平衡这棵树（到某种程度）的作用。
实施上面描述的重新的构造的一种方法是执行单旋转，从下向上进行。这意味着我们将在访问路径上的每个节点和它们的父节点实施旋转。
虽然这个策略使得对k1 的访问花费时间减少，但是它并没有明显地改变（原先）访问路径上其他节点的状况。事实上可以证明，对于这种策略将会存在一系列M个操作共需要Ω (M*N)的时间，因此这个想法不够好。
展开（Splaying）的思路类似于前面介绍的旋转的想法，不过在旋转如何实施上我们稍微有些选择的余地。
我们仍然从底部向上沿着访问路径旋转。令X是在访问路径上的一个（非根）节点，我们将在这个路径上实施旋转操作。如果X的父节点是树根，那么我们只要旋转X和树根。这就是沿着访问节点上的最后的旋转。否则，X就有父亲（P）和祖父（G）,存在两种情况以及对称的情形要考虑。第一种情况是之字型（zig-zag）情形（见图1）。这里，X是右儿子的形式，P是左儿子的形式（反之亦然）。如果是这种情况，我们就执行一次像AVL那样的双旋转。否则，出现另一种一字型（zig-zig）情形：X和P或者都是左儿子，或者都是右儿子。在这种情况下，我们把下图2左边的树变换成右边的树。
虽然从一些小例子很难看出来，但是展开操作不仅将访问的节点移动到根处，而且还把访问路径上大部分节点的深度大致减少一半的效果（某些浅的节点最多向下推后两个层次）。
我们可以通过访问要删除的节点实行删除操作。这种操作将节点上推到根处。如果删除该节点，则得到两棵子树TL 和TR （左子树和右子树）。如果我们找到TL 中最大的元素，那么这个元素就被旋转到TL 的根下，而此时TL 将有一个没有右儿子的根。我们可以是TR 为右儿子从而结束删除。
当访问路径太长而导致超出正常查找时间的时候，这些旋转将对未来的操作有益。当访问耗时很少的时候，这些旋转不那么有益甚至有害。对伸展树的分析很困难，因为树的结构经常变化。另一方面，伸展树的编程要比AVL树简单得多，这是因为要考虑的情形少并且没有平衡信息需要存储。
本节介绍了AVL树要求所有节点的左子树与右子树的高度相差最多是1。这就保证了树不至于太深。
在伸展树中的节点可以达到任意深度，但是在每次访问之后树又以多少有些神秘的方式被调整。实际效果是，任意M次操作花费O（MlogN）时间，它与平衡树花费的时间相同。