Tree rotation algorithms

This is a discussion on Tree rotation algorithms within the C Programming forums, part of the General Programming Boards category; Can i get some good links /tutorials on tree rotation algorithms. Not exactly for balancing the tree.I need it just ...

  1. #1
    dpp
    dpp is offline
    Registered User
    Join Date
    Jan 2009
    Posts
    197

    Tree rotation algorithms

    Can i get some good links /tutorials on tree rotation algorithms.
    Not exactly for balancing the tree.I need it just to have a feel on rotations.

  2. #2
    Registered User
    Join Date
    Jun 2010
    Posts
    45
    Code:
         A
       /    \
     B      C
    
    becomes
    
       B
         \
          A
            \
             C
    think how you would do this step by step. what pointers would you change? do you need to keep temp pointers?

    unless im missing something, thats about all there is to tree rotation. any algorithm would come from you deciding which way to rotate

  3. #3
    Registered User
    Join Date
    Apr 2011
    Posts
    3
    Code:
    static void
    pvt_left_rotate(struct clib_rb_t *pTree, struct clib_rb_node_t *x){
        struct clib_rb_node_t *y;
        y = x->right;
        x->right = y->left;
        if (y->left != rb_sentinel)
            y->left->parent = x;
        if (y != rb_sentinel)
            y->parent = x->parent;
        if (x->parent){
            if (x == x->parent->left)
                x->parent->left = y;
            else
                x->parent->right = y;
        }
        else
            pTree->root = y;
        y->left = x;
        if (x != rb_sentinel)
            x->parent = y;
    }
    static void
    pvt_right_rotate(struct clib_rb_t *pTree, struct clib_rb_node_t *x) {
        struct clib_rb_node_t *y = x->left;
        x->left = y->right;
        if (y->right != rb_sentinel)
            y->right->parent = x;
        if (y != rb_sentinel)
            y->parent = x->parent;
        if (x->parent) {
            if (x == x->parent->right)
                x->parent->right = y;
            else
                x->parent->left = y;
        }
        else
            pTree->root = y;
        y->right = x;
        if (x != rb_sentinel)
            x->parent = y;
    }
    More Details: SourceForge.net Repository - [clibutils] Contents of /src/c_rb.c

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, 08: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, 09:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21