3

我有一个代表整数集的有根有序树。每个节点存储相关子树的大小，以及该子树中的最大和最小元素。如果固定（但在运行时确定），则所有节点的分支度。同样对于足够小的子树，我想将表示更改为关联子集的位图。例如，根节点可能存储一组大小为 1000000 的子节点，其中一个子节点将存储大小为 100000 的子集，然后他的一个子节点将再次存储大小为 10000 的子集，在下一个级别中，我们将停止使用此表示并只存储相关子集的普通位图。

我正在尝试在 C++ 中实现这个结构，我对节点类型的定义存储了三个整数（大小、最小值和最大值）、指向子树的指针数组（类似于 node_t ** 子节点）和位图（如果我们是使用这种表示）。问题是所有节点都存储了至少一个不相关的元素（例如，如果集合足够大，我们将使用指针数组而不是位图）。应该如何声明节点类型来解决这个问题？我考虑过使用两种节点子类型（每种情况一个），但我不确定对运行时性能的影响是什么。

提前致谢。PS。如果问题不清楚以进行编辑，请告诉我。

4

1 回答 1

1

由于您使用多种表示形式，您可能至少需要两种节点类型：第一种将是处理根以及附近后代的通用节点，第二种类型将包含指向地图的指针。后面的节点没有任何子节点，但它们的直接祖先应该将它们视为整个子树，而不是指向地图的终止节点。

由于每个上层节点都有指向其子节点的指针，因此您需要一种方法来确保这些指针也能够指向 mapNode 以及分支节点。一个很好的方法是创建一个带有虚拟函数的虚拟基节点类型，该函数返回您正在寻找的任何数据。例如：

class baseNode {
  virtual int getLargest();
  virtual baseNode* addData(int);
};

class leafNode : baseNode { //for non-map termination
  leafNode(int in) {Data = in;}

  int getLargest() {return Data;}
  baseNode* addData(int);

  int Data;
};

class treeNode : baseNode {

public:
  int getLargest(); //returns leftChild->getLargest(), etc
  baseNode* addData(int);

  baseNode* leftChild;//can point to either a treeNode or mapNode
  baseNode* rightChild;
};

class mapNode : baseNode {
  baseNode* addData(int);
  int getLargest(); //parses subMap to find/return the desired value

  Map* subMap;
};

你需要一些技巧才能让它做你需要做的事情，但原理是一样的。请记住，对于 1m 个对象，您添加的每个字节都会增加大约 1 MB 的净内存使用量，因此请尽量保持最小。如果您的所有分支节点最终都到达一个 mapNode，您可以leafNode完全消除该声明。

向结构中添加数据很棘手，特别是因为您正在使用多种类型并且父母（希望）对他们的邻居一无所知；使用虚拟访问器来做需要的事情。在许多情况下，如果分支节点尝试“向下”添加值，则它引用的子节点可能需要更改类型。在这种情况下，子结构应该构造新的子结构，然后将其返回给父结构。这可以这样做：

baseNode* treeNode::addData(int in) {
  if ((childCount+1) < threshold) { //not enough to merit a map
    //....
    //if (input needs to go to the leftChild) {
      if (leftChild == 0) {
        leftChild = new leafNode(in); 
      } else {
        leftChild = leftChild->addData(in);
      }
    //}  
    return (baseNode*)this; //casting may be optional
  } else {  //new Data merits converting self + kids into a map
    mapNode* newMap = new mapNode();
    //Set newMap->subMap to children, deleting as you go

    delete this;//remove self after return
    return (baseNode*)newMap; //return the mapNode holding subtree
  }
}

baseNode* leafNode::addData(int in) {
  treeNode* tmpNode = new treeNode(); //create replacement
  tmpNode->leftChild = this; //pin self to new node
  tmpNode->rightChild = new leafNode(in); //store data
  return (baseNode*)tmpNode;
}

baseNode* mapNode::addData(int in) {
  subMap->addValue(in);//However you do it...
  return (baseNode*)this; //parent is always a treeNode
}

通常leftChild = leftChild->addData(in);实际上不会修改任何东西，特别是如果它指向一个treeNode，但是这样做并没有真正伤害任何东西，额外的if (newPtr != leftChild)检查只会增加不必要的开销。请注意，如果一个leafNode 需要更改为具有多个孩子的treeNode，或者如果它是一个具有足够孩子的treeNode 值得将其自身（而且是孩子！）更改为mapNode ，则会导致更改。

于 2012-09-02T01:06:58.030 回答