red-blackツリーをJavaで汎用化する方法

Question

私はred-blackツリーで作業しており、以下に示した完全な作業コードを書いています。私はGenericsチュートリアルを見て、単一クラス宣言で、関連するメソッドのセットを指定することができることを理解しました。赤黒のツリーアルゴリズムにどのように適用できますか？ジェネリックスの場合はどうなりますか？可能であれば、これで私を助けてくれますか？

import java.util.Scanner; 

public class RedBlackTree { 

    private final int RED = 0; 
    private final int BLACK = 1; 


    private class Node { 

     int key = -1, color = BLACK; 
     Node left = nil, right = nil, parent = nil; 

     Node(int key) { 
      this.key = key; 
     } 
    } 

    private final Node nil = new Node(-1); 
    private Node root = nil; 

    public void printTree(Node node) 
    { 
     if (node == nil) { 
      return; 
     } 
     printTree(node.left); 
     System.out.print(((node.color==RED)?"Color: Red ":"Color: Black ")+"Key: "+node.key+" Parent: "+node.parent.key+"\n"); 
     printTree(node.right); 
    } 

    private Node findNode(Node findNode, Node node) 
    { 
     if (root == nil) { 
      return null; 
     } 

     if (findNode.key < node.key) { 
      if (node.left != nil) { 
       return findNode(findNode, node.left); 
      } 
     } else if (findNode.key > node.key) { 
      if (node.right != nil) { 
       return findNode(findNode, node.right); 
      } 
     } else if (findNode.key == node.key) { 
      return node; 
     } 
     return null; 
    } 

    private void insert(Node node) 
    { 
     Node temp = root; 
     if (root == nil) { 
      root = node; 
      node.color = BLACK; 
      node.parent = nil; 
     } else { 
      node.color = RED; 
      while (true) { 
       if (node.key < temp.key) { 
        if (temp.left == nil) { 
         temp.left = node; 
         node.parent = temp; 
         break; 
        } else { 
         temp = temp.left; 
        } 
       } else if (node.key >= temp.key) { 
        if (temp.right == nil) { 
         temp.right = node; 
         node.parent = temp; 
         break; 
        } else { 
         temp = temp.right; 
        } 
       } 
      } 
      fixTree(node); 
     } 
    } 

    private void fixTree(Node node) 
    { 
     while (node.parent.color == RED) { 
      Node uncle = nil; 
      if (node.parent == node.parent.parent.left) { 
       uncle = node.parent.parent.right; 

       if (uncle != nil && uncle.color == RED) { 
        node.parent.color = BLACK; 
        uncle.color = BLACK; 
        node.parent.parent.color = RED; 
        node = node.parent.parent; 
        continue; 
       } 
       if (node == node.parent.right) { 
        //Double rotation needed 
        node = node.parent; 
        rotateLeft(node); 
       } 
       node.parent.color = BLACK; 
       node.parent.parent.color = RED; 
       //if the "else if" code hasn't executed, this 
       //is a case where we only need a single rotation 
       rotateRight(node.parent.parent); 
      } else { 
       uncle = node.parent.parent.left; 
       if (uncle != nil && uncle.color == RED) { 
        node.parent.color = BLACK; 
        uncle.color = BLACK; 
        node.parent.parent.color = RED; 
        node = node.parent.parent; 
        continue; 
       } 
       if (node == node.parent.left) { 
        //Double rotation needed 
        node = node.parent; 
        rotateRight(node); 
       } 
       node.parent.color = BLACK; 
       node.parent.parent.color = RED; 

       rotateLeft(node.parent.parent); 
      } 
     } 
     root.color = BLACK; 
    } 

    void rotateLeft(Node node) 
    { 
     if (node.parent != nil) { 
      if (node == node.parent.left) { 
       node.parent.left = node.right; 
      } else { 
       node.parent.right = node.right; 
      } 
      node.right.parent = node.parent; 
      node.parent = node.right; 
      if (node.right.left != nil) { 
       node.right.left.parent = node; 
      } 
      node.right = node.right.left; 
      node.parent.left = node; 
     } else {//Need to rotate root 
      Node right = root.right; 
      root.right = right.left; 
      right.left.parent = root; 
      root.parent = right; 
      right.left = root; 
      right.parent = nil; 
      root = right; 
     } 
    } 

    void rotateRight(Node node) 
    { 
     if (node.parent != nil) { 
      if (node == node.parent.left) { 
       node.parent.left = node.left; 
      } else { 
       node.parent.right = node.left; 
      } 

      node.left.parent = node.parent; 
      node.parent = node.left; 
      if (node.left.right != nil) { 
       node.left.right.parent = node; 
      } 
      node.left = node.left.right; 
      node.parent.right = node; 
     } else {//Need to rotate root 
      Node left = root.left; 
      root.left = root.left.right; 
      left.right.parent = root; 
      root.parent = left; 
      left.right = root; 
      left.parent = nil; 
      root = left; 
     } 
    } 




    void replace(Node target, Node with){ 
      if(target.parent == nil){ 
       root = with; 
      }else if(target == target.parent.left){ 
       target.parent.left = with; 
      }else 
       target.parent.right = with; 
      with.parent = target.parent; 
    } 

    boolean delete(Node z){ 
     if((z = findNode(z, root))==null) 
      return false; 
     Node x; 
     Node y = z; 
     int y_original_color = y.color; 

     if(z.left == nil){ 
      x = z.right; 
      replace(z, z.right); 
     }else if(z.right == nil){ 
      x = z.left; 
      replace(z, z.left); 
     }else{ 
      y = treeMinimum(z.right); 
      y_original_color = y.color; 
      x = y.right; 
      if(y.parent == z) 
       x.parent = y; 
      else{ 
       replace(y, y.right); 
       y.right = z.right; 
       y.right.parent = y; 
      } 
      replace(z, y); 
      y.left = z.left; 
      y.left.parent = y; 
      y.color = z.color; 
     } 
     if(y_original_color==BLACK) 
      fixDelColor(x); 
     return true; 
    } 

    void fixDelColor(Node x){ 
     while(x!=root && x.color == BLACK){ 
      if(x == x.parent.left){ 
       Node w = x.parent.right; 
       if(w.color == RED){ 
        w.color = BLACK; 
        x.parent.color = RED; 
        rotateLeft(x.parent); 
        w = x.parent.right; 
       } 
       if(w.left.color == BLACK && w.right.color == BLACK){ 
        w.color = RED; 
        x = x.parent; 
        continue; 
       } 
       else if(w.right.color == BLACK){ 
        w.left.color = BLACK; 
        w.color = RED; 
        rotateRight(w); 
        w = x.parent.right; 
       } 
       if(w.right.color == RED){ 
        w.color = x.parent.color; 
        x.parent.color = BLACK; 
        w.right.color = BLACK; 
        rotateLeft(x.parent); 
        x = root; 
       } 
      }else{ 
       Node w = x.parent.left; 
       if(w.color == RED){ 
        w.color = BLACK; 
        x.parent.color = RED; 
        rotateRight(x.parent); 
        w = x.parent.left; 
       } 
       if(w.right.color == BLACK && w.left.color == BLACK){ 
        w.color = RED; 
        x = x.parent; 
        continue; 
       } 
       else if(w.left.color == BLACK){ 
        w.right.color = BLACK; 
        w.color = RED; 
        rotateLeft(w); 
        w = x.parent.left; 
       } 
       if(w.left.color == RED){ 
        w.color = x.parent.color; 
        x.parent.color = BLACK; 
        w.left.color = BLACK; 
        rotateRight(x.parent); 
        x = root; 
       } 
      } 
     } 
     x.color = BLACK; 
    } 

    Node treeMinimum(Node subTreeRoot) 
    { 
     while(subTreeRoot.left!=nil){ 
      subTreeRoot = subTreeRoot.left; 
     } 
     return subTreeRoot; 
    } 

    public void consoleUI() { 
     Scanner scan = new Scanner(System.in); 
     while (true) { 
      System.out.println("\n1. Insert() method\n" 
        + "2. ToString() method\n" 
        + "3. Contains() method\n" 
        + "4. Delete() method\n" 
        + "5. Exit \n"); 
      int choice = scan.nextInt(); 

      int item; 
      Node node; 
      switch (choice) { 
       case 1: 
        item = scan.nextInt(); 
        while (item != 001) { 
         node = new Node(item); 
         insert(node); 
         item = scan.nextInt(); 
        } 
        printTree(root); 
        break; 

        case 2: 
        printTree(root); 
        break; 

       case 3: 
        item = scan.nextInt(); 
        while (item != 001) { 
         node = new Node(item); 
         System.out.println((findNode(node, root) != null) ? "found" : "not found"); 
         item = scan.nextInt(); 
        } 
        break; 

        case 4: 
        item = scan.nextInt(); 
        while (item != 001) { 
         node = new Node(item); 
         System.out.print("\nDeleting item " + item); 
         if (delete(node)) { 
          System.out.print(": deleted!"); 
         } else { 
          System.out.print(": entered item does not exist!"); 
         } 
         item = scan.nextInt(); 
        } 
        System.out.println(); 
        printTree(root); 
        break; 

        case 5: 
        return; 

      } 
     } 
    } 
    public static void main(String[] args) { 
     RedBlackTree redblacktree = new RedBlackTree(); 
     redblacktree.consoleUI(); 
    } 
} 

Answer 1

エッセンシャルgenericiseする手順：

1. クラス宣言： - 決定キー、

   class RedBlackTree<KeyType extends Comparable<KeyType>, ValueType> 
   

   各ノードを格納することを2つの値を仮定し、これは完全なコードであります順序付けられたツリー内の位置と、そうでないnull可能な値。 ValueTypeはオプションですが、ツリーの形で効率的なマップ実装を行います。 （別に4castleでコメントに基づいて：それは木にKeyTypeの非挿入することは不可能ですので、それはComparable<? super KeyType>でComparable<KeyType>を交換しても意味がありません）

2. クラスの実装（Nodeクラス）：の2例を置き換えますint keyとKeyType key;インスタンス変数ValueType val（オプション）を追加します。 ValueTypeには、追加した場合、ノードのコンストラクタは次のようになる。

   Node(KeyValue key, KeyValue val) { 
       this.key = key; 
       this.val = val; 
   } 
   

3. クラスの使用（方法consoleUI）、Node宣言時KeyTypeとValueTypeのタイプ、インスタンス化、例：

   Node<Integer, String> node; 
   ... 
       node = new Node(item, val); 
   

   又は

   Node<Integer, Void> node; 
   ... 
       node = new Node(item, null); 
   

*結果*

import java.util.Scanner; 

public class RedBlackTree<KeyType extends Comparable<KeyType>, ValueType> { 

    private static final int RED = 0; 
    private static final int BLACK = 1; 
    private static final Node nil = new Node(-1); ****** 
    private Node root = nil; 

    private class Node { 
     KeyType key; 
     ValueType val; 
     color = BLACK; 
     Node left = nil, right = nil, parent = nil; 

     Node(int key) { 
     this.key = key; 
     this.val = val; 
     } 
    } 

    // believe remaining code is unchanged (except for adding val param) 
    // ... 
    // ... 

    public void consoleUI() { 
     Scanner scan = new Scanner(System.in); 
     while (true) { 
      System.out.println("\n1. Insert() method\n" 
       + "2. ToString() method\n" 
       + "3. Contains() method\n" 
       + "4. Delete() method\n" 
       + "5. Exit \n"); 
      int choice = scan.nextInt(); 

      int item; 
      Node<Integer, Void> node; 
      switch (choice) { 
       case 1: 
        item = scan.nextInt(); 
        while (item != 001) { 
         node = new Node(item, null); 

     etc 

一般の提案：それは木クラス自体の内部に埋め込まツリーの使用を持ってしても意味がありません。2.にあなたのクラスを破ります。クラスコールRedBlackTreeTestを作成し、consoleUIとmainをそれに移動します。