2006年03月16日

今天在国外的BLOG见到, 有兴趣的朋友可以去试试

http://www.madeinexpress.com/

提交了后又觉得有点后悔, 我为什么要把自己那么好的点子告诉给Microsoft?

呵呵, 也许那个idea并不是那么的好…….

2006年03月14日

1) see this

http://lab.msdn.microsoft.com/productfeedback/viewfeedback.aspx?feedbackid=df12fa82-05a0-412c-9e71-9da936759eca

and this

http://lab.msdn.microsoft.com/productfeedback/viewfeedback.aspx?feedbackid=b2a76fe4-c572-4d8a-9e76-f6a380a25c9f

before VS.NET 2005 was released, they delcared we can build standard XHTML website with VS.NET easily, what a joke!!!

2) I spent a whole day trying to customize the CreateUserWizard control in the template, afterwards I reallize I  can customize my own textbox with those UserName, Password, and Email name, but I will lose all validation, then I have to customize everything! So, why do I need such a stupid control?

At the end, I just used my own form and called MemberShip functions, then I felt much better.

3) We are having a huge project with over several thousands of files running on .NET 1.1, after a team in the company analyzed over one month, they concluded, there is no way to upgrade the current program smoothly, ’cause the 2.0 is changed too much. We will have to rebuild many components in our system. And there are over 1000 ascx in the system, but the "code-behind" property is gone, so we have to modify every single file. So nice!

4) Master page? what a great idea! it sucks.

there is no way to customize the page meta, I have to write the following function in somewhere

    public static void AppendMeta(Page page, string name, string content)
    {
        HtmlHead head = page.Header;
        HtmlMeta meta = new HtmlMeta();
        meta.Attributes.Add("name", name);
        meta.Attributes.Add("content", content);
        head.Controls.Add(meta);
    }

or I can use another strategy, define a BasePage for the whole website, then expose the meta properties…

Wait a min, a BasePage? is this something we used in 1.1?

………………

there are more jokes about .NET framework I don’t want to discuss.

don’t misunderstand me, I am not blaming only .NET here. but recently I have been working on .NET 2.0, there are so many stuffs just driving me crazy! 

As a developer, I strongly recommend everyone to read this

Why I hate Framework

2004年12月16日

 

本文将介绍一种另类的快速排序(其实也不是什么新方法,估计也有不少朋友见过了)。一般的quicksort如果不是同时从左和从右找,发现前值小于后值就交换,然后递归继续;就是先假定一个位置的元素为pivot,然后不同方向搜索。这些方法都需要循环几次,所以一般在网上看到的代码都有用到几个while,然后再递归两次。下面你将看到一个quicksort只用了一次while

 

原理依然是使用分区法,比如以下这个数组

[60, 30, 80, 70, 50, 20]

 

先假定 60 pivot,选择它下一个值,我们称为smallend,稍后我们再解释它的意思。

 

根据以上所述,pivotindex0,该值为60smallendindex1,该值为30

 

然后我们从smallend开始往前,我们把往前的那个指针称为idx,现在idx1,因为我们是从smallend的位置开始往前的。只有发生以下三种情况:

 

1.当我们发现一个比pivot大的值,什么野不做。

2 当我们发现一个比pivot小的值,把它和smallend位置的那个元素交换,并让smallend++

3Smallend = idx,不交换,但是让smallend++

 

比如上面那个数组,idx=1,元素为30,因为<60,但是发现这个位置就是smallend了,于是直接加1,现在数组个元素位置不变,smallend=2

 

接下来idx=2,元素为80,因为 >60,什么也不做,继续往前;idx=3,元素为70,什么也不做。Idx=4,元素为50,把它和smallend位置的元素交换,并增加smallend,数组变成

[60, 30, 50, 70, 80, 20]

现在smallend3idx4

 

继续往前走,idx=5,元素为20,交换,增加smallend。数组变为

[60, 30, 50, 20, 80, 70]

 

循环已经结束。Smallend=4,也就是正指向元素80那个位置。

相信大家现在大概直到,smallend就是指所有比pivot小的元素在数组中后面那个位置。

现在,我们把smallend1smallend=3,指向元素20的位置。我们把这个元素和pivot交换。那么pivot已经找到它的位置了——它左边的所有值都比自己小,右边所有值都比自己大。数组已经变成

[20, 30, 50, 60, 80, 70]

 

然后,再开始递归,quicksort(左边),quicksort(右边)。结束!

 

具体实现的代码如下:

 

 

private static void QuickSort(int[] arr,int left, int right)

{

       if (right>left)

{

        int smallend= left + 1;

        int idx = left + 1; // start from the element next to the first element

        int rightIdx; // reserved to backup the smallend

                   

        // check from left+1 to right

        while (idx<=right)

        {

            if (arr[idx]<arr[left])

            {

                 swap(arr, idx, smallend);

                 smallend++;

             }

             // increase the next element position

            idx++;

         } // end while

               

         rightIdx = smallend;

         smallend–;

         swap(arr, left, smallend);

         // 到这一句结束就已经把数组分好两块了

 

         // recursively quick sort the left partition

         QuickSort(arr, left, smallend) ;

         // recursively quick sort the right partition

        QuickSort(arr, rightIdx, right);

    } // end if

}

 

private static void swap(int[] arr, int index1, int index2)

{

    if (index1==index2) return;

    int temp =arr[index1];

    arr[index1] = arr[index2];

    arr[index2] = temp;

}

 

实现过程中只用了一次while,但是道理上还是使用了quicksort的原则。

 

注:请勿修改或转至刊登于盈利性刊物,欢迎网上自由转载。谢谢。

 

 

删除

 

 

这次,让我们直接看例子,请回顾之前看到的【树一】

 

 

1.  最简单的情况就是,删除一个leaf结点的值后,改结点仍然不会空。比如删除【树一】的39,43,69,73(是说一次删除一个,不是指依次删除)。提到的值都是位于leaf上,而且这些结点都是已经有两个值;不过要记得移除了large值的话,不需要多做什么;但移除small值,需要将large值设置为-1,然后把原来的large移动到small上。

 

 

2.  在【树一】上移除12

 

 

如果移走了12,树会变成如下:

 

 

<53>

         /         \

        /           \

<27>        <65, 78>

/  \        /     |     \

   <>  <39,43> <60> <69,74>  <93>

            树八 (not valid yet)

 

 

    <27> 的左子树空了,这不合法。这时候,我们需要向<12>的“亲戚”(sibling)借一个值,也就是<27>的右子树,它刚好有两个值。将小值39推上去,再将27拉下来,最后如下

 

 

<53>

         /         \

        /           \

<39>        <65, 78>

/  \        /     |     \

   <27> <43> <60> <69,74>  <93>

            树九

 

 

    这里使用的策略是,当删除一个结点的值会识得该结点变空,就尝试向它的亲戚结点借一个值,如果可能的话。

 

 

3.  删除非leaf结点的值

 

 

这次让我们删除【树九】的65,这是一个在非leaf结点上的值。

因为当一个结点非leaf,它一定有子树,因此也必定存在有“inorder successor”(这个东西真的不知道怎么翻译,这个跟BST的删除一样,找到一个最小的比65大的元素)

 

 

所以,我们可以找到69,然后跟65替换,最后的树变成

<53>

         /         \

        /           \

<39>        <69, 78>

/  \        /     |     \

   <27> <43>   <60>   <74>  <93>

     树十

 

 

4.  删除一个元素,其亲戚结点无值可借

 

 

比如【树十】我们要删除74,它右边的亲戚结点只有一个值,无法借过来。还记得我之前曾经提过吗,对,我们把父结点的值拉下来,就刚好如同我们新增时候所做的反过来。我们可以将69拖下来,并与60合并。最后树变成

 

 

<53>

         /         \

        /           \

<39>         <78>

/  \        /        \

   <27> <43>   <60,69>    <93>

     树十一

 

 

请自己尝试在【树十一】上增加74,看看是否和【树十】一样

 

 

5.  删除一个元素,其亲戚结点无值可借,而且父结点只有一个元素,无法下推

 

 

比如,我们要从【树十】中删除43,如果我们像刚才所说的那样做,把父结点拖下来合并,树就会变成这样:

 

 

<53>

         /         \

        /           \

<>         <69, 78>

/  \        /     |     \

 <27,39> <>   <60>   <74>  <93>

     树十二 (not valid yet)

 

 

这明显不合法。我们需要做的时候重复一次,再把父结点(39的父结点是53)拖下来合并,原来39的位置变成53了,53的位置又变空了。可是这次原来39的位置有亲戚子树<69,78>可以借。请参照情况2,把小值69推上去,因为53去了左子树那边,需要找它的inorder successor(找到60),把它移到53的右子树去。最终,完整的树变成

 

 

 

 

 

 

<69>

         /         \

        /           \

<53>          <78>

/   \        /     \

 <27,39> <60>   <74>   <93>

     树十三

 

 

现在是一棵合法的2-3树了,但是这次你不能用将43重新插入来检验是否正确,因为如果重新插入43会变成

 

 

<69>

         /         \

        /           \

<39,53>        <78>

/  |  \        /   \

 <27> <43> <60>   <74>   <93>

     树十四

 

 

6.  删除一个元素,其亲戚结点无法借值,其父结点只有一个元素,其父结点的亲戚结点也无法借值……

 

 

这是最复杂的情况,其实也就是需要不断的重复步骤,直到出现以下情况

1)  当一个结点有两个元素

2)  当一个结点的亲戚结点可以借值

3)  当已经到达root

 

 

当最后一种情况发生的时候,root的两个子树就合并,原来的root就被删除,新的root出现,树的高度减1

 

 

总结

 

 

删除元素i的方法

 

 

1)  找到包含元素i的结点n

2)  如果n是一个leaf,先删除i

如果n不是一个leaf,找到i的inorder successor,与i交换,然后删除i

3)  如果这个时候n不是空,那么删除完成

如果n变空了,恶梦开始(^^),我们需要修复树

a)       检查n的亲戚结点,如果有两个元素,借一个过来(要注意借过来的元素和父结点元素的安排)比如你从左子树借一个过来,那当然是借一个左子树的large,然后原来的父结点元素拖下来;如果是从右子树借一个,那当然是借small,还要同时把small变成large,再把small变成新父结点,原来的父结点放到空结点去。(如果觉得比较混乱请自己画个图就清楚了)

b)       如果没有亲戚结点有两个元素,那就直接把父结点拖下来合并,让父结点变成空。

c)       递归的往上重复,直到遇到在情况6中所述的三种情形。

 

 

代码

 

 

首先我要给大家看的是 tree23里面的delete方法

 

 

    public void delete(int data)

    {

        tree23Node ptr, found;

        int tmp;

       

        found = locate(data); // 首先我找到该元素所在的结点

       

        if (found==null)

        {

            return;

        }

        else

        {

            if (!found.isLeaf()) // if it is not a leaf

            {

                if (found.small==data && found.itemCount>1)

                {

                    ptr = found.middle;

                }

                else

                {

                    ptr = found.right;

                }

           

                // 这里我是找 inorder successor

                while(ptr.left!=null) ptr = ptr.left;

               

                // 然后交换需要删除的那个值

                if (found.small==data)

                {

                    tmp = found.large;

                    found.small = ptr.small;

                    ptr.large = tmp;

                }

                else

                {

                    tmp = found.large;

                    found.large = ptr.smll;

                    ptr.large = tmp;

                }

            }

            else  // found is a leaf

            {

                ptr = found;

            }

           

            // 交换完毕了就删除元素

            if (ptr.large == data)

{

    ptr.large = -1;

 ptr.itemCount–;

            }

            else if (ptr.small==data)

            {

                ptr.small = ptr.large;

                ptr.large = -1;

                ptr.itemCount–;

            }

           

            // if it is empty, fix the root

            // 这里我用了跟新增一样的技巧,调用fix方法修复,然后返回整棵树

            if (ptr.itemCount == 0)

                root = ptr.fix();

               

        } // end if found==null

    } // end delete

 

 

剩下的工作,就是在 tree23Node里增加一个方法fix,不需要任何参数,该方法调用的时候this一定是一个空结点,然后就往上找就是。具体实现的步骤已经说得很清楚了,而方法也类似split那样。

 

 

如果感兴趣的朋友不妨自己试试,倒的确是一个锻炼的好机会。

 

 

后记

 

 

这篇东西纯粹是介绍性质的文章,因为2-3树在国外是很受重视的,可惜似乎国内倒不太关注。我在google上找到有人问,却没有什么比较详细的中文资料。于是才决定写这篇东西。写得比较潦草,也没有非常专业的口吻,不妥的地方还请指教。非常欢迎转载,但是请不要自己修改后发表到盈利的报刊杂志上,只限网上转载,转载的时候也请声明出处,谢谢。

2004年12月15日

 


 


对于 class tree23,我提供了一个public的insert方法,如下:


 







public void insert(int data)


{


    // if the root is empty, which means the tree is emtpy.


    // create the tree. otherwise, call a private method


   


    if (root==null)


    {


        root = new tree23Node(data);


    }


    else


    {


        insert(root, data);


    }


} // end insert


 


同时,我也提供了一个private的insert方法,其实也可以放到同一个地方,主要就是免得一个方法太长而已。该方法代码如下:


 







private void insert(tree23Node curr, int data)


{


    // stores the node in a temporary variable


   


    tree23Node ptr = curr;


 


// for 2-3 tree, all new item must be inserted in a leaf.


     // find the correct leaf firstly


     // 还记得我前面说过的吧,第一步永远都是先找到一个leaf


               


     while (!ptr.isLeaf())


     {


         if (data <= ptr.small && ptr.left!=null)


         {


              ptr = ptr.left;


          }


          else if (data>=ptr.large && ptr.right!=null)


          {


               ptr = ptr.right;


          }


          else if (data<ptr.large && ptr.middle!=null)


          {


              ptr =  ptr.middle;


          }


      }


               


// 下面首先判断两种情况,如果当前的leaf只有一个元素,直接放进去就是了


               


      if (ptr.itemCount==1)


      {


           if (ptr.small <= data)


           {


                ptr.large = data;


                ptr.itemCount ++;


            }


            else


            {


                ptr.large = ptr.small;


                ptr.small = data;


                ptr.itemCount ++;


            }


       } // end outer if


               


       // 否则的话,这个leaf已经full了,因为它有两个值。那我就split它好了。但是在split之前,我先做一件事,就是先还是照加入新值,并按顺序排列好。就是说,如果新值最小,就放到small,把原来的small放到large,把原来的large放到temp。如果新值最大,就放到temp;如果它是中间值,就放到large,而原来的large就放到temp。


               


       else


       {


             if (ptr.large <= data)


             {


                 ptr.temp = data;


              }


              else if (ptr.small <= data)


              {


                  ptr.temp = ptr.large;


                  ptr.large = data;


              }


              else


              {


                  ptr.temp = ptr.large;


                  ptr.large = ptr.small;


                  ptr.small = data;


              }


                   


              // increase the item count of this node, which


              // should be 3 now


                   


              ptr.itemCount++;


                   


              // call split method and overwrite root


 


              root=ptr.split(); // split 方法返回的是一棵完整的树


 


         } // end else


} // end method insert


 


终于到了最激动人心的时候,就是 class tree23Node 的split方法。


 


为什么要把这个方法放到tree23Node里面呢?一开始我只是觉得会方便一些,因为比较split的时候,对每个结点的各种属性都需要访问和改变,如果在this里面访问,可以不需要写 “[对象].” 这样。呵呵,很无聊的原因吧。


 


其实,放到tree23Node还是有原因的,从OO的概念上看,tree23.split() 没有意义,无论它是否private。Split这个操作是属于一个node的。另外,从可读性和操作性上,放在tree23里都相当麻烦,我也看过不少这样做的代码,大家也不妨去google查查看。


 


在显示代码之前,先做一些说明。


 


Split方法只有当一个node是full的时候才被调用,而且返回值是一棵完整的2-3tree。


该结点其中small是最小值,large是中间值,temp包含最大值。我们要做的是:


1.     将最小值和最大值分开,变成独立的两个node,让我们叫一个是小结点,一个是大结点


2.     把中间值推到父结点。


1)如果父结点是空的,那么表示我们已经到了root,创建一个新root包含那个中间值,并连接小结点到left,大结点到right,返回新创建的root


2) 看看this是属于父结点的哪一个子树


    a) 属于左子树,推上去的值一定是一个父结点的最小值,需要保存在small里


  


如果父结点是full的,先把原来的right连接到rtNode里做个备份,原来的large放到temp里,small放到large,推上去的值放在small里。现在轮到父结点需要split了,请在这里记住rtNode不为null。


 


如果父结点不是full,那大家都知道怎么做了。


 


b)属于右子树,推上去的一定是父结点的最大值,需要保存在large(也可能在temp里,要看父结点是否full)


 


   然后如上,分析父结点是否为full


c) 属于中子树,如果父子树有中子树,那么表示它一定已经full了。


  


   最后,看看父结点的 rtNode是否为空,如果不是,表示需要继续往上split。递归调用。否则就一直循环推上去直到root,返回。


 


可能我上面解释的不太清楚,还是让我们看代码吧


 







tree23Node split()


{


tree23Node retval, node1, node2;


     int s, m, l;


                   


                   


     s = small;


     m = large;


     l = temp;


                   


     // firstly, prepare two new nodes that are splited


     // in this node. That means, I have two new nodes that


     // one has the smallest item, another has the largest item.


     // Then, I will pass the middle item up.


    


     node1 = new tree23Node(s)                    ;


     node2 = new tree23Node(l);


                   


     // there are two cases


     // 1. this is the root, I just need to create a new root


     //    that contains the middle item and connect two new


     //    nodes to it


     // 2. this is not the root, I need to do the following things


     //      1) consider this node is parent’s left, middle, or


     //         right, to do different connections


     //      2) if parent is still full, recursively split


               


     if (parent==null)


     {


           // create a new node contains the middle value


          


           retval = new tree23Node(m);


           retval.left = node1;


           retval.right = node2;


      }


      else


      {


         // get the parent node


                  


         retval = parent;


             


         // if this node is parent’s left child


                 


         if (retval.left==this)


         {


              // if parent is full already, now parent should


              // have four children(1 is in rtNode), three items


         


              if (retval.itemCount>1)


              {


                    retval.rtNode = retval.right;


                    retval.right = retval.middle;


                   retval.temp = retval.large;


               }


 


               retval.left = node1;


               retval.middle = node2;


               retval.large = retval.small;


               retval.small = m;


         }


         else if (retval.right==this)


         {


                // if parent of this is not full, now parent


                // should have 3 children, otherwise 4, 1 is in


                // rtNode


                           


                if (retval.itemCount==1)


                {


                     retval.middle = node1;


                     retval.right = node2;


                     retval.large = m;


                 }


                 else


                 {


                      retval.right = node1;


                      retval.rtNode = node2;


                      retval.temp = m;


                  }


         }


         else if (retval.middle == this)


         {


                  // if this is the parent’s middle child


                  // it means parent must have 2 items, it


                  // has been full, I need to store one in rtNode


                           


              retval.middle = node1;


              retval.rtNode = retval.right;


              retval.right = node2;


              retval.temp = retval.large;


              retval.large = m;


         }


         else


         {


              //should never happen


                    


              System.out.println(“pointer error!”);


              System.exit(0);


         }


                       


         // 我已经把新元素加到父结点去了,它是否合法我暂时不管,总之我先增父结点的总数,减掉当前结点的总数


                       


          retval.itemCount++;


          itemCount–;


                 


      } // end else parent != null


                   


      // fix the new nodes


               


      node1.parent = node2.parent = retval;


                


      // if this node is not a leaf, I also need to fix


      // new nodes’ children and those parents


               


      if (!isLeaf())


      {


            node1.left = left;


            node1.right = middle;


            node2.left = right;


            node2.right = rtNode;


        


            if (node1.left!=null)


            {


                node1.left.parent = node1;


             }


                       


            if (node1.right!=null)


            {


                node1.right.parent = node1;


             }


                       


             if (node2.left!=null)


             {


                 node2.left.parent = node2;


             }


                     


             if (node2.right!=null)


             {


                 node2.right.parent = node2;


              }


      } // end if


                   


      // now I can clean the resources


                   


      left = middle = right = rtNode = parent = null;


                   


      // if parent still has an rtNode, it means parent is full


      // now, it needs to be splited too.


                   


      if (retval.rtNode!=null)


      {


            return retval.split();


      }


                   


      // if I am here, that means I have splited everything


      // now I move to the top, return the root


                   


      while (retval.parent!=null)


      {


            retval = retval.parent;


      }


                   


      return retval;


               


} // end method split


 


到这里,新增就全部讲完了。真是累得可以,明天继续。


 

 


 


续上次的答案,依次加入34,35,37后,2-3 tree应该变成如下:


 


 


<27,53>


             /       |       \


            /        |        \


<15>     <34,39>     <65, 78>


/   \    /   |    \     /    |    \


<12> <22> <32><35,37><43> <60> <69,74>  <93>


 


    树七


 


你对了吗?


 


1)  最后,让我们看看最复杂的一种情况,如果在【树七】中,加入36,应该变成怎样?


 


我们可以一步一步来,首先,找到36应该在的leaf,<35,37>,加入后变成<35,36,37>,该leaf变成full了。Split,然后推中值上去。变成如下:


 


      <34,36,39>


    /    |   |   \


  <32> <35> <37> <43>


 


好,父树也变成full了,这种情况我们见过,再split和再推中值上去。


 


     <27,36,53>


  /    |      |     \


 <15> <34>    <39>  <65,78>


 /\   /  \    /  \     / | \


  <32><35><37><43> 


 


嗯,现在我们的root也变成full了。那就在split一次,然后新建一个root,保存中值。 变成


      


         <36>


       /       \


    <27>       <53>


   /   \     /     \


<15>  <34> <39>   <65,78>


………………………………… (以下省略,大家都知道下面怎么连接了吧)


 


这个时候,我们的2-3 tree高度增加了1


 


到这里,已经列举了所有增加新值的例子。如果还不是太清晰,那我就在此总结一下吧:


 


l         新值的增加总是发生在leaf。(它最后是否在leaf上就很难说,但增加这个动作永远是发生在leaf上,所以第一步永远都是找到新值应该位于的leaf)


l         如果一个结点有三个值,我们说它是full了,需要split,把中值推到父结点上去。


l         如果一个结点需要split而它又刚好是root,那么就新创建一个root,保存那个中值。树的高度增加1。


 


接下来我们要做什么呢?大家是想看删除的特性吗?嗯,我只能说,删除相当复杂,即使只是BST的删除也很麻烦,大家都还记得BST的删除吧。我现在可以说的2-3 tree的删除大概是和新增反过来的,新增是往上推一个值,删除是往下找一个子树合并。


 


我不想立刻就开始讲删除,因为我想趁大家还记得新增的特性时让大家看看代码,加深大家对新增的印象。


 


我的代码- 新增部分


 


前面我给大家看过一个最简单的structure of 2-3 tree node,那个结构其实也可以做,但是比较麻烦。因为我们需要往上读父结点,如果没有parent指针,一般都是两种方法,一是用临时变量保存,这种方法在2-3tree里不是太现实,因为你不知道要往上查多少次;另外一种方法是用回溯,把所有顺序访问过的结点放到stack里,而我前面也说过,2-3 tree的高度最大为log2n + 1,所以stack的实现用数组都可以,比较方便。如果stack为空,表示我们已经到root了。但是用stack的话,我们就只能用循环。(大家都明白为什么吧)


 


如果在c++里,我们还可以用递归回到父结点上;但是java里参数传递没有引用传递(也有人说JAVA只有引用传递,都是说法一个,这里不追究)这个概念,所以我们很难用递归一步一步往上走。


 


不过既然写程序的是我们,我们可以对那个结构稍做修改,以适应我们的需要。


 


请参照上面那些树的图,有没有发现很多时候新增动作发生之后,一个结点会出现4个子树,3个值。这是最大的可能发生的情况,那么我们就给结构3个值,4个子树。同时为了方便,也给它一个父结点的引用,以及一个itemCount的值标志该结点有多少个值。


 


因此,新的tree23Node结构如下:


 


 






public class tree23Node


{


        int small; // the small item in this node


        int large; // the large item in this node


        int temp; // stores a temporary item


               


        tree23Node left;        // specifies left child


        tree23Node middle;    // specifies middle child


        tree23Node right;     // specifies right child


        int itemCount;       // how many items in this node


 


        // 以下一个结点用来储存临时子树,为什么设置成为private,是因为我打算将读取它们的动作都放在这个class里,就自然不需要让别人看到它们。


        private tree23Node rtNode;


        private tree23Node parent;


}


 


 


下面是tree23Node的constructor,一共有两个,很容易看到,这里就不注释了。


需要注意的是,我设置了default value是 -1,其实也是最小值。所以我是假定后面的2-3 tree 加入的值都是正数。当然你也可做相应修改以至能够接受负数。


 






    tree23Node()


    {


        itemCount=0;


        small = large = temp = -1;


        left = middle = right = parent = null;


    } // end tree23Node constructor


               


    tree23Node(int newVal)


    {


         itemCount = 1;


         small = newVal;


         large = temp = -1;


         left = middle = right = parent = null;


    } // end tree23Node constructor


 


同时tree23Node还提供两个方法,一个是isLeaf,返回真如果该node是一个leaf;代码如下(对不起,注释我一般习惯用英文):


 






/****************************************************************


* method isLeft


* purpose: tell whether this node is a leaf or not.


*       (a leaf is a node that has no child)


* return true if it is a leaf


***************************************************************/


public boolean isLeaf()


{


     boolean retval = false;


      if (left==null && middle ==null && right==null)


      {


           retval = true;


       }


       return retval;


} // end method isLeaf


 


另外一个重要的方法是 split,这个代码会放到最后。


 


下一篇,我们会看到tree23 class 里面的insert方法


 

 


 


前言


 


备注:文中可能偶尔多用了英文,倒不是卖弄,很多时候只是习惯性的,因为如果你平时接触的东西都是英文的,你写下来的时候自然想到的是英文字眼,而不是多一层先翻译成中文。还有一些是我只记得英文资料上的定义,比如我写之前想到 balanced tree,却不知道中文应该是什么,查google才知道应该翻译成平衡树。还有的原因是可能英文解释能更清晰表达就直接使用英文了。反正这篇东西的对象都是同行,我相信大部分人都有阅读英文资料的习惯,因此一定能够了解。如果阁下不喜欢中文夹着英文的东西,请不必阅读了,谢谢。


 


tree 在计算机数据结构里是一种非常重要的东西,介绍性的东西就不多讲了,树多数用于检索量比较大的地方,比如数据库和硬盘文件排列之类。树分很多种,最简单的当然是 BST (binary search tree) 中文应该是 二叉检索树,这个东西虽然简单,可是毛病很多,比如很容易出现 worse case,就是检索中最不愿意看到的线性检索(一棵只有右子树或者左子树的树);而且BST不是balanced的。所以,BST一般很少应用,前人发明了很多其他的树,比如AVLB-TREE2-3 tree, 2-3-4 tree 等等。这篇文章要介绍的就是2-3 tree,主要是因为它的中文资料……似乎没有(反正我没有在google上找到)。而 2-3-4 tree 只是一个变种,最后会简单介绍一下。


 


本文的实现代码我用了JAVA,本来这种需要访问指针的东西,我更想用c++,但考虑易读性还是JAVA比较好点,比较适合介绍性质的代码。


 


特性


 


2-3 tree 严格来说只有两个要求:


1.所有的结点有2个或者3个子树


2.所有的leaves(叶)都在同一个级别上。


 


不知道这样的中文解释是否够清楚,解释一下就是:叶是树中最后一个结点,它们的高度(path from root)都必须一样;每个结点最多只能有3个子树。


 


比如下面这棵树就是一个合法的2-3 tree


 

<10 20>
/  |  \
/   |   \
<5> <15> <30 40>

 


其实2-3 tree也是从BST演变过来的,小值就在左边,大值在右边。每个结点最多只有两个值,一个小,一个大。如果一个结点有两个值,这个结点称为full,那么如果它有子树,那么它一定有3个子树。如上图所示,小值(<10) 在左子树,大值 (>20) 在右子树,而中间值( 10<x<20 ),就在中间的子树。


 


为什么要这样排列?


因为它是balanced的!一棵高度为k2-3 tree2k – 1 3k – 1 之间的叶;一棵有n elements 2-3 tree 高度最小为 1+log3n 最大为 1+log2n。它的检索时间为O(logn)


 


检索的pseudo code


 



LOOP until curr = nil


IF ( data = curr.small OR data = curr.large )


    Return curr


ELSE IF ( data < curr.small )


  curr = curr.left


ELSE IF ( data > curr.small AND data < curr.large )


  curr = curr.middle


ELSE


  curr = curr.large



也可以通过递归来做,跟BST差不多,检索并不是本文介绍的目的,因为实在没什么好说的。

2-3 tree的结点结构


 


最简单的结构如下


struct tree23Node {


    int small,


    int large,


    tree23Node left,


    tree23Node middle,


    tree23Node large


}


 


插入


 


对于2-3 tree,所有的插入(新值)都必须发生在leaf。所以,首先找到新值应该所在的leaf,然后根据这个leaf的情况做出判断:


 


1.  该点只有一个元素。直接加入就可以了,判断是small还是large。


2.  该点full(small和large都有值),其父结点不是full。那就split该结点,并把中间值推上去。


3.  该点和其父结点都full。如果父结点full,表示父结点已经有3个子树。那就需要一直split 并一直往上推,直到发生以下情况:


1)     父结点最多只有3个子树


2)     父结点是根,创建一个新root,保存中间值。树的高度增加1


 


最好的解释其实还是例子,请先看一棵合法的2-3 tree如下:


         


 


 


<53>


         /         \


        /           \


<27>        <65, 78>


/  \        /     |     \


  <12> <39,43> <60> <69,74>  <93>


 


        树一


 


1)  加入 15


 


新加入一个值的时候,要记住,所有的新增一定发生在leaf。所以第一步我们需要找到15的位置。不错,就是在<12>那里。这个 leaf 只有一个元素,就是说不是full,这是最简单的一种情况,直接把15加在那个leaf就可以了。因为15>12,所以树会变成


 


<53>


         /         \


        /           \


<27>        <65, 78>


/  \        /     |     \


<12,15> <39,43> <60> <69,74>  <93>


 


     树二


 


我们可以再检查一下,是否满足2-3 tree的两个要求。(1) 所有结点只有2个或者3个子树,这个满足了。(2)所有的leaves都在同一个级别(高度一样),这个也满足了。


 


2)  加入22


 


这次好像有点麻烦了,22似乎应该加在<12,15>这个leaf上,可是它已经full了。如果加入后,应该变成


 


  <53>


             /         \


            /           \


<27>        <65, 78>


/  \        /     |     \


<12,15,22> <39,43> <60> <69,74>  <93>


 


    树三 (not valid yet)


 


按照前面提到的插入要求,需要split这个结点,split之后,该结点应该变成<12> <15> <22> 三个结点,然后把中间那个推上去。(为什么呢?因为只有中值上去变成父树里的值,原来的large变成的那个结点才能变成中子树的结点,还记得它的特性吗?所以,最后的树应该变成


 


   <53>


             /         \


            /           \


<15,27>        <65, 78>


/   |   \        /     |     \


<12> <22> <39,43> <60> <69,74>  <93>


 


     树四


    请自行检验是否合法2-3 tree


 


3)  现在让我们试试新加入 32


 


首先,大家都知道32应该在那个leaf开始动作了吧。不错,就是<39,43>,加入后,这个leaf应该变成<32,39,43>;full了,要split,变成<32><39><43>,再把中值推上去,变成以下的一棵树


 


 


   <53>


             /         \


            /           \


<15,27,39>   <65, 78>


/  |  |   \    /     |     \


<12><22><32><43> <60> <69,74>  <93>


 


     树五(not valid yet)


 


很显然,这不是一个合法的树。因为有结点有超过3个子树,而且有结点超过两个元素(full)。那么就需要继续split,然后又是中值往上推,直到见到只有两个子树的结点<53>。所以,再split一次后的树应该变成:


 


 


  <27,53>


             /     |       \


            /      |        \


<15>     <39>      <65, 78>


/   \      /   \    /    |    \


<12>  <22> <32> <43> <60> <69,74>  <93>


 


        树六


 


4)  请自行尝试在【树六】的基础上加入 34,35,37, 然后下次阅读第二篇的答案。

2004年10月09日

终于看完这出号称筹备了5年的《2046》,结束的时候感觉好累,于是就直接上床了。临睡着的时候听到自己说,够了,王家卫。

我本身其实还一直挺欣赏他的,他的每部电影我都有看过几遍之多。他到目前为止,自己亲自执导的电影,不算《旺角卡门》,其他的,每部都是在讲爱情,无非是换着角度在谈情,无论是看似杀手片的《堕落天使》还是看似武侠片的《东邪西毒》,又或者是同性之爱的《春光乍泄》。我现在倒真的挺想知道,王家卫自己目前的感情生活到底是怎样的?他曾经的女人又是怎样看他的呢?

至于现在这出《2046》,我不想谈演员的演技,也不想故事的合理性。《2046》其实根本就是一篇散文,一篇大概不会超过200多字的一篇散文;你很难怪他要筹备那么长时间,试想谁打算把《荷塘夜色》扩开成部电影,难度也挺高的。

可为什么我现在看完他这部新作和他以前的作品后感觉相差那么多呢?纯粹作为个人意见的总结一下,会有什么样的人看完《2046》后会有感触,觉得意犹未尽呢:

单身者或失恋者
感情伴侣有摩擦,或者认为对方并不是自己最好的那位
浪子,并经常回想自己过去的伴侣者
性生活压抑者,最近都没有正常的性生活
生活目的暂时还比较渺茫,对未来有憧憬,但对真正来到有心悸
工作乏味者,或者压力大并没有找到解决办法
多愁善感者(其实满足以上两项,基本都是多愁善感者)
年龄至少23以上,因为没有一定的故事的人不会太接受他的故事

如果你有符合上面所述2项以上,你肯静下心来看完《2046》,我相信你会像某些人说的,看完后会情不自禁的开始想……

那么,又有什么人相反呢?

每周有比较固定生活和工作的作息安排
生活忙碌但激情大过压力
对目前的伴侣感到满意,不会让自己缅怀过去,感情生活也十分愉快
有健康固定的性生活
有比较清晰的生活目标和计划
家庭主妇型(男人也可以算,就是顾家型)
超级忙碌型,但无可奈何者(比如一定要照顾小孩,又要上班,又要上课,每天都非常忙碌)

如果你有符合上面所述的2项以上,就算你肯静下心看完,我估计你多半也不会有什么感觉。

以我个人这次看完的第一反应就是,
----唉,还是感情,生活中除了爱情还有好多别的东西啊;
----爱情为什么要这样表达呢,何苦呢?
----睡觉吧……

我不认为《2046》拍的不好,也并不认为他拍的很无聊。他这次的表达手法也挺新颖的,可是为什么总是要那么苦涩的去看爱情这个问题?《重庆森林》里的羞涩,《堕落天使》里的自私,《花样年华》里的罪恶,他永远没有尝试去表现过爱情里积极愉快的一面;这也是我在开头好奇王家卫自己的感情生活的原因。

所以,够了,王家卫,也是时候尝试一下正面了吧。

他的电影确实很适合某些心态的人静静的看,就好像 jazz,适合一个人在夜里品尝,尝的时间越长,越觉得动听。但当你在某种时候,比如坐公车的时候,听 jazz 简直就是受罪…… 呵呵

最后,倒是很佩服王家卫能总是找到这么多些好的 jazz,每出戏都能带给我一些新的音乐上的感动,如果有原音碟,倒是可以考虑一下。

2004年07月28日

有时候看一些留学论坛广告版的帖子都会觉得寒心,不知道有些留学生是花着自己挣的钱还是谁的钱。

有的人明明有辆几乎崭新的跑车,还是要再买一部新车换;有的人有了一台很大的显示器,还是要再买一个液晶的;再看看一些人的家具,质量好得真是没话说。这些人有了解钱来的有多辛苦吗?当他们爹妈提款机啊?

可能是因为我是工作了几年才出国,所以很明白一个月几千元工薪阶层的积累有多难。想想大多数人的父母,我相信不是个个都是银行行长,省长之类人的子女吧,还是应该有很多双亲都是在为子女撑着省钱的吧。

出国留学本来花费就高,家里的两老头发都半白也不能退休,还要再撑几年。平时我和我女朋友两个人每个月都记帐,省吃俭用的,家里除了床和书桌什么都没有了;我每个月还抓紧时间赚点小钱帮补一下,也都只是想帮帮家里,让两老放心。可是别的人就是可以开跑车,家里什么电器都齐全,过着奢华而豪放的日子。

我并不是想引起什么纠纷,也无意贬低什么人,更不是妒忌他们;我只是想在这里说说,如果你家里真的有实力,你可以花那些豪钱,但也不要忘了留学真正的目的。

等胜利完成了学业后,花自己挣的钱才是最开心和满足的事啊……

2004年07月16日

Today is really an unexpectable day.

Suddenly found a song’s lyric?really good, especially at current time.

Martin

The pancakes

Maybe 21st’s not the right time
Perhaps my expectation was a little bit high
Or maybe cos i was still drunk since may
Or between us there is nothing to say

To be frank i have forgotten your voice
To be honest i can’t even remember your face
Somehow in my heart you’ve occupied a place
Every now and then you make me fall
You bring me sore

So by the time you came passing by
I knew it was all designed
I knew there’s no place where i could hide
You know i can’t decide
You know i can’t deny

So by the time you came passing by
And then you left me behind
Oh martin you messed it all up
So how you took me up into the sky
How you let me fall and cry

All along i’d been waiting for your call
After all just a simple lie is nothing at all
but you’ve decided not to call anyway
Cos between us there is really nothing to say

So by the time you came kissing me
You know you’re confusing me
Oh martin you know it’s all wrong
So how you threw me up into the sky
Shot me down and said goodbye

?