感悟《数据结构与算法分析(C++描述)》中的一些超经典递归函数

在这里,我想感悟一下关于数据结构方面的经典著作《数据结构与算法分析(C++描述)》中的两个经典的递归函数。  

 

一、AVL树中的插入操作 

基本思想:由于AVL树是一种平衡树(每个节点的左右子树高度差不超过1),所以每进行一次插入操作,就有可能破坏AVL树的性质。当破坏性质之后就要进行相应的调整,调整的内容在这里我就不赘述了。

下面是作者:Mark Allen Weiss写的关于AVL树的插入函数: 

1.树节点的定义:

struct AVLNode
{
 T element;
 AVLNode* left; //左子树
 AVLNode* right; //右子树
 int height; //节点高度(节点的高度:节点的高度是指该节点到一片树叶的最长的路径长。)
 
 AVLNode(const T& eIn,AVLNode* lt = NULL,AVLNode* rt = NULL,int h = 0)
        :element(eIn),left(lt),right(rt),height(h) { }
};  

 

2.插入函数

/*x 是需要插入的数据项; t是子树的根;插入之后更新子树的根。*/
void insert(const T& x,AVLNode* & t)
{
     if(t == NULL)
        t = new AVLNode(x,NULL,NULL);//空节点
     else if(x < t -> element) //向左插入节点
     {
         insert(x,t -> left);

         if(height(t -> left) – height(t -> right) == 2) //如果破坏了AVL树的性质,进行相应调整
         {
              if(x < t -> left -> element)//向左儿子的左子树进行插入
                  rotateWithChild(t); //进行一次左单旋转
              else
                  doubleWithLeftChild(t);//进行一次左双旋转 
          }
     } 
     else if(x > t -> element) //向右插入节点
     {
          insert(x,t -> right);
         
          if(height(t -> right) – height(left) == 2) //破坏了AVL树性质
          {
              if(t -> right -> element < x) //向右儿子的右子树进行一次插入
                  rotateWithRightChild(t); //进行一次右单旋转
              else
                  doubleWithRightChild(t);//进行一次右双旋转 
          }
     }
     else //该树中已经存在该节点   
         ;      

    //更新节点高度 
     t -> height = max(height(t -> left),height(t -> right)) + 1;  

其他函数: 

(1)int max(int lhs,int rhs) //计算高度

{

     return lhs > rhs ?: rhs;

(2)int height(AVLNode* t) const //返回及节点的高度  

{

     return t == NULL ? -1:t -> height;

}   

(3)void rotateWithLeftChild(AVLNode* & k) //进行一次左单旋转

{

       AVLNode* k1 = k -> left;  

       k -> left = k1 -> right;

       k1 -> right = k;

       k -> height = max(height(k -> left),height(k -> right)) + 1;//更新根的高度   

       k1 -> height = max(height(k1 -> left),k2 -> height) + 1;//更新新根的高度

       k = k1; //新的根

(4)void doubleWithLeftChild(AVLNode* k) //进行左双旋转 

{

      rotateWithRightChild(k -> left);//先对左儿子进行一次右单旋转

      rotateWithLeftChild(k -> right);//再旋转根节点

}   

剩余的那两个旋转和这两个旋转函数是对称的,这里就不多说了。

 

请注意插入函数最后我弄成蓝色的那行代码。

     我们一般都会这么想:在插入之后判断是否还平衡,如果不平衡的话,我们就进行相应的调整。我们会编写这样的一个函数:

int calculateHeight(AVLNode* t)。 这个函数是递归的,递归的计算节点的高度。如果出现不平衡的情况,则进行相应的调整。可是,如果这样的话,就会增加一些递归的开销,实在没有必要。

     但是这个作者另辟蹊径,他不是编写递归函数,而是在递归的过程中完成,在弹栈的过程中完成了这个工作。在弹栈的过程中,首先判断在压栈的过程中经过的那些节点的左右子树的高度差,如果发现左右子树高度差超过了1,那么进行相应的调整;之后再更新节点的高度。

天才的作者,看来他对递归的过程了如指掌了:压栈,出栈~~在出栈的过程中更新节点的高度,好经典!!

 

二、左式堆的合并函数

思想:递归的合并小堆的右子堆和大堆。 以下是作者写的两个合并函数:

1.LeftistNode* merge(LefttistNode* h1,LeftistNode* h2) //合并两个子堆

{

    if(h1 == NULL)

        return h2;

    if(h2 == NULL)

        return h1;

    if(h1 -> element < h2 -> element)

        return merge1(h1,h2);//merge1函数假设第一个参数是小堆 

    else

        return merge1(h1,h2);

}      

2.//下面的这个函数假设第一个参数是小堆。

 LeftistNode* merge1(LeftistNode* h1,LeftistNode* h2)

{

      if(h1 -> left == NULL)

          h1 -> left = h2;//处理单个节点的情况,此时h1的右子树早已为空,为什么呢??呵呵~~  

      else

      {

          h1 -> right = merge(h1 -> right,h2);

          if(h1 -> left -> npl < h1 -> right -> npl)

               swapChildren(h1);//交换左右子树

        

       //风格的又一体现

         h1 -> npl = h1 -> right -> npl + 1;

       }

       return h1;

}   

说这本书是经典之作,一点都不夸张,代码写得好美!!他试图给我们养成一种思维习惯!!

知识共享许可协议
本作品《感悟《数据结构与算法分析(C++描述)》中的一些超经典递归函数》verynix创作,采用知识共享署名-非商业性使用-禁止演绎 3.0 Unported许可协议进行许可。
基于verynix.com上的作品创作。
Permissions beyond the scope of this license may be available at verynix.com.

本文链接: http://verynix.com/1037.html

Post Footer automatically generated by wp-posturl plugin for wordpress.

Leave a Reply

Your email address will not be published. Required fields are marked *