之前简单了解过 AVL 树，知道概念但一直没动手实践过。Now
 
 AVL 树是二叉搜索树的一种。二叉搜索树的规则就是：每个节点的 left child 都比自己小，right child 都比自己大。而 AVL 的在此之上又加了一个规则：每个节点的 left 深度与 right 深度只差<=1，这样就能充分利用 二叉树的结构，避免出现一个分支走到黑，导致搜索效率变低。如下图：
                                             
                                这种树结构，搜索起来完全没有体现出二叉搜索树的优势
 
所以同样多的元素，搜索树的深度越低，就会越快的定位到搜索点。
 
AVL 树为了保持树的平衡，每次插入、删除都会检查 每个受影响的节点，深度差是否 <  1。最难的部分就是如果树失衡，如何调整节点。插入的处理流程大致如下：
     给定一个 value，一路比较直到插入到某个位置。然后查找哪些节点因此而失衡，针对第一个失衡的节点进行旋转。
 
下面是我从另一个博客上找来的图（http://blog.csdn.net/gabriel1026/article/details/6311339），介绍了四种失衡的情况，以及调整方式：
注：图中红色的小块 表示新插入的元素，A 点表示从插入点向上，发现的第一个失衡的点。
 
      AVL树的旋转一共有四种情形，注意所有旋转情况都是围绕着使得二叉树不平衡的第一个节点展开的。

我想了解如何学习

姓名：
手机：
留言：