一步一步写平衡二叉树

《一步一步写平衡二叉树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一步一步写平衡二叉树（AVL树）一步一步写平衡二叉树（AVL树）作者：C小加更新时间：2012-8-20　　平衡二叉树（BalancedBinaryTree）是二叉查找树的一个进化体，也是第一个引入平衡概念的二叉树。1962年，G.M.Adelson-Velsky和E.M.Landis发明了这棵树，所以它又叫AVL树。平衡二叉树要求对于每一个节点来说，它的左右子树的高度之差不能超过1，如果插入或者删除一个节点使得高度之差大于1，就要进行节点之间的旋转，将二叉树重新维持在一个平衡状态。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况

2、都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。　　平衡二叉树实现的大部分过程和二叉查找树是一样的（学平衡二叉树之前一定要会二叉查找树），区别就在于插入和删除之后要写一个旋转算法去维持平衡，维持平衡需要借助一个节点高度的属性。我参考了机械工业出版社的《数据结构与算法分析-C语言描述》写了一个C++版的代码。这本书的AVLTree讲的很好，不过没有很完整的去描述。我会一步一步的讲解如何写平衡二叉树，重点是平衡二叉树的核心部分，也就是旋转算法。第一步：节点信息　　相对于二叉查找树的节点来说，我们需要用一个属

3、性二叉树的高度，目的是维护插入和删除过程中的旋转算法。代码如下：//AVL树节点信息templateclassTreeNode{public:TreeNode():lson(NULL),rson(NULL),freq(1),hgt(0){}Tdata;//值inthgt;//以此节点为根的树的高度unsignedintfreq;//频率TreeNode*lson;//指向左儿子的地址TreeNode*rson;//指向右儿子的地址};第二步：平衡二叉树类的声明　　声明中的旋转函数将在后边的步骤中详解。代码如下：//AVL树类的属性和方法声明template

4、assT>classAVLTree{private:TreeNode*root;//根节点voidinsertpri(TreeNode*&node,Tx);//插入TreeNode*findpri(TreeNode*node,Tx);//查找voidinsubtree(TreeNode*node);//中序遍历voidDeletepri(TreeNode*&node,Tx);//删除intheight(TreeNode*node);//求树的高度voidSingRotateLeft(TreeNode*&k2);//左左情况下的旋转

5、voidSingRotateRight(TreeNode*&k2);//右右情况下的旋转voidDoubleRotateLR(TreeNode*&k3);//左右情况下的旋转voidDoubleRotateRL(TreeNode*&k3);//右左情况下的旋转intMax(intcmpa,intcmpb);//求最大值public:AVLTree():root(NULL){}voidinsert(Tx);//插入接口TreeNode*find(Tx);//查找接口voidDelete(Tx);//删除接口voidtraversal();//遍历接口};第

6、三步：两个辅助方法　　旋转算法需要借助于两个功能的辅助，一个是求树的高度，一个是求两个高度的最大值。这里规定，一棵空树的高度为-1，只有一个根节点的树的高度为0，以后每多一层高度加1。为了解决指针NULL这种情况，写了一个求高度的函数，这个函数还是很有必要的。代码如下：//计算以节点为根的树的高度templateintAVLTree::height(TreeNode*node){if(node!=NULL)returnnode->hgt;return-1;}//求最大值templateintAVLTree::Max(intcmp

7、a,intcmpb){returncmpa>cmpb?cmpa:cmpb;}第四步：旋转　　对于一个平衡的节点，由于任意节点最多有两个儿子，因此高度不平衡时，此节点的两颗子树的高度差2.容易看出，这种不平衡出现在下面四种情况：　　1、6节点的左子树3节点高度比右子树7节点大2，左子树3节点的左子树1节点高度大于右子树4节点，这种情况成为左左。　　2、6节点的左子树2节点高度比右子树7节点大2，左子树2节点的左子树1节点高度小于右子树4节点，这种情况成为左右。　　3、2节点的左子树1节点高度比