HotBitmapGG#AndroidInterview#[数据结构] AVL树和AVL旋转、哈夫曼树和哈夫曼编码1

#1. AVL树 　　AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O（log n）。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。 　　节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要**重新平衡**这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。 ##１.２AVL旋转 　　AVL树的基本操作一般涉及运作同在不平衡的二叉查找树所运作的同样的算法。但是要进行预先或随后做一次或多次所谓的"AVL旋转"。 　　以下图表以 **四列** 表示四种情况，每行表示在该种情况下要进行的操作。在左左和右右的情况下，只需要进行一次旋转操作；在左右和右左的情况下，需要进行两次旋转操作。 > Root是失去平衡树的根节点，Pivot是旋转后重新平衡树的根节点  - 插入 　向AVL树插入，可�