LongTree的正确分析理解

05-01-04 mybillliu
LongTree的正确理解分析

在网上有一篇文件介绍LongTreer的原理的,但是对于leftChildren和rightSiblings的讲解似乎有些不完整。

leftChildren保存某结点儿子在keys[]中的数组索引值,同理rightSiblings保存其本结点兄弟在keys[]中的数组索引值。

通过一些测试让我理解这一功能:

下面是从JiveMessage表中截取的部分数据

messageID	ParentMessageID	threadID	forumID
2	NULL	         1	31
31	2	         1	31
46	2	         1	31
61	2	         1	31
62	2	         1	31
32	31	         1	31
47	46	         1	31
<p>

在LongTree中的addChild方法加入了部分代码,也修改了部分代码,目的是为了输出leftChildren 、rightSiblings的数值

public void addChild(long parentKey, long newKey)
  {
    //	找到一个给定的节点parentKey的父结点
    char parentIndex = findKey(parentKey, (char) 1);
    //System.out.println("父节点索引号:" + (int)parentIndex + "-----父结点:" + parentKey +
    //   "-----子结点:" + (int)newKey);
    if (parentIndex == 0)
    {
      throw new IllegalArgumentException("Parent key " + parentKey +
                                         " not found when adding child " +
                                         newKey + ".");
    }

    keys[nextIndex] = newKey;
    leftChildren[nextIndex] = 0;
    rightSiblings[nextIndex] = 0;
    System.out.println("keys[" + (int) nextIndex + "] = " + (int) newKey);

    // Adjust references. Check to see if the parent has any children.
    if (leftChildren[parentIndex] == 0)
    {
      // No children, therefore make the new key the first child.
      leftChildren[parentIndex] = nextIndex;
      System.out.println("leftChildren[" + (int) parentIndex + "] = " +
                         (int) nextIndex);
    }
    else
    {
      // The parent has children, so find the right-most child.
      long siblingIndex = leftChildren[parentIndex];

      while (rightSiblings[new Long(siblingIndex).intValue()] != 0)
      {
        siblingIndex = rightSiblings[new Long(siblingIndex).intValue()];
      }

      // Add the new entry as a sibling of that last child.

      //rightSiblings[new Long(siblingIndex).intValue()] = nextIndex;

      int tmpint = new Long(siblingIndex).intValue();
      rightSiblings[tmpint] = nextIndex ;
      System.out.println("rightSiblings[" + tmpint +"] = "  + (int)nextIndex);
    }

    // Finally, increment nextIndex so it's ready for next add.
    nextIndex++;
  }
<p>

下面是输出值

keys[2] = 31

leftChildren[1] = 2

keys[3] = 32

leftChildren[2] = 3

keys[4] = 46

rightSiblings[2] = 4

keys[5] = 47

leftChildren[4] = 5

keys[6] = 61

rightSiblings[4] = 6

keys[7] = 62

rightSiblings[6] = 7

得到了这么一组值,该如何理解呢?

假设有

leftChildren[X] = Y

正确理解是

keys[Y]是keys[X]的一个儿子结点

同理

rightSiblings[X] = Y

正确理解是

keys[Y]是keys[X]的一个兄弟结点

也就是说leftChildren、rightSiblings保存的是它们子结点、兄弟结点在keys[]中的数组索引值而已,而不能说leftChildren保存的是某一结点的子结点

时间有限,懒得去好好的整理文字,大家能理解就行

愿和更多的对Jive有深入研究的朋友交流

QQ:45214493(对JIVE没有研究者勿加)

mybillliu
2005-01-04 16:45
愿和所有对JAVA有深入研究的朋友一起共同交流、进步

猜你喜欢