Структура RedBlackTrees?

Question

Мне не удастся окунуться в redbacktrees, основываясь на этой реализации http://pastebin.com/Gg3YbPUg.

/** 
* Insert into the tree. 
* @param item the item to insert. 
* @throws DuplicateItemException if item is already present. 
*/ 
public void insert(AnyType item) 
{ 
    current = parent = grand = header; 
    nullNode.element = item; 

    while(compare(item, current) != 0) 
    { 
     great = grand; grand = parent; parent = current; 
     current = compare(item, current) < 0 ? 
        current.left : current.right; 

      // Check if two red children; fix if so 
     if(current.left.color == RED && current.right.color == RED) 
      handleReorient(item); 
    } 

     // Insertion fails if already present 
    if(current != nullNode) 
     throw new DuplicateItemException(item.toString()); 
    current = new RedBlackNode<AnyType>(item, nullNode, nullNode); 

     // Attach to parent 
    if(compare(item, parent) < 0) 
     parent.left = current; 
    else 
     parent.right = current; 
    handleReorient(item); 
} 

Я только что сделал простое дерево, используя номер 1,14,15,2,11,7,5,8

// Test program 
public static void main(String [ ] args) 
{ 
    RedBlackTree<Integer> t = new RedBlackTree<Integer>(); 

    t.insert(1); 
    t.insert(14); 
    t.insert(15); 
    t.insert(2); 
    t.insert(11); 
    t.insert(7); 
    t.insert(5); 
    t.insert(8); 

    t.printTree(); 
} 

И построен на пример из http://www.cs.auckland.ac.nz/software/AlgAnim/red_black.html, моего дерева должен выглядеть как ...

И мой консольный вывод из функции printTree

/** 
* Print all items. 
*/ 
public void printTree() 
{ 
    printTree(header.right); 
} 

/** 
* Internal method to print a subtree in sorted order. 
* @param t the node that roots the tree. 
*/ 
private void printTree(RedBlackNode<AnyType> t) 
{ 
    if(t != nullNode) 
    { 
     printTree(t.left); 
     System.out.println("main element is <" + t.element + "("+t.color+")> left <" + t.left.element +"> right <" + t.right.element + ">"); 
     printTree(t.right); 
    } 
} 

Is ...

main element is <1(COLOR:RED)> left <8> right <8> 
main element is <2(COLOR:BLACK)> left <1> right <5> 
main element is <5(COLOR:RED)> left <8> right <8> 
main element is <7(COLOR:RED)> left <2> right <14> 
main element is <8(COLOR:BLACK)> left <8> right <8> 
main element is <11(COLOR:RED)> left <8> right <8> 
main element is <14(COLOR:BLACK)> left <11> right <15> 
main element is <15(COLOR:RED)> left <8> right <8> 

(для целей чтения я переименовал 0 и 1, как цвет красный и черный) Из того, что я понимаю, что переменная «заголовок» является корнем дерева.

Если бы я должен был сделать что-то вроде

public void function(AnyType x) 
{ 
    RedBlackNode<AnyType> n = find(x); 
    //what is the parent of n? 
} 

/** 
* Find an item in the tree. 
* @param x the item to search for. 
* @return the matching item or null if not found. 
*/ 
public RedBlackNode<AnyType> find(AnyType x) 
{ 
    nullNode.element = x; 
    current = header.right; 

    for(; ;) 
    { 
     if(x.compareTo(current.element) < 0) 
      current = current.left; 
     else if(x.compareTo(current.element) > 0) 
      current = current.right; 
     else if(current != nullNode) 
      return current; 
     else 
      return null; 
    } 
} 

Из вышеприведенного реализации Pastebin из RedBlackTree, как я знаю, что мой текущий родительский элемент для п?

Answer 1

Если это правильное красно-черное дерево, оно соблюдает правила, то корень имеет, чтобы быть черным, поэтому 1 не может быть корнем.

Я построить красно-черное дерево в Java, которая имеет гораздо лучше распечатку, если вы заинтересованы:

└── (Black) 8 
    ├── (Black) 2 
    │ ├── (Red) 1 
    │ │ ├── (Black) null 
    │ │ └── (Black) null 
    │ └── (Red) 5 
    │  ├── (Black) null 
    │  └── (Black) null 
    └── (Red) 15 
     ├── (Black) 11 
     │ ├── (Black) null 
     │ └── (Red) 14 
     │  ├── (Black) null 
     │  └── (Black) null 
     └── (Black) 17 
      ├── (Black) null 
      └── (Black) null 

Here это код на красно-черное дерево, проверьте RedBlackTreePrinter класс, чтобы посмотреть, как я построил консольный вывод.