Creating a Self Ordering Binary Tree

Question

I have an assignment where I need to make use a binary search tree and alter it to self order itself such that items that are accessed the most (have a higher priority) are at the top of the tree, the root being the most accessed node.

The professor gave me the BST and node struct to work with, but trying to get my head around the algorithm to update the tree as things are being inserted is confusing me.

I know that as the insert is happening, it checks if the current node's data is less or greater than the current node, then recursively goes in the correct direction until it finds a null pointer and inserts itself there. and after it is inserted it increases the priority by 1.

template <class Type>
void BinarySearchTree<Type> ::  insert( const Type & x, BinaryNode<Type> * & t )
{
    if( t == NULL )
        t = new BinaryNode<Type>( x, NULL, NULL );
    else if( x < t->element )
        insert( x, t->left );
    else if( t->element < x )
        insert( x, t->right );
    else
        t->priority++;  // Duplicate; do nothing for right now
}

Now I need to figure out when the node is equal, how to re-order the tree so that the current node (who is equal to an already existing node) finds the existing node, increases that node's priority, then shifts it up if the root is a lower priority.

I think I have the idea down that the AVL logic would work, and when a shift would take place, it would be a single rotation right or a single rotation left.

Here's where I'm confused, don't really know where to start with creating an algorithm to solve the problem. Since the AVL algorithm works with keeping track of the balance of a tree, then rotating nodes left or right accordingly, this tree doesn't need to worry about being balanced, just that the nodes with the highest priority not have children with a higher priority.

Answer 1

Just two pointers:

1. If you want to actually combine the ideas of priority queues and binary search trees, think about combining heap and BST in one structure.
2. There is the concept of self-organising lists. The idea is to move recently accessed element to (or towards the) front in order to speed up future accesses to the same element, thusly "learning" the element distribution over time (with quality depending on the particular implementation). Maybe you can adapt this to trees?

---

Spoiler: Follow below links only if you have not been able to come up with something yourself.

1. This is called a treap.
2. Splay trees implement this idea.

Answer 2

Have a look at splay trees, they are really what you need. You would have to modify the splay function, not to move each accessed node all the way to the tree, but slowly upwards