Category Archives: 学科基础

computer sience fundermantals

从AVL树和红黑树窥探树的节点设计

在这里,我想通过<数据结构与算法分析>中对AVL树的和<算法导论>中对红黑树的分析谈谈自己对树的节点中指针的设计方案的一点感悟.

今天晚上按照惯例,我又翻开了那本经典得不能再经典的<算法导论>,研究的是红黑树的一些基本操作:插入节点,旋转,删除节点.

看了将近半个小时的”左旋转”算法,一直没有看懂,郁闷了……不过,自己还是克服了心理障碍,又重新仔细地看了一遍那个算法的伪代码,终于弄懂了,原来自己没有弄懂代码中的那些父亲节点的变化问题.

我陷入了沉思,仔细地琢磨着:为什么这本书上的节点要这样设计?Why?

我想到了<数据结构与算法分析>中关于AVL树节点的插入问题.

1.节点的类:

struct AVLNode

{

      T* element;

      AVLNode* left; //左子树

      AVLNode* right; //右子树

      int height; // 高度

      AVLNode(const T& theElement,AVLNode* lt,AVLNode* rt,int h = 0)

              :element(theElement),left(lt),right(rt),height(h) {}

};

2.函数:        

/* x is the item to insert.
 * t is the node that roots the subtree.
 * Set the new root of the subtree.*/
void insert(const T& x,AVLNode* & t)
{
     if(t == NULL) //如果子树为空
        t = new AVLNode(x,NULL,NULL); //申请新的节点 
     else if(x < t -> element) //如果x小于t中的元素
     {
         insert(x,t ->left); //往左插入 

         if(height(t -> left) – height(t -> right) == 2) //如果违反了AVL树的性质 
         { 
              if(x < t -> left -> element) //进行一次左旋转
                  rotateWithLeftChild(t);
              else
                  doubleWithLeftChild(t); //先进行一次左旋转,再进行一次右旋转
      }
      else if(x > t -> element)
      {
          insert((x,t -> right));  //想右插入

          if(height(t -> right) – height(t -> left) == 2) //违反了AVL树的性质 
              rotateWithRightChild(t); //进行一次右旋转
          else
              doubleWithRightChild(t); //先进行一次右旋转,再进行一次左旋转
     }
     else //元素重复
        ; 

     

t -> height  = max(height(t -> left),height(t -> right)) + 1; //更新t中的高度
     } 
}    
    

刚开始看最后那行代码的时候,我相当地困惑,根本看不懂.主要的问题是没有理解什么时候更新路过的那些节点的高度.

于是,我又不得不请教王师兄,他也仔细地跟我讲了两遍,然后在工作室的讨论班上他又认真研究了一番.但是,我依然模糊中……我当然不服啊,于是,又硬着头皮用gdb调试了好几遍……皇天不负有心人,终于,我弄明白了最后那行代码的意思了,进而,这个子程序我也差不多弄懂了:原来,在递归的过程中,节点经过的路径上的那些节点都被压入栈里面了;当节点被插入以后,出栈,在出栈的过程中,最后那行的代码不断地更新路径上的那些节点的高度,如果违反了AVL树的性质,则进行相应的调整.

随着所学知识的不断加深,人总对以前学过的知识进行反省……

<算法导论>上关于红黑树节点的旋转伪代码让我顿时陷入了沉思:为什么这他们要增加一个数据成员:指向父亲节点的指针??? 不觉得麻烦吗??(呵呵,当然,名著还是名著,当然有原因的…….)

我想到了上面 AVL树的那几行代码,我对比地看,对比地琢磨,终于明白了这本经典名著的良苦用心:为了更方便地寻找到一个节点的父亲节点.

有人纳闷了:这有什么大惊小怪的?

呵呵,别急,我先给你对比一下迭代和递归的优缺点:

1.如果一个问题刚开始难以解决,可以将其简化后再尝试解决。如果这个过程可以重复进行,问题最终会变得容易处理。由此引出两种不同的方法:递归和迭代。

2.循环或迭代,是一种重复执行一个过程的方法;递归是另一种方法。递归函数是通过调用函数自身来完成任务,而且在每次调用自身时减少任务量。而迭代是循环的一种形式,这种循环不是由用户输入而控制,每次迭代步骤都必须将剩余的任务减少;也就是说,循环的每一步都必须执行一个有限的过程,并留下较少的步骤。循环的进度通常用一个在每次迭代时都进行自增或自减的变量的值来衡量,直到到达预定的目标为止。

3.用递归算法表示许多问题的求解方法时算法思想非常简洁。但是递归算法不仅时间效率非常差,而且由于递归算法是不断的函数调用和函数返回过程,因此其实际的计算机运行时间通常远大于循环方式算法的计算机运行时间,甚至在有限的时间内无法求解。这就存在一个把递归算法化为非递归算法的问题。 

听说递归的时间效率有点低下,我自然会有将递归化为迭代的想法了.

在AVL树的节点插入之后,需要调整那些不平衡的节点,如果你用了含有指向父亲节点的指针之后,这个过程就变得相对的容易一些:你在回溯的过程中,只需要回溯到它的父亲节点就行了.

有人又说了,我可以用栈啊……

呵呵,我说,你不觉得那样很麻烦吗?而且,整个压栈和出栈的过程你能烂熟于心??这个过程就让你痛不欲生.

所以,我还是觉得,增加一个指向父亲节点的指针,这样进行回溯的时候相当的方便.

这样100%完美吗?

呵呵,不好说,我总觉得多了一个指针,有点浪费空间.当然,这只是感性的一些看法,具体的,还要研究研究……

搞定断错误(Segmentation faults)和两次释放内存的问题

我满怀信心的编写了链表函数,结果运行时得到了两个错误:

1.段错误(Segmentation faults)

  我当时编写了一个链表的排序函数如下:

  void Linkedlist::sort()
    //to sort the list
     {
          int data = 0;
   
          Node* p1 = head;
         Node* p2 = head;
   
         if(head != NULL)
          {
          //selection sort
           while(p2 -> next != NULL)
           {
             while(p1 != NULL)  
             {
              p1 = p1 -> next; //move p1 to next node  (问题就出现在这里,因为p1 -> next 可能是NULL
   
             //exchange two node’s data
               if(p1 -> data <= p2 -> data)
               {
                 data = p1 -> data;
                 p1 -> data = p2 -> data; 

                  p2 -> data = data;
             }
             }
   
             p2 = p2 -> next; //move p2 to the next node
             p1 = p2;
            }
          }
     }


当时我去google了一下,找到了很多的帖子,总结起来有一下的几个原因:

1。 针没有赋值;
2。 量赋值类型有错误。

3。数组越界也能产生断错误;

4。 最主要的错误就是声明了指针,但是没有初始化 ,结果再后来的时候进行间接引用 ,就出现问题了。


又找到了一个很好的英文网址:

http://en.wikipedia.org/wiki/Segmentation_fault   


我也感觉到我很大一部分原因出现在指针的操作上了,但是一直没有看出来,后来就不得不上csdn,终于在那些大牛人的帮助下搞定了,超级感谢他们。     

2.两次释放内存,出现:double free or corruption (fasttop): 0x0890e008   

*** glibc detected *** ./l1: double free or corruption (fasttop): 0x0890e008 ***
======= Backtrace: =========
/lib/libc.so.6[0xb7d0ba00]
/lib/libc.so.6(cfree+0x89)[0xb7d0d6f9]
/usr/lib/gcc/i686-pc-linux-gnu/4.1.2/libstdc++.so.6(_ZdlPv+0x21)[0xb7ebc1a1]
./l1(__gxx_personality_v0+0x279)[0x8048a01]
./l1(__gxx_personality_v0+0x29d)[0x8048a25]
./l1[0x8048e60]
/lib/libc.so.6(__libc_start_main+0xdc)[0xb7cbbfdc]
./l1(__gxx_personality_v0+0x59)[0x80487e1]

======= Memory map: ========
08048000-0804a000 r-xp 00000000 08:03 1271041    /home/zhongyijun/Datastructures/list/stack/3.2/l1
0804a000-0804b000 r–p 00001000 08:03 1271041    /home/zhongyijun/Datastructures/list/stack/3.2/l1
0804b000-0804c000 rw-p 00002000 08:03 1271041    /home/zhongyijun/Datastructures/list/stack/3.2/l1
0890e000-0892f000 rw-p 0890e000 00:00 0          [heap]
b7b00000-b7b21000 rw-p b7b00000 00:00 0
b7b21000-b7c00000 —p b7b21000 00:00 0
b7ca5000-b7ca6000 rw-p b7ca5000 00:00 0
b7ca6000-b7dd0000 r-xp 00000000 08:03 2932840    /lib/libc-2.6.1.so
b7dd0000-b7dd2000 r–p 0012a000 08:03 2932840    /lib/libc-2.6.1.so
b7dd2000-b7dd3000 rw-p 0012c000 08:03 2932840    /lib/libc-2.6.1.so
b7dd3000-b7dd6000 rw-p b7dd3000 00:00 0
b7dd6000-b7de0000 r-xp 00000000 08:03 3228413    /usr/lib/gcc/i686-pc-linux-gnu/4.1.2/libgcc_s.so.1
b7de0000-b7de1000 r–p 00009000 08:03 3228413    /usr/lib/gcc/i686-pc-linux-gnu/4.1.2/libgcc_s.so.1
b7de1000-b7de2000 rw-p 0000a000 08:03 3228413    /usr/lib/gcc/i686-pc-linux-gnu/4.1.2/libgcc_s.so.1
b7de2000-b7e06000 r-xp 00000000 08:03 2932821    /lib/libm-2.6.1.so
b7e06000-b7e07000 r–p 00023000 08:03 2932821    /lib/libm-2.6.1.so
b7e07000-b7e08000 rw-p 00024000 08:03 2932821    /lib/libm-2.6.1.so
b7e08000-b7ee6000 r-xp 00000000 08:03 3228412    /usr/lib/gcc/i686-pc-linux-gnu/4.1.2/libstdc++.so.6.0.8
b7ee6000-b7eea000 r–p 000dd000 08:03 3228412    /usr/lib/gcc/i686-pc-linux-gnu/4.1.2/libstdc++.so.6.0.8
b7eea000-b7eeb000 rw-p 000e1000 08:03 3228412    /usr/lib/gcc/i686-pc-linux-gnu/4.1.2/libstdc++.so.6.0.8
b7eeb000-b7ef2000 rw-p b7eeb000 00:00 0
b7eff000-b7f01000 rw-p b7eff000 00:00 0
b7f01000-b7f02000 r-xp b7f01000 00:00 0          [vdso]
b7f02000-b7f1c000 r-xp 00000000 08:03 2932839    /lib/ld-2.6.1.so
b7f1c000-b7f1d000 r–p 00019000 08:03 2932839    /lib/ld-2.6.1.so
b7f1d000-b7f1e000 rw-p 0001a000 08:03 2932839    /lib/ld-2.6.1.so
bfd08000-bfd1d000 rw-p bffeb000 00:00 0          [stack]
已放弃

又查了很多的帖子,调试了好几次程序,但是弄错了方向,我还以为是我的creat函数出错呢,还是没有找出来,不得不再次上csdn,在几个人的提醒下终于发现自己的析构函数有问题了,果真是释放了好几次内存: 

Linkedlist::~Linkedlist()
{
    deleteL();

void Linkedlist::deleteL()
//delete the linkedlist 
{
    Node* p1 = head;
    Node* p2 = head;

    if(head != NULL)
    {
        while(p1 != NULL)
        {
            p1 = p1 -> next; //move p1 to the next node 
            delete p2; //delete the previous node       (这里出现问题,因为p2没有继续移动) 
        }  
        head = NULL;
    }
}

哎,终于搞定了,学了不少,既学会了使用gdb,又长了见识~~


Page 6 of 6« First...23456