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.
/*
* 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;
}
}
