Categories
28°C, New York
Home JAVA Red Black Tree Java

Red Black Tree Java

Red Black Tree vs AVL Tree

Prim's Algorithm with a Java Implementation

A Red-Black Tree is a self-balancing binary search tree where each node contains an extra bit for the storing colour either red or black. This structure ensures that the tree remains balanced during the insertions and deletion operation, so maintains an O(log n) time complexity for the basic operations. In the Red-Black Tree, each node is either red or black, the root of the tree is always black, and all leaves (NIL nodes) are black. If the red node has children then the children are always black which means no two red nodes are adjacent. Every path from the given node to the descendant leaves has the same number of black nodes. These can help the tree remain balanced so keeping the depth of the tree logarithmic relative to the number of nodes.

Organization of Red-Black Tree

A Red-Black Tree is a balanced binary search tree with specific properties that help maintain balance and ensure efficient operations. Now we can see the structure and organization of the Red-Black Tree:

Properties of Red-Black Tree:

  1. Every node is either black or red.
  2. The root of the Red-Black tree is always black.
  3. All null nodes (leaves) are black.
  4. Red nodes cannot have red children i.e. no two red nodes in the same row.
  5. Every path from the node to its descendant leaves has the same number of black nodes.

Representation of Red-Black Tree:


Explanation of the Image:

  1. The root of the Red-Black tree is 20 which is in black.
  2. Every path from root to leaves that means null nodes has same number of black nodes.
  3. Red nodes 15 and 30 have the black parents which are maintaining no two consecutive red nodes rule.

Implementation of Red-Black Tree:

Java 
// Java Program implement 
// Red-Black Tree

enum Color {
    RED, BLACK
}

// Node Class
class Node<T extends Comparable<T>> {
    T data;
    Node<T> left;
    Node<T> right;
    Node<T> parent;
    Color color;

    // Constructor to create a new node
    Node(T data) {
        this.data = data;
      
          // New nodes are always red when inserted
        this.color = Color.RED; 
        this.left = null;
        this.right = null;
        this.parent = null;
    }
}

public class RedBlackTree<T extends Comparable<T>> {
    private Node<T> root;
    private final Node<T> TNULL; // Sentinel node for null references

    // Constructor to initialize the Red-Black Tree
    public RedBlackTree() {
        TNULL = new Node<>(null);
        TNULL.color = Color.BLACK;
        root = TNULL;
    }

    // Preorder traversal helper function
    private void preOrderHelper(Node<T> node) {
        if (node != TNULL) {
            System.out.print(node.data + " ");
            preOrderHelper(node.left);
            preOrderHelper(node.right);
        }
    }

    // Function to start preorder traversal
    public void preorder() {
        preOrderHelper(this.root);
    }

    // Inorder traversal helper function
    private void inOrderHelper(Node<T> node) {
        if (node != TNULL) {
            inOrderHelper(node.left);
            System.out.print(node.data + " ");
            inOrderHelper(node.right);
        }
    }

    // Function to start inorder traversal
    public void inorder() {
        inOrderHelper(this.root);
    }

    // Postorder traversal helper function
    private void postOrderHelper(Node<T> node) {
        if (node != TNULL) {
            postOrderHelper(node.left);
            postOrderHelper(node.right);
            System.out.print(node.data + " ");
        }
    }

    // Function to start postorder traversal
    public void postorder() {
        postOrderHelper(this.root);
    }

    // Function to perform left rotation
    private void leftRotate(Node<T> x) {
        Node<T> y = x.right;
        x.right = y.left;
        if (y.left != TNULL) {
            y.left.parent = x;
        }
        y.parent = x.parent;
        if (x.parent == null) {
            this.root = y;
        } else if (x == x.parent.left) {
            x.parent.left = y;
        } else {
            x.parent.right = y;
        }
        y.left = x;
        x.parent = y;
    }

    // Function to perform right rotation
    private void rightRotate(Node<T> x) {
        Node<T> y = x.left;
        x.left = y.right;
        if (y.right != TNULL) {
            y.right.parent = x;
        }
        y.parent = x.parent;
        if (x.parent == null) {
            this.root = y;
        } else if (x == x.parent.right) {
            x.parent.right = y;
        } else {
            x.parent.left = y;
        }
        y.right = x;
        x.parent = y;
    }

    // Function to insert a new node
    public void insert(T key) {
        Node<T> node = new Node<>(key);
        node.parent = null;
        node.left = TNULL;
        node.right = TNULL;
        node.color = Color.RED; // New node must be red

        Node<T> y = null;
        Node<T> x = this.root;

        // Find the correct position to insert the new node
        while (x != TNULL) {
            y = x;
            if (node.data.compareTo(x.data) < 0) {
                x = x.left;
            } else {
                x = x.right;
            }
        }

        node.parent = y;
        if (y == null) {
            root = node;
        } else if (node.data.compareTo(y.data) < 0) {
            y.left = node;
        } else {
            y.right = node;
        }

        // Fix the tree if the properties are violated
        if (node.parent == null) {
            node.color = Color.BLACK;
            return;
        }

        if (node.parent.parent == null) {
            return;
        }

        fixInsert(node);
    }

    // Function to fix violations after insertion
    private void fixInsert(Node<T> k) {
        Node<T> u;
        while (k.parent.color == Color.RED) {
            if (k.parent == k.parent.parent.right) {
                u = k.parent.parent.left;
                if (u.color == Color.RED) {
                    u.color = Color.BLACK;
                    k.parent.color = Color.BLACK;
                    k.parent.parent.color = Color.RED;
                    k = k.parent.parent;
                } else {
                    if (k == k.parent.left) {
                        k = k.parent;
                        rightRotate(k);
                    }
                    k.parent.color = Color.BLACK;
                    k.parent.parent.color = Color.RED;
                    leftRotate(k.parent.parent);
                }
            } else {
                u = k.parent.parent.right;

                if (u.color == Color.RED) {
                    u.color = Color.BLACK;
                    k.parent.color = Color.BLACK;
                    k.parent.parent.color = Color.RED;
                    k = k.parent.parent;
                } else {
                    if (k == k.parent.right) {
                        k = k.parent;
                        leftRotate(k);
                    }
                    k.parent.color = Color.BLACK;
                    k.parent.parent.color = Color.RED;
                    rightRotate(k.parent.parent);
                }
            }
            if (k == root) {
                break;
            }
        }
        root.color = Color.BLACK;
    }

    // Main function to test the Red-Black Tree implementation
    public static void main(String[] args) {
        RedBlackTree<Integer> tree = new RedBlackTree<>();
        tree.insert(55);
        tree.insert(40);
        tree.insert(65);
        tree.insert(60);
        tree.insert(75);
        tree.insert(57);

        System.out.println("Preorder traversal:");
        tree.preorder();

        System.out.println("\nInorder traversal:");
        tree.inorder();

        System.out.println("\nPostorder traversal:");
        tree.postorder();
    }
}

Output:

Preorder traversal: 55 40 65 60 57 75 
Inorder traversal: 40 55 57 60 65 75 
Postorder traversal: 40 57 60 75 65 55

Complexity of the above Program:

Operation

Explanation

Complexity

Insertion Operation

Insertion operation is used to insert the new node into the Red-Black Tree while maintain the properties.

  • The time complexity of Insertion operation is O(log n).
  • The space complexity of Insertion operation is O(1).

Deletion Operation

Deletion operation is used to remove the node from Red-Black Tree while maintain the properties.

  • The time complexity of deletion operation is O(log n).
  • The space complexity of deletion operation is O(1).

Searching Operation

Search operation is used to find the node with the given key in Red-Black Tree

  • The time complexity of search operation is O(log n).
  • The space complexity of search operation is O(1).

Traversal Operation

Traversal Operation is used to visit the all nodes of Red-Black Tree in a certain order.

  • The time complexity of traversal operation is O(n).
  • The space complexity of traversal operation is O(log n).

Applications of Red-Black Tree

Red-Black Tree are used in the various applications where the balanced tree data structures are essential for the maintaining the efficient operations. Here is the some applications of the Red-Black Tree:

  1. Implementation of Associative Containers in Standard Libraries
  2. Event-Driven Simulations
  3. Compiler Design
  4. Operating Systems
  5. Networking
  6. Databases and File Systems
  7. Memory Management

Conclusion

In conclusion, Red-Black tree are the indispensable data structure in field of the computer science. It is providing the balanced and efficient solution for the dynamic data management. Their ability to maintain a balanced tree structure ensures logarithmic time complexity for the key operations such as insertion, deletion and searching. This efficiency makes the ideal for the wide range of application from the implementing associative containers in the standard libraries and managing memory in garbage collectors to optimizing routing tables in the networking and symbol tables in the compilers.



Tags:
#Java-DSA #Java #Java

Red Black Tree vs AVL Tree

Prim's Algorithm with a Java Implementation