c++ - 二叉搜索树 - 按两个数据项排序

Question

我想维护两个相关的二叉搜索树，其节点包含两项数据 - 页码和创建/引用时间(细节并不重要 - 本质上它是两个 64 位数字)。

第一棵树按页码排序，第二棵树按创建时间排序——本质上用例是:

• 查找页面是否存在(在树中)，按页码搜索
• 如果页面存在，更新其引用时间为现在
• 如果页面不存在 - 将页面添加到两个树中，创建时间为现在
• 但是，在上述情况下，如果树已达到最大容量，则删除引用时间最早的页面

我尝试这样做的方法是按页码搜索第一棵树——这样我们就得到了一个也有创建/引用时间记录的节点，然后在第二棵树上搜索同时具有这两个记录的节点引用时间是那个页面。

困难在于引用时间可能不是唯一的(这是一个绝对障碍):是否有一种算法我可以在节点中实现，允许我搜索树以找到正确的节点而不破坏树代码...

现在是树代码...

template <typename NODE> NODE* redblacktree<NODE>::locatenode(NODE* v,
    NODE* node) const
{
if (node == NULL)
    return node;
if (v->equals(node))
    return node;
if (v->lessthan(node))
    return locatenode(v, node->left);
else
    return locatenode(v, node->right);
}

这是一个简单的(有效的)单一搜索代码，在节点端用于单一索引值:

bool PageRecord::operator==(PageRecord& pRecord) const
{
return (pageNumber == pRecord.getPageNumber());
}

bool PageRecord::operator<(PageRecord& pRecord) const
{
return (pageNumber < pRecord.getPageNumber());
}

Answer 1

更改 NODE 数据结构以允许节点中有多个页面。

typedef struct node
{
    int choice;  // if 1 then page tree, if 0 then reference tree
    vector<Page> pg;  // if choice=0
    Reference ref;  // if choice=1

    struct node* left;
    struct node* right;
}NODE;

您可以相应地修改equals 和lessthan 函数。 locatenode 函数保持不变。

---

我将添加一些关于这里使用的数据结构的内容。您实际上不需要树来维护引用。只有在以下情况下才需要引用:

• 如果页面存在，更新其引用时间为现在
• 但是，在上述情况下，如果树已达到最大容量，则删除引用时间最早的页面

所以这也可以使用堆来完成。这样做的好处是，插入操作只需要 O(1) 时间。

对于第一点，如果必须更新引用，则节点在堆中向下移动。所以维护一个从页树到引用堆的链接。并不断交换引用堆中的节点，直到当前节点走到最后一层。 O(logn) 时间。

第二点，删除堆的第一个节点。 O(logn) 时间在这里。

至于如果页面不存在 - 将页面添加到创建时间为现在的两棵树，将新节点添加到堆的末尾。 O(1) 时间。