Thread: avl tree

  1. #1
    Registered User
    Join Date
    Nov 2005
    Posts
    29

    Question 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?

  2. #2
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    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

  3. #3
    Registered User
    Join Date
    Nov 2005
    Posts
    29

    move node to root

    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.

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >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.
    My best code is written with the delete key.

  5. #5
    Registered User
    Join Date
    Nov 2005
    Posts
    29
    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.
    Last edited by wind_lark; 10-24-2006 at 01:17 PM.

  6. #6
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >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.
    My best code is written with the delete key.

  7. #7
    Registered User
    Join Date
    Nov 2005
    Posts
    29
    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?

  8. #8
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >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.
    My best code is written with the delete key.

  9. #9
    Registered User
    Join Date
    Nov 2005
    Posts
    29

    Exclamation

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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  2. Binary Tree, couple questions
    By scoobasean in forum C Programming
    Replies: 3
    Last Post: 03-12-2005, 09:09 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM