Binary search trees - ordering by two data items

Question

I want to maintain two related binary search trees the nodes of which hold two items of data - a page number and a time of creation/reference (the details are not that important - essentially it is two 64 bit numbers).

The first tree is ordered by page number, the second by time of creation - essentially the use case is:

• Find if the page exists (is in the tree), searching by page number
• If the page exists, update its reference time to now
• If the page does not exist - add the page to both trees with a creation time of now
• But, in the case above, if the tree has reached maximum capacity delete a page with the oldest reference time

The way I tried to do this was to search the first tree by page number - thus we get back a node that has also a record of the creation/reference time, then search the second tree for a node that has both that reference time and is that page.

The difficulty is that the reference time may not be unique (this is an absolute barrier): is there an algorithm I can implement in the node that allows me to search through the tree to find the correct node without breaking the tree code...

This the tree code now...

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);
}

And here is a simple (working) single search piece of code at the node end for a single indexing value:

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

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

Answer 1

Change the NODE data structure to allow more than one page in the 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;

You can modify the equals and lessthan functions accordingly. The locatenode function remains the same.

---

I'll add something about the data structures used here. You actually don't need a tree to maintain the references. References are required only when:

• If the page exists, update its reference time to now
• But, in the case above, if the tree has reached maximum capacity delete a page with the oldest reference time

So this can be done using a heap as well. The advantage is that, then insert operation will cost only O(1) time.

For the first point, if reference has to updated, the node goes downward in the heap. So maintain a link from the page tree to the reference heap. And continue swapping the nodes in the reference heap until the current node goes to the last level. O(logn) time.

For the second point, delete the first node of the heap. O(logn) time here.

And as for If the page does not exist - add the page to both trees with a creation time of now, add the new node at the end of the heap. O(1) time.