avl tree

i would like to know if...

i know how to write the functions for

Code:

---

void BST::LeftRotate(BSTNode* x) {}

---

&

Code:

---

void BST::RightRotate(BSTNode* y) {}

---

how do i return these void functions to another function so that i can move the item that has just recently searched to the root of the tree, by rotation to make searching more efficient?

since its void you dont return the results of these functions, as you know. simply call the function passing the address of the item recently moved, then 'return;', ie:

Code:

---

void BST::RightRotate(BSTNode* y)
{
    ....
    BST::RightRotate(itemNode);
    return;
}

---

hope this helps

it's not just about return; in the function. i need to move the node to root. and rotate it properly to be the root of the tree. So if the node found is a left subtree of its parent, rotate right at the parent node until it becomes root of the tree. i'm trying to combine it with the search function.

>so that i can move the item that has just recently searched to the root of the tree
Is this an AVL tree (as your thread title suggests)? If so, you're on the wrong track. The definition of the AVL algoritihm makes a move-to-front technique extremely difficult (bordering on impossible) to pull off efficiently in any useful situation.

>to make searching more efficient?
If your searches are heavily skewed to a small subset of the items then an AVL tree might not be your best bet. You should consider a splay tree instead. If your searches are relatively uniform then an AVL tree is about as efficient as it gets for lookup in balanced trees.

>i'm trying to combine it with the search function.
Like I said, if this is an AVL tree, you'd best forget about such a feature because it's going to be too hard for negligable gain. If it's not an AVL tree, you can find plenty of tricks here.

assuming my Binary search tree i want to make has characteristics like a splay tree instead.
then moving the desired node to the root node will greatly reduce the no. of steps the recursive function search performs. just wondering if i can make a program that recognises the search frequencies of desired nodes (input) and then move the node with the highest recurring search to the root.

>just wondering if i can make a program that recognises the search frequencies
>of desired nodes (input) and then move the node with the highest recurring search to the root.
That's exactly what a splay tree does. I don't see what the problem is here.

so if rotation occurs, the parent and grandparent of the particular node changes.
which nodes do i need to compare to? how do i determine left or right? i'm trying to create another function(node, value) that can call the left and right rotate functions which i written.

and i can't see the logic of a splay tree which recognises the node(user input) with the highest search frequency and move it to root. can u help?

>and i can't see the logic of a splay tree which recognises the node(user input)
>with the highest search frequency and move it to root.
That's the beauty of splay trees. You don't have to care. Every node is splayed, and the result is that the most frequently used items find themselves near the root.

>i'm trying to create another function(node, value) that can call the left and right rotate functions which i written.
What you want to do is write a splay function. Search google and you'll find them all over the place. Nag me enough and I'll finish up my splay tutorial and you'll find yet another resource.

ya i think i need ur resource. whether to rotate the parent or grandparent, left or right first, i really have no idea....