2

この実装http://pastebin.com/Gg3YbPUgに基づいて、redbacktreesに頭を悩ませることはできません。

/**
 * 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の例に基づくと、MyTreeは次のようになります...

RBT

そして、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 );
    }
}

は...

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の名前をCOLOR RED AND BLACKに変更しました）私が理解していることから、「header」変数はツリーのルートです。

私が次のようなことをする場合

 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;
    }
}

上記のRedBlackTreeのpastebin実装から、現在の親要素がnに対して何であるかをどのように知ることができますか？

4

1 に答える 1

3

それが適切な赤黒木であり、規則を順守している場合、ルートは黒である必要があるため、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

これが赤黒木へのコードです。RedBlackTreePrinterクラスをチェックして、コンソール出力をどのように構築したかを確認してください。

于 2012-05-29T13:30:17.400 に答える