# Java Implementations

## Node Implementation

```java
private static final boolean RED = true;
private static final boolean BLACK = false;

class TreeNode{
    private Key key;
    private Value val;
    private TreeNode left;
    private TreeNode right;
    private boolean color;
    
    // ....... constructor ........
}

private boolean isRed(Node x){
    if(x == null) return false;
    return x.color == RED;
}
```

![](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-2eca29dccf53b979da184278fab2dde639506dad%2Fimage%20\(74\).png?alt=media)

## Search Operation

**Observation**. Search is the same as for elementary BST ( ignore color ).

![](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-868b6c3758c0fa2cd595167570b48a01b6389bb4%2Fimage%20\(35\).png?alt=media)

```java
public class redBlackTree {
    public key search(TreeNode x, key key){
        if(x == null) return null;
        while(x!=null){
            int cmp = (key).compareTo(x.key);
            if( cmp < 0 ) x = x.left;
            else if( cmp > 0 ) x = x.right;
            else return  x.key;
        }
        return null;
    }
}
```

## Elementary operations

### Left Rotation

![](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-ffa046fd55988085ba1d8f52ea30285caa39a26c%2Fimage%20\(79\).png?alt=media)

![](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-a5f652572118c554db4ccfd5289fafcb8f5f16be%2Fimage%20\(51\).png?alt=media)

```java
private TreeNode rotateLeft(TreeNode h)
 {
     assert isRed(h.right);
     TreeNode x = h.right;
     h.right = x.left;
     x.left = h;
     x.color = h.color;
     h.color = RED;
     return x;
 }
```

### Right Rotation

**Invariants:** Maintains symmetric order and perfect black balance.

![](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-f1dc316c7542133cc4a528154cbcad520aa48bbb%2Fimage%20\(81\).png?alt=media)

![](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-23594a878cc6eda28e37c8a2bd3808f303a4e89c%2Fimage%20\(54\).png?alt=media)

```java
private TreeNode rotateRight(TreeNode h)
 {
     assert isRed(h.left);
     TreeNode x = h.left;
     h.left = x.right;
     x.right = h;
     x.color = h.color;
     h.color = RED;
     return x;
 }
```

### Color Flip

![](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-5467da31b6b1d633d69f876f7229ab82b1775d2e%2Fimage%20\(78\).png?alt=media)

![](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-5c28de407bd822c106d3dc22ea631e1e5a982512%2Fimage%20\(56\).png?alt=media)

```java
public void colorFlip(TreeNode h){
    assert !isRed(h);
    assert isRed(h.left);
    assert isRed(h.right);
    h.color = RED;
    h.left.color = BLACK;
    h.right.color = BLACK;
}
```

## Insertion

**Basic Strategy:** Maintain 1-1 correspondence with 2-3 trees by applying elementary red-black BST operations.

### Case 1: Into Exactly 2-node

* Do standard BST insert; color new link red
* If new red link is a right link, rotate left.

![Explanation for inserting a node in 2-node](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-3cb730ccefbaf95d235ad35ca09382a0d74295cd%2Fimage%20\(38\).png?alt=media)

**Example**: Insert ' C '

![Example for inserting a node in 2-node](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-e566f6aa6b75129950fdc6a60f91e302a65667d3%2Fimage%20\(46\).png?alt=media)

### Case 2: Insert into 3-node

* Do standard BST insert; color new link red.
* Rotate to balance the 4-node ( if needed ).
* Flip colors to pass red link up one level.
* Rotate to make lean left (if needed).

![Explanation for inserting a node in 3-node](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-add6d525603ea1c9333faeb3abec8f51acb4c82f%2Fimage%20\(64\).png?alt=media)

**Example**: Inserting ' H '

![Example for inserting a node in 3-node Red Black Tree](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-fb7ed14d2967ee979743af1c47b845b80b967503%2Fimage%20\(55\).png?alt=media)

### Passing red links up the tree

* Do standard BST insert; color new link red.
* Rotate to balance the 4-node ( if needed ).
* Flip colors to pass red link up one level.
* Rotate to make lean left (if needed).
* Repeat case 1, case 2 ( if needed ).

**Example:**

![](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-092c7237ac0472769404bdf3bec1e92d78eecc33%2Fimage%20\(36\).png?alt=media)

### Java Implementation

```java
private Node put(Node h, Key key, Value val)
 {
     // insert at bottom with color RED
     if (h == null) return new Node(key, val, RED);
     int cmp = key.compareTo(h.key);
     
     if (cmp < 0) h.left = put(h.left, key, val);
     else if (cmp > 0) h.right = put(h.right, key, val);
     else if (cmp == 0) h.val = val;
     
     //lean left
     // Right child red, left child black: rotate left.
     if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
     
     // balance 4-node
     // Left child, left-left grandchild red: rotate right.
     if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
     
     // split 4-node
     // Both children red: flip colors.
     if (isRed(h.left) && isRed(h.right)) flipColors(h);
    
     return h;
 }
```

## Delete

Delete operations are bit complicated.