1
\$\begingroup\$

I am writing a program to implement the Red-Black Tree data structure in java. Below is the beginning of my implementation, namely the left and right rotate functions. I want to know if these functions are correct, and if not, any tips on correcting them. I am basing my functions off of pseudocode I found. Here is a link to the pseudocode I used. If you need to see the node class let me know however I think it is self explanatory for the most part.

pseudocode

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package rbtree;

/**
 *
 * @author williamnewman
 */
public class RBTree {
    node root;

   RBTree(int val){
       node r = new node();

       r.setVal(val);
       this.root = r;
   }

   void leftRotate(node x){
     node y = x.rightChild;
     x.rightChild = y.leftChild;
     if(y.leftChild != null){
         y.leftChild.parent = x;
     }
     y.parent = x.parent;
     if(x.parent == null)
         this.root = y;
     else if(x == x.parent.leftChild){
         x.parent.leftChild = y;
     }
     else{
         x.parent.rightChild = y;
     }
     y.leftChild = x;
     x.parent = y;
    }

   void rightRotate(node x){
       node y = x.leftChild;
       x.leftChild = y.rightChild;
       if(y.rightChild != null){
           y.rightChild.parent = x;
       }
       y.parent = x.parent;
       if(x.parent == null){
           this.root = y;
       }
       else if(x == x.parent.rightChild){
           x.parent.rightChild = y;
       }
       else{
           x.parent.leftChild = y;
       }
       y.rightChild = x;
       x.parent = y;
   }

}
\$\endgroup\$
0
\$\begingroup\$
  1. In Java class names should start with an upper letter (node->Node).
  2. Why all your methods have default visibility? You usually want to have public methods though if this intentional then just ignore this point.
  3. You seem to be restricting your RBTree to have only ints. You could use generics instead to make it more flexible and make it useful in more cases
  4. Your formatting is inconsistent (indentation).
\$\endgroup\$
  • \$\begingroup\$ The functions will work though? \$\endgroup\$ – Will Jul 16 '17 at 20:56
  • \$\begingroup\$ It should but the best way to know it is just to test it. The more tests (testing different cases) the more confident can you be that it works exactly as you want. From what I see though it should be okay \$\endgroup\$ – Mibac Jul 16 '17 at 20:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.