2016-11-15 16 views
1

我在紅黑樹上工作,並寫下了它的完整工作代碼,我在下面給出了它。我經歷了泛型教程,並瞭解了使用單類聲明,可以指定一組相關的方法。我怎樣才能將它應用到我的紅黑樹算法?泛型情況下會發生什麼?如果可能,你能幫我解決這個問題嗎?這是全碼:如何在java中製作紅黑樹通用

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(); 
    } 
} 
+2

提示:'public class RedBlackTree >' – 4castle

+0

我建議你看看'TreeMap'的openjdk實現,因爲它使用帶泛型的紅黑樹。 http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/TreeMap.java – sprinter

回答

0

基本步驟genericise:

  1. 類聲明:

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

    假定每個節點存儲兩個值 - 一個關鍵,它決定在有序樹內的位置以及不可空的值。 ValueType是可選的,但它確實以樹的形式提供了有效的地圖實現。 (除了在評論由4castle基礎:它沒有任何意義與Comparable<? super KeyType>更換Comparable<KeyType>,因爲這是不可能插入非KeyType S插入樹)

  2. 類實現(Node類):替換這兩種情況int keyKeyType key;添加實例變量ValueType val(可選)。如果值類型加入,節點構造變爲:

    Node(KeyValue key, KeyValue val) { 
        this.key = key; 
        this.val = val; 
    } 
    
  3. 類的使用(方法consoleUI),期間Node聲明類型實例化KeyTypeValueType,例如:

    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並將consoleUImain移入其中。

+0

謝謝@格倫最好爲您的答案,我將它們應用到我的代碼但是,它沒有工作,由於錯誤。主要發生的錯誤是「不兼容的類型:int不能轉換爲KeyType,其中KeyType是類型變量:」我不能修復它們。如果可能的話,你可以出示工作代碼嗎?我很想理解這一點。提前致謝! –

+0

@sprinter不幸的是,我無法修復它們,我的意思是我在將int轉換爲時遇到了問題。你能告訴我你的實施嗎? –