基于树的查找--------------平衡二叉查找树 平衡

yuyang911220

一,分析平衡二叉查找树有什么意义？

           平衡二叉查找树是对二叉查找树的改进，那二叉查找树哪些地方是不尽人意的呢？

        在分析二叉查找树的平均查找长度时，会发现，二叉查找树的平均查找长度与二叉查找树

        的形态有关系，最坏的情况是退化为链表，查找变为线性查找，平均查找长度为(n 1)/2.最
        好的情况就是树的形态与折半查找的判断树形式。平均查找长度为logN。
       

        平衡二叉树就是为了保证树的形态向“树”的方向走。避免了二叉查找树退化为链表的可能。

        从而提高了查找效率。其实平衡二叉查找树与二叉查找树的区别并不是很大，平衡树在“改变”
        树的时候会维护树的形态，“改变”无非就两种，插入节点和删除节点，而树的查找只“读”
        了树，并没改变，所以树的查找，平衡树和查找树是一样的。
        例如：
       

        现在我要使用24,12,53,28,45,90创建查找树，如果创建的二叉查找树（如左图），
        则平均查找长度：(1 2 2 3 4 3)/6 = 15/6 如果创建的是平衡二叉查找树(如右图)，
        则平均查找长度：(2 3 2 3 1 3)/6 = 14/6. 平衡二叉树的查找效率要高，
        这个例子是借用上次使用的，可能代表性不是强。
        ----------------------------------------------------------------

        二，平衡二叉查找树相关的重要概念。


        1，什么是平衡二叉查找树？



        平衡二叉查找树又称为平衡二叉排序树，又称为AVL树，是二叉查找树的改进。
     定义（满足如下三个条件）：
           (1),是二叉查找树。
           (2),左子树与右子树的深度之差的绝对值小于或等于1.
           (3),左右子树也是平衡二叉查找树。


        2，什么是平衡因子？

        平衡二叉查找树的每个结点都要描述一个属性，就是平衡因子，


它表示结点的左子树深度与右子树深度之差。


        该概念的引入也是为了更好地描述什么是平衡二叉查找树。有了这概念后。
        我们可以重新对二叉查找树下个定义。

        如果某个二叉查找树的所有节点的平衡因子只有-1,0,1则说明其实平衡的，
        否则说明是不平衡的。
-------------------------------------------------------------------
三，平衡二叉查找树是如何创建和插入的？如何保证插入一个新节点后树仍然是
        一棵平衡二叉查找树？

        先介绍几个特殊的节点。

        插入一个新的节点，只有该节点的祖先节点的平衡因子会变化，其他节点的
        平衡因子都不会变化。

       
如上图，插入15这个节点后，平衡因子变化的只有20,25,40。都是15的“祖先节点”。

       
A节点：为插入点最底层“祖先节点”最可能的失衡点。比如插入的节点是15，故插入的位置是节点20的左孩子，这从20这个节点开始遍历祖先节点，取最近的的最可能失衡点，
这儿就是40这个节点。如果没有找到，说明插入这个节点不可能破坏平衡
B节点就是该祖先节点一条线中A节点的下一个。

这两个特殊的点很重要，因为后面的失衡类型就是根据这两个点的平衡因子来判断的。







       
插入节点很简单，主要就是插入节点后有可能破坏平衡，那就必须将非平衡的树调整为平衡树。

        现在将非平衡的情况分为四种，每种情况都有自己的调整方法。