19
$\begingroup$

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.

$\endgroup$
12
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Why would he have to make this change? Either strategy is viable, and there are others. Besides, this is/was a homework question so hints are preferred to (uncommented) solutions. Lastly, this answer is redundant as it is; maybe you can change it to lead the OP towards your proposed solution? $\endgroup$ – Raphael Apr 12 '12 at 5:45
  • $\begingroup$ Well, a couple of hints for you then: 1. Have a look at splay function and see what it does, read the question and figure out, based on what it says, whether you modify the splay function or not. And no, not all strategies are viable since he has certain requirements to meet based on priority so shifting to the front all the time is not valid 2. Uncommented solution? How is my answer and uncommented solution? 3. "Redundant as it is"... I don't see how your answer, oops, sorry - hints are ultimate and my "uncommented solution" brings noting to the table $\endgroup$ – Bober02 Apr 12 '12 at 8:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.