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