0 Replies - 348 Views - Last Post: 29 November 2010 - 08:46 PM

#1 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12634
  • View blog
  • Posts: 45,801
  • Joined: 27-December 08

Binary Tree Rotations

Posted 29 November 2010 - 08:46 PM

Description: Invoke this method, passing the root node of the Tree as well as the direction to rotate.Rotates binary tree by modifying the structure without modifying the order.
/***
  * @precondition: The TreeNodes are for a binary tree 
  * @param root: The TreeNode to rotate from
  * @param direction: true- left, false- right
  * @return TreeNode<E>: The new root of the tree
  *
  * This snippet modifies the structure of a binary
  * tree without modifying the order of the elements.
  * It is used often in balanced binary trees like AVL  
  * Trees to balance the Tree.
  * 
  * */
public static TreeNode<E> rotate(TreeNode<E> root, boolean direction){

     //the Node we are removing from the Root will be our new 
     //root Node
     TreeNode<E> temp = direction ? root.remove(0) : root.remove(1);

     //because temp will be promoted and will only have 2 children,
     //one of its Nodes will be displaced
     TreeNode<E> displaced = temp.remove(direction? 1 : 0);   

     //if we are shifting from the left, add the root to the right
     //otherwise, add the root to the left 
     temp.add((direction ? 1 : 0), root);

     //now add the removed Node back in as the root's child
     root.add(direction ? 0 : 1);

     //now that we have finished altering the Tree's structure
     //have the root point to temp 
     root = temp;
     return root;
}


Is This A Good Question/Topic? 0
  • +

Page 1 of 1