C++中的有序树的良好节点定义

Question

我有一个代表整数集的有根的有序树。每个节点存储相关子树的大小，以及该子树中的最大和最小元素。所有节点的分支度如果固定（但在运行时确定）。对于足够小的子树，我想将表示更改为相关子集的位图。例如，根节点可以存储一个大小为1000000的集合，其中一个孩子将存储大小为100000的子集，然后他的一个孩子将再次存储大小为10000的子集，并且在下一个级别中，我们将停止使用该表示并且仅为相关联的子集存储简单的位图。我试图在C++中实现这个结构，我的节点类型的定义存储三个整数（大小，最小值和最大值），指针数组（像node_t **孩子）到子树和位图（如果我们使用这种表示）。问题是所有的节点都存储了至少一个不相关的元素（例如，如果集合足够大，我们将使用指针数组而不是位图）。应该如何声明节点类型来解决这个问题？我想过使用两种节点的子类型（每种情况一种），但我不确定在运行时对性能的影响是什么。

在此先感谢。 PS。请让我知道如果问题不清楚编辑它。

Answer 1

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

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

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对象时，您添加的每个字节都会将净内存使用量增加大约一兆字节，因此尽量保持最小限度。如果所有分支节点最终到达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。