如何在java中制作红黑树通用

我在红黑树上工作，并写下了它的完整工作代码，我在下面给出了它。我经历了泛型教程，并了解了使用单类声明，可以指定一组相关的方法。我怎样才能将它应用到我的红黑树算法？泛型情况下会发生什么？如果可能，你能帮我解决这个问题吗？这是全码：如何在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(); 
    } 
}

来源

2016-11-15 John Doe

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

我建议你看看'TreeMap'的openjdk实现，因为它使用带泛型的红黑树。 http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/TreeMap.java – sprinter

基本步骤genericise：

类声明：
```
class RedBlackTree<KeyType extends Comparable<KeyType>, ValueType> 
```
假定每个节点存储两个值 - 一个关键，它决定在有序树内的位置以及不可空的值。 ValueType是可选的，但它确实以树的形式提供了有效的地图实现。（除了在评论由4castle基础：它没有任何意义与Comparable<? super KeyType>更换Comparable<KeyType>，因为这是不可能插入非KeyType S插入树）
类实现（Node类）：替换这两种情况int key与KeyType key;添加实例变量ValueType val（可选）。如果值类型加入，节点构造变为：
```
Node(KeyValue key, KeyValue val) { 
    this.key = key; 
    this.val = val; 
} 
```

类的使用（方法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移入其中。

来源

2016-11-15 09:09:16

谢谢@格伦最好为您的答案，我将它们应用到我的代码但是，它没有工作，由于错误。主要发生的错误是“不兼容的类型：int不能转换为KeyType，其中KeyType是类型变量：”我不能修复它们。如果可能的话，你可以出示工作代码吗？我很想理解这一点。提前致谢！ –

@sprinter不幸的是，我无法修复它们，我的意思是我在将int转换为时遇到了问题。你能告诉我你的实施吗？ –

如何在java中制作红黑树通用

回答

相关问题