Как создать красно-черное дерево в java

Question

Я работаю над красно-черным деревом и написал полный рабочий код, который я привел ниже. Я прошел учебник по универсальным средствам и понял, что с объявлением одного класса можно указать набор связанных методов. Как я могу применить его к моему алгоритму с красным черным деревом? Что происходит в случае дженериков? Если возможно, вы могли бы помочь мне с этим, пожалуйста? Это полный код:

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> 
   

   Подразумевается, что каждый узел хранит два значения - это ключ, который определяет местоположение в упорядоченном дереве и значение с нулевым значением, которое этого не делает. ValueType является необязательным, но он дает эффективную реализацию карты в виде дерева. (Помимо основаны на комментарий по 4castle: это не имеет смысла, чтобы заменить Comparable<KeyType> с Comparable<? super KeyType>, потому что это невозможно вставить Непро- KeyType сек в дерево)

2. реализации класса (Node класс): заменить два случая int key с KeyType key; добавить переменную экземпляра ValueType val (необязательно). При добавлении ValueType, узел Конструктор становится:

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

3. использование класса (метод consoleUI), тип-экземпляр KeyType и ValueType во Node декларации, Например:

   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 в него.