left-leaning red-black tree

DO++に紹介してあったleft-leaning red-black treeという赤黒木の一種で実装が簡単なものを実装してみた．get,put,deleteを実装したところ156行となった．アルゴリズムイントロダクションの実装が疑似コードで150行程度なので*1．

また，JavaのTreeMapと挿入+検索+削除の合計の実行時間を比較したところオーダー的にはほぼ同程度の性能となった*2．

public class LLRB <Key extends Comparable<Key> , Value>{
  private static final boolean RED = true;
  private static final boolean BLACK = false;  
  private Node root;
  private class Node{
    private Key key;
    private Value val;
    private Node left , right;
    private boolean color;
    
    Node(Key key , Value val , boolean color){
      this.key = key;
      this.val = val;
      this.color = color;
    }
  }
  
  public Value get(Key key){
    return get(root , key);
  }
  
  public void put(Key key , Value value){
    root = put(root, key , value);
    root.color = BLACK;
  }
    
  public boolean isEmpty(){
    return root == null;
  }
  
  public boolean containsKey(Key key){
    return get(key) != null;
  }
  
  public void delete(Key key){
    root = delete(root , key);
    if(root != null)root.color = BLACK;
  }

  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.left;
      else x = x.right;
    }
    return null;
  }
    
  private Node put(Node h , Key key , Value value){
    if(h == null)return new Node(key , value , RED);    
    int cmp = key.compareTo(h.key);
    if(cmp == 0) h.val = value;
    else if(cmp < 0) h.left = put(h.left, key, value);
    else h.right = put(h.right , key , value);
    if(isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
    if(isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
    if(isRed(h.left) && isRed(h.right))flipColors(h);
    return h;
  }

  private Node delete(Node h , Key key){
    if(key.compareTo(h.key) < 0){
      if(!isRed(h.left) && !isRed(h.left.left))
        h = moveRedLeft(h);
      h.left = delete(h.left, key);
    }else{
      if(isRed(h.left))
        h = rotateRight(h);
      if(key.compareTo(h.key) == 0 && h.right == null)
        return null;
      if(!isRed(h.right) && !isRed(h.right.left))
        h = moveRedRight(h);
      if(key.compareTo(h.key) == 0){
        h.val = get(h.right , min(h.right));
        h.key = min(h.right);
        h.right = deleteMin(h.right);
      }else
        h.right = delete(h.right , key);
    }
    return fixUp(h);
  }

  private Key min(Node h){
    if(h.left == null)return h.key;
    return min(h.left);
  }

  private Node deleteMin(Node h){
    if(h.left == null)return null;
    if(!isRed(h.left) && !isRed(h.left.left))
      h = moveRedLeft(h);
    h.left = deleteMin(h.left);
    return fixUp(h);
  }
   
  private Node moveRedLeft(Node h){
    flipColors(h);
    if(isRed(h.right.left)){
      h.right = rotateRight(h.right);
      h = rotateLeft(h);
      flipColors(h);
    }
    return h;
  }
  
  private Node moveRedRight(Node h){
    flipColors(h);
    if(isRed(h.left.left)){
      h = rotateRight(h);
      flipColors(h);
    }
    return h;
  }
  
  private Node fixUp(Node h){
    if(isRed(h.right))
      h = rotateLeft(h);
    if(isRed(h.left) && isRed(h.left.left))
      h = rotateRight(h);
    if(isRed(h.left) && isRed(h.right))
      flipColors(h);
    return h;
  }
  
  private Node rotateLeft(Node h){
    Node x = h.right;
    h.right = x.left;
    x.left = h;
    x.color = h.color;
    h.color = RED;
    return x;
  }
  
  private Node rotateRight(Node h){
    Node x = h.left;
    h.left = x.right;
    x.right = h;
    x.color = h.color;
    h.color = RED;
    return x;
  }
  
  private void flipColors(Node h){
    h.color = !h.color;
    h.left.color = !h.left.color;
    h.right.color = !h.right.color;
  }
  
  private boolean isRed(Node h){
    if(h == null)return false;
    return h.color == RED;
  }
}

*1:FIXUPのところは倍で数えています

*2:両対数なので実際は倍程度速度が違います，まあ定数倍なので大した問題ではない