3

整数のセットを表すルート化された順序付きツリーがあります。各ノードには、関連付けられたサブツリーのサイズと、このサブツリーの最大要素と最小要素が格納されます。固定されている場合のすべてのノードの分岐度（ただし、実行時に決定されます）。また、十分に小さいサブツリーの場合、関連付けられたサブセットのビットマップに表現を変更したいと思います。たとえば、ルートノードはサイズ1000000のセットを格納し、この子の1つはサイズ100000のサブセットを格納し、次に彼の子の1つはサイズ10000のサブセットを格納し、次のレベルではこの表現の使用を停止します。関連するサブセットのプレーンビットマップのみを格納します。

この構造をC++で実装しようとしていますが、ノードタイプの定義には、3つの整数（サイズ、最小、最大）、サブツリーへのポインターの配列（node_t **子など）、およびビットマップ（この表現を使用）。問題は、すべてのノードが無関係な要素を少なくとも1つ格納していることです（たとえば、セットが十分に大きい場合は、ポインターの配列を使用しますが、ビットマップは使用しません）。この問題を解決するには、ノードタイプをどのように宣言する必要がありますか？ノードの2つのサブタイプ（それぞれの場合に1つ）を使用することを考えましたが、実行時のパフォーマンスにどのような影響があるかわかりません。

前もって感謝します。PS。編集する質問が不明な場合はお知らせください。

4

1 に答える 1

1

複数の表現を使用しているため、おそらく少なくとも2つのノードタイプが必要になります。1つ目はルートと近くの子孫を処理する汎用ノードで、2つ目はマップへのポインタを含みます。後者のノードには子の説得力はありませんが、それらの直接の祖先は、マップを指す終了ノードではなく、サブツリー全体としてそれらを見る必要があります。

各上位ノードには子へのポインターがあるため、これらのポインターが分岐ノードだけでなく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メガバイト増加するため、最小限に抑えるようにしてください。すべての分岐ノードが最終的に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に変更する必要がある場合、またはそれ自体（および子です！）をmapNodeに変更する価値がある十分な子を持つtreeNodeである場合は、変更が発生することに注意してください。

于 2012-09-02T01:06:58.030 に答える