[Data Structure (Java)] Tree (6) - 2-3 Tree & LLRB Tree

 

https://crane206265.tistory.com/92

 

[Data Structure (Java)] Tree (5) - AVL Tree

아마도 마지막 Tree 글일거 같아요. 2-3 Tree와 LLRB Tree에 대해 알아봅시다.

---

2-3 Tree

: tree with symmetric order and perfect balance that allows 2-node or 3-node

- 2-node : 1 key, 2 children in node

- 3-node : 2 key, 3 children in node (one for smaller, one for between, one for greater)

- perfect balance : every path from the root to a null link has the same length

 

- generalization of BST to privoid flexibility (faster performance)

- symmetric order -> inorder traversal : ascending order

 

* inorder traversal in 2-3 tree

  - 2-node : left -> parent -> right

  - 3-node : left -> smaller parent -> middle -> larger parent -> right  

 

 

<Operations>

search
: as BST, comparing with keys

insert
: as BST, but manipulate 3-nodes to keep the tree balanced perfectly

- insertion into a 2-node : add new key to create a 3-node
- insertion into a 3-node : create 4-node(temporary) -> move middle key to parent
                                         -> smaller, larger key becomes child
repeat "move-up" until become 2-3 tree

* splitting 4-node : local transformation
--> constant # of operations
--> maintain symmetric order & perfect balance

 

* perfect balance

--> worst case : all 2-nodes -> $O(log_2{N})$

--> best case : all 3-nodes -> $O(log_3{N})$

---

LLRB : Left-Leaning Red-Black Tree

: represent 2-3 tree as a BST (way to implement 2-3 tree easily)

: use "internal" left-leaning links as "glue" for 3-nodes

 

3-node representation in LLRB

3-node has 2 keys
--> to BST : larger key is parent / smaller key is child - linked with red link("glue")
- less / between child : child of smaller key
- smaller key / greater child : child of larger key

 

<Invarients of LLRB Tree>
- no node has two red links coonected to it
- red links lean left
- every path from root to null link has the same # of black links

 

* 1-1 correspondence between 2-3 tree and LLRB tree :

red-black tree $\Leftrightarrow$ BST with horizontal red links $\Leftrightarrow$ 2-3 tree (merge red links)

---

LLRB API

API of LLBR<Key, Value>

methods	explanation
boolean isEmpty()	return if tree is empty
int size()	return # of node in the tree
boolean contains(Key key)	return if the entry associated the given key exists
Value get(Key key)	return the value associated with the give key (if it does not exist : return null)
void put(Key key, Value val)	if key exist : replace the associated value to the given value else : add the given entry (key, val)
int height()	return the height of the tree

 

To restore color invariants : color flips & rotations
- left rotation : orient a right-leaning red link to lean left
- right rotation : orient a left-leaning red link to lean right (temporarily)
- color flip : recolor to split 4-node
(* all of these maintains symmetric order & perfect black balance)

 

insertion implementation

: do standard BST insert -> color new link red
-> repeat up the tree until color invariants restored
(1) if only right link red : left rotation
(2) if two left red links in a row : right rotation
(3) if left and right links both red : color flip

---

LLRB Implementation

import java.lang.Comparable;

public class LLRB<Key extends Comparable<Key>, Value> {
    //----- constructor & instance variables -----
    private static final boolean RED = true;
    private static final boolean BLACK = false;
    private Node root;
    private int n;

    private class Node {
        Key key;
        Value val;
        Node left, right;
        boolean color; //color of parent link -> RED = true, BLACK = false

        public Node(Key key, Value val, boolean color) {
            this.key = key;
            this.val = val;
            this.color = color;
        }
    }

    public LLRB() {}


    //----- methods -----
    public boolean isEmpty() {
        return n == 0;
    }

    public int size() {
        return n;
    }

    public Value get(Key key) {
        return get(root, key);
    }

    private Value get(Node x, Key key) {
        while(x != null) {
            int cmp = key.compareTo(x.key);
            if(cmp == 0) return x.val;
            else if(cmp > 0) x = x.right;
            else if(cmp < 0) x = x.left;
        }
        return null;
    }

    public boolean contains(Key key) {
        return get(key) != null;
    }

    public void put(Key key, Value val) {
        root = insert(root, key, val);
        root.color = BLACK;
    }
    
    public Node insert(Node x, Key key, Value val) {
        if(x == null) {
            n++;
            return new Node(key, val, RED);
        }

        int cmp = key.compareTo(x.key);
        if(cmp == 0) x.val = val;
        else if(cmp > 0) x.right = insert(x.right, key, val);
        else if(cmp < 0) x.left = insert(x.left, key, val);

        if(!isRed(x.left) && isRed(x.right)) x= leftRotation(x);
        if(isRed(x.left) && isRed(x.left.left)) x = rightRotation(x);
        if(isRed(x.left) && isRed(x.right)) x = colorFlip(x);

        return x;
    }

    public int height() {
        return height(root);
    }

    public int height(Node x) {
        if(x == null) return -1;
        else return 1 + Math.max(height(x.left), height(x.right));
    }

    //----- helper methods -----
    private boolean isRed(Node x) {
        if(x == null) return false;
        return x.color == RED;
    }

    private Node leftRotation(Node x) {
        Node t = x.right;
        x.right = t.left;
        t.left = x;
        t.color = x.color;
        x.color = RED;
        return t;
    }

    private Node rightRotation(Node x) {
        Node t = x.left;
        x.left = t.right;
        t.right = x;
        t.color = x.color;
        x.color = RED;
        return t;
    }

    private Node colorFlip(Node x) {
        x.color = RED;
        x.left.color = BLACK;
        x.right.color = BLACK;
        return x;
    }
}

 

Running Time Analysis

height : O(log n)
(<- perfect balanced && never two red links in a row)

==> search(), insert(), delete() : O(log n)
(in worst case, better then BST)