10

O（log n）時間で挿入、検索、削除機能を備えたRed Black Treeを実装しています。挿入と検索は正常に機能しています。しかし、私は削除に固執しています。RBT 削除のアルゴリズムを示すこの ppt スライドをインターネットで見つけました: http://www.slideshare.net/piotrszymanski/red-black-trees#btnNext 56 ページ以降。私は少し質問しすぎていることを知っていますが、2週間以上これに固執しており、問題を見つけることができません. 削除するノードの前任者が見つかるまで、それに応じてノードを回転させて色を変更する必要があるトップダウン削除を理解している方法。このノード (リーフまたは 1 つの右の子を持つノード) を見つけたら、削除するノードのデータをこのノードのデータに置き換え、通常の BST 削除のようにこのノードを削除しますよね?

これは、そのスライドから学んだことに基づいて作成したコードです。誰かが親切にそれを調べてくれるなら、私はもっと感謝しています! または、少なくとも私が使用しているものよりも優れたアルゴリズムがあると思われる場合は、教えてください!

 public void delete(int element){

    if (root == null){ 
        System.out.println("Red Black Tree is Empty!");

    } else {

      Node X = root; 
      parent = null; 
      grandParent = null; 
      sibling = null; 

      if (isLeaf(X)){

          if (X.getElement() == element){
              emptyRBT();
          } 

      } else {

      if (checkIfBlack(root.getLeftChild()) && checkIfBlack(root.getRightChild())){
          root.setIsBlack(false);

          if (X.getElement() > element && X.getLeftChild() != null){ 
              X = moveLeft(X);

          } else if (X.getElement() < element && X.getRightChild() != null){
              X = moveRight(X);
          } 

          Step2(X, element);

      } else { 

          Step2B(X, element);

       } 
     }
   } 
   root.setIsBlack(true);
}

public void Step2(Node X, int element)
{
    int dir = -1;

    while (!isLeaf(X)){

      if (predecessor == null){  // still didn't find Node to delete

        if (X.getElement() > element && X.getLeftChild() != null){
            X = moveLeft(X);
            dir = 0;
        } else if (X.getElement() < element && X.getRightChild() != null){
            X = moveRight(X);
            dir = 1;
        } else if (X.getElement() == element){
            toDelete = X;
            predecessor = inorderPredecessor(X.getRightChild());
            X = moveRight(X);
        }

      } else { // if node to delete is already found and X is equal to right node of to delete
               // move always to the left until you find predecessor

          if (X != predecessor){
              X = moveLeft(X);
              dir = 0;
          } 
      }

      if (!isLeaf(X)){
        if (!hasOneNullNode(X)){

         if (checkIfBlack(X.getLeftChild()) && checkIfBlack(X.getRightChild())){
             Step2A(X, element, dir);
         } else {
             Step2B(X, element);
         }
       }
     }
   }

   removeNode(X);

   if (predecessor != null){
       toDelete.setElement(X.getElement());
   }
}

public Node Step2A(Node X, int element, int dir) {

    if (checkIfBlack(sibling.getLeftChild()) && checkIfBlack(sibling.getRightChild())) {
        X = Step2A1(X);

    } else if ((checkIfBlack(sibling.getLeftChild()) == false) && checkIfBlack(sibling.getRightChild())) {
        X = Step2A2(X);

    } else if ((checkIfBlack(sibling.getLeftChild()) && (checkIfBlack(sibling.getRightChild()) == false))) {
        X = Step2A3(X);

    } else if ((checkIfBlack(sibling.getLeftChild()) == false) && (checkIfBlack(sibling.getRightChild()) == false)) {
        X = Step2A3(X);
    }

    return X;
}

public Node Step2A1(Node X) {

    X.setIsBlack(!X.IsBlack());
    parent.setIsBlack(!parent.IsBlack());
    sibling.setIsBlack(!sibling.IsBlack());

    return X;
}

public Node Step2A2(Node X) {

    if (parent.getLeftChild() == sibling){
        LeftRightRotation(sibling.getLeftChild(), sibling, parent);

    } else RightLeftRotation(sibling.getRightChild(), sibling, parent);

    X.setIsBlack(!X.IsBlack());
    parent.setIsBlack(!parent.IsBlack());

    return X;
}

public Node Step2A3(Node X) {

    if (parent.getLeftChild() == sibling){
        leftRotate(sibling);
    } else if (parent.getRightChild() == sibling){
        rightRotate(sibling);  
    }

    X.setIsBlack(!X.IsBlack());
    parent.setIsBlack(!parent.IsBlack());
    sibling.setIsBlack(!sibling.IsBlack());
    sibling.getRightChild().setIsBlack(!sibling.getRightChild().IsBlack());

    return X;
}

public void Step2B(Node X, int element){

    if (predecessor == null){
        if (X.getElement() > element && X.getLeftChild() != null){
            X = moveLeft(X);
        } else if (X.getElement() < element && X.getRightChild() != null){
            X = moveRight(X);
        } else if (X.getElement() == element){
            Step2(X, element);
        }

    } else {

        if (X != predecessor)
            X = moveLeft(X);
        else Step2(X, element);
    }

    if (X.IsBlack()){

       if (parent.getLeftChild() == sibling){
           leftRotate(sibling);
       } else if (parent.getRightChild() == sibling){
           rightRotate(sibling);
       }

       parent.setIsBlack(!parent.IsBlack());
       sibling.setIsBlack(!sibling.IsBlack()); 

       Step2(X, element);

    } else {
        Step2B(X, element);
    }
}

public void removeNode(Node X) {

    if (isLeaf(X)) {
        adjustParentPointer(null, X);
        count--;

    } else if (X.getLeftChild() != null && X.getRightChild() == null) {
        adjustParentPointer(X.getLeftChild(), X);
        count--;

    } else if (X.getRightChild() != null && X.getLeftChild() == null) {
        adjustParentPointer(X.getRightChild(), X);
        count--;
    } 
}

public Node inorderPredecessor(Node node){

   while (node.getLeftChild() != null){
       node = node.getLeftChild();
   }

   return node;
}

public void adjustParentPointer(Node node, Node current) {

    if (parent != null) {

        if (parent.getElement() < current.getElement()) {
            parent.setRightChild(node);
        } else if (parent.getElement() > current.getElement()) {
            parent.setLeftChild(node);
        }
    } else {
        root = node;
    }
}

public boolean checkIfBlack(Node n){
    if (n == null || n.IsBlack() == true){
        return true;
    } else return false;
}

public Node leftRotate(Node n)
{  
    parent.setLeftChild(n.getRightChild());
    n.setRightChild(parent);

    Node gp = grandParent;

    if (gp != null){

        if (gp.getElement() > n.getElement()){
            gp.setLeftChild(n);
        } else if (gp.getElement() < n.getElement()){
            gp.setRightChild(n);
        }

    } else root = n;

    return n;
}

public Node rightRotate(Node n)
{  
    parent.setRightChild(n.getLeftChild());
    n.setLeftChild(parent);

    Node gp = grandParent;

    if (gp != null){

        if (gp.getElement() > n.getElement()){
            gp.setLeftChild(n);
        } else if (gp.getElement() < n.getElement()){
            gp.setRightChild(n);
        }

    } else root = n;

    return n;
}

ノードは削除されていますが、削除後のツリーは黒く違反されており、これは非常に間違っています。

4

2 に答える 2

5

永遠に混乱しているブログには、赤黒木に対する挿入と削除の両方のトップダウン実装があります。また、それが機能する理由についてもケースバイケースで説明します。ここでは複製しません (かなり長いので)。

このブログは、C++ と Java の両方で赤黒木を実装するためのリファレンスとして使用しました。以前の回答で説明したように、この実装は std::map の赤黒ツリーのボトムアップ実装 (当時 gcc に付属していた STL が何であれ) よりも高速であることがわかりました。

これは、テストされていない、コードの Java への直接変換です。テストして、自分のスタイルに合うようにモーフィングすることを強くお勧めします。

private final static int LEFT = 0;
private final static int RIGHT = 1;

private static class Node {
    private Node left,right;
    private boolean red;
    ...

    // any non-zero argument returns right
    Node link(int direction) {
        return (direction == LEFT) ? this.left : this.right;
    }
    // any non-zero argument sets right
    Node setLink(int direction, Node n) {
        if (direction == LEFT) this.left = n;
        else this.right = n;
        return n;
    }
}

boolean remove(int data) {
  if ( this.root != null ) {
    final Node head = new Node(-1, null, null); /* False tree root */
    Node cur, parent, grandpa; /* Helpers */
    Node found = null;  /* Found item */
    int dir = RIGHT;

    /* Set up helpers */
    cur = head;
    grandpa = parent = null;
    cur.setLink(RIGHT, this.root);

    /* Search and push a red down */
    while ( cur.link(dir) != null ) {
      int last = dir;

      /* Update helpers */
      grandpa = parent, parent = cur;
      cur = cur.link(dir);
      dir = cur.data < data ? RIGHT : LEFT;

      /* Save found node */
      if ( cur.data == data )
        found = cur;

      /* Push the red node down */
      if ( !is_red(cur) && !is_red(cur.link(dir)) ) {
        if ( is_red(cur.link(~dir)) )
          parent = parent.setLink(last, singleRotate(cur, dir));
        else if ( !is_red(cur.link(~dir)) ) {
          Node s = parent.link(~last);

          if ( s != null ) {
            if (!is_red(s.link(~last)) && !is_red(s.link(last))) {
              /* Color flip */
              parent.red = false;
              s.red = true;
              cur.red = true;
            }
            else {
              int dir2 = grandpa.link(RIGHT) == parent ? RIGHT : LEFT;

              if ( is_red(s.link(last)) )
                grandpa.setLink(dir2, doubleRotate(parent, last));
              else if ( is_red(s.link(~last)) )
                grandpa.setLink(dir2, singleRotate(parent, last));

              /* Ensure correct coloring */
              cur.red = grandpa.link(dir2).red = true;
              grandpa.link(dir2).link(LEFT).red = false;
              grandpa.link(dir2).link(RIGHT).red = false;
            }
          }
        }
      }
    }

    /* Replace and remove if found */
    if ( found != null ) {
      found.data = cur.data;
      parent.setLink(
        parent.link(RIGHT) == cur ? RIGHT : LEFT,
        cur.link(cur.link(LEFT) == null ? RIGHT : LEFT));
    }

    /* Update root and make it black */
    this.root = head.link(RIGHT);
    if ( this.root != null )
      this.root.red = false;
  }

  return true;
}
于 2013-01-09T19:03:48.133 に答える
1

クイック リンク : http://algs4.cs.princeton.edu/33balanced/RedBlackBST.java.html

--> 注意 : サイトのコードは 2 つの jar に依存しています。ただし、データ構造では、依存関係は最小限である可能性があります。場合によっては、main メソッド (テスト クライアントとしてのみ機能する) をコメント アウトするだけで十分です。そうでない場合: jar は同じサイトでダウンロードできます。

2週間探してアルゴリズムを勉強しているなら、あなたは知っている可能性があります

http://algs4.cs.princeton.edu/

有名に付随するウェブサイト

アルゴリズム、Robert Sedgewick および Kevin Wayne 著

本。

この Web サイトには、赤黒 (バランス) ツリーの実装があります。

http://algs4.cs.princeton.edu/33balanced/RedBlackBST.java.html

私はまだそれを調べていませんでしたが (今年後半に調べます)、RBTree の実用的な実装であると完全に信頼しています。

このトピックの訪問者にとって興味深いかもしれないいくつかの補足事項: MIT はオンラインでアルゴリズムに関する優れたコースを配置しました。rbtrees に関するものは http://www.youtube.com/watch?v=iumaOUqoSCkです

于 2013-01-02T18:38:42.717 に答える