赤黒の木。プロパティ、組織の原則、挿入メカニズム。

赤黒ツリーの概念 赤黒ツリーは二分木の一種で あり、その主な本質は自己バランスをとる能力です。自己バランス ツリーにはいくつかの種類がありますが、この記事では赤黒ツリー (RCB) についてのみ説明します。バランスは、ツリー ノードの追加属性「カラー」を導入することで実現されます。各ツリー ノードは、要素に加えて、ノードが赤か黒かに関する 1 ビットの情報を格納します。これは色だけでなく、あるタイプのノードを別のタイプのノードから区別できるようにするその他の情報も含めることができます。たとえば、1 または 0、true または false などです。KChD の構成 (プロパティ) の原則: 1. ツリーのルートは黒です。2. データを含まないすべての葉は黒です 。 3. 各赤いノードの子は両方とも黒です。 4.黒ノード の深さはどのサブツリーでも同じです。 ツリーに対して実行される主な操作は次のとおりです。 1. 検索 2. ノードの挿入element 3 要素の削除 (delete) 最後の 2 つの操作は明らかにツリーの構造の変更につながるため、結果としてツリーの不均衡が生じる可能性があります。 時間と空間の複雑さ。 時間計算量 QCD の挿入、削除、および検索操作はO(log n) です。ここで、n はツリー内のノードの数です。これらを実行するには、それぞれのサブツリーの 1 つを破棄して目的のノードに到達する必要があるためです。ステップ。挿入または削除によって CCH のプロパティが侵害される場合は、リバランスを実行する必要があります。バランス調整は、再カラー O(1) と回転 O(1) の 2 つの操作で構成されます。各バランス調整操作には、子要素と親要素のリンクとその色に関する情報の書き換えが含まれるため、一定の時間がかかります。ただし、要素を挿入または削除する場合、ツリーの最下位ノードからルートに至るまでバランスをとる必要がある状況が発生する場合があります。n ノードで構成される CCH の最大高さは 2log(n + 1) 以下であることが保証されているため、最悪の場合、リバランスには log(n) - 操作が必要になる可能性があります。挿入には新しいノードの作成のみが含まれるため、 挿入のメモリコストはO(1)であり、バランス操作と再描画操作には追加のメモリは必要ありません。木のバランスが崩れているかどうかはどうやって判断できるのでしょうか? KChD の場合、前述のすべての特性が満たされていれば、バランスが取れた状態になります。 インバランス状態には 4 種類あります。 1. 左右アンバランス (LL) 2. 左右アンバランス (RR) 3. 左右アンバランス (LR) 4. 左右アンバランス (RL) 最初の 2 つの状態も同様です 。リニア(Line)と呼ばれる視覚的には、片側に傾いた直線の枝として表現できるためです。残りの 2 つは三角形と呼ばれます。CCH をバランスの取れた状態にするには、回転と呼ばれる操作を実行する必要があります。 これら 4 つのタイプのバランスをとるために、2 つのタイプの回転が使用されます。 1. LL および RR の場合 2. LR および RL の場合 1 つ目のタイプは、中央が上になるように最初のノードを引き下げることです。視覚的には、これは、ノードが実際に釘にぶら下がっているロープ上のノードであるかのように表すことができます。 回転自体は次のようになります。 複雑な LL 回転では、ノードにも子孫がある場合、原則は同じですが、正しいものになります。親となるノードの子は、プルされるノードの左/右の子になります。例: 2 番目のタイプ (LR、RL) は2 つのステージで構成され、最初にツリーを最初の状態にし、次に最初のノードをプルダウンします。 この図を見ると、単に移動している だけであることがわかります。一番下のノードを一番上のノードに変更して、それを「新しい」祖父にし、「元の」祖父を左または右の子のいずれかにします。例: 複雑な LR/RL ローテーションでは、ノードにも子孫がある場合、原則は同じですが、「新しい」親の以前の子孫が、子ノードの子孫の空いた場所を占めます。例: 赤黒ツリーの プログラム コード 理論については説明しましたが、次に CNC デバイスが Java プログラミング言語でどのように構成されているかを見てみましょう。特にTreeMap の実装では赤黒ツリーの仕組みが使用されますが、わかりやすくするために、より単純化したコードを使用します。すべては、空のノードを表す Node 型のプライベート静的フィールド EMPTY を初期化することから始まります。EMPTY の子孫も EMPTY です。すべてのシート (最初の図では NIL として表されている) は挿入時にこのフィールドによって初期化されるため、要素を挿入するときに便利です。

public class RedBlackTree {
    private static final Node EMPTY = new Node(0);

    static {
        EMPTY.left = EMPTY;
        EMPTY.right = EMPTY;
    }

クラス構造には、現在のノード current 、現在のノードparentの親、現在のノードgrandの祖父、現在のノードgreatの曽祖父、およびツリーheaderのルートへのポインタへの参照が含まれています。

protected Node current;
   private Node parent;
   private Node grand;
   private Node great;
   private Node header;

   public RedBlackTree() {
       header = new Node(Integer.MIN_VALUE);
       header.left = EMPTY;
       header.right = EMPTY;
   }

作成時にヘッダーは最小値 Integer.MIN_VALUE に初期化されるため、要素は常にその値より大きくなり、その子は常に空の EMPTY 要素になります。すべての要素は常にヘッダーよりも大きいため、最初の挿入は常にヘッダーの右側に行われます。したがって、 header の右の子は常にツリーのルートを指すため、header.right == EMPTYの場合、ツリーは空になります。実際、最も興味深いのは要素の挿入です。要素を KCHD に挿入する方法は次のとおりです。 1. ノードを挿入し、赤色に色付けします。2. 挿入によって CCH のプロパティが違反された場合は、親、叔父、または祖父を再ペイントし、ノードを回転してツリーのバランスをとった状態に戻します。 要素を挿入するときに発生する可能性のある主なシナリオは 4 つあります。便宜上、この挿入された要素を Z と呼びます。 1. Z = ルート (挿入される要素はツリーのルート) 2. Z.uncle = red (叔父)挿入される要素の色は赤です) 3. Z .uncle = 黒 (線)。挿入した要素のおじさんが黒くなっており、要素を挿入した後に木のバランスがLLやRRの形で崩れてしまいました。4. Z.uncle = 黒（三角形）。挿入した要素のおじさんが黒くなっており、要素を挿入した後にツリーがRLまたはLRの形でアンバランスになってしまいました。視覚的には次のようになります。 考えられる 4 つのケースそれぞれについて状況を修正する方法を詳しく見てみましょう。 事例１．根元だけ黒く塗ります ケースその2おじいちゃんを赤、おじさんを黒に塗ります。ノードの祖父がルートである場合、祖父の色は再び黒で塗られます。 事例その３。タイプNo.1に従って回転を実行します。つまり、おじいさんの結び目を引き下げます。「A」が「B」の代わりになり、「元の」祖父ノードを赤、親ノードを黒に再色付けします。 事例その４。いくつかの段階から構成されているため、最も難しいです。まず、タイプ 2 に従って回転を実行します。これにより、ケース 3 で説明した状態になります。つまり、回転を実行しましたが、ツリーはまだアンバランスな状態にあります。ノード「Z」（ノード「A」）は赤色です。つまり、ノード「A」は CCH のプロパティに違反し、ローテーションはその親ノード (祖父 - ノード「B」、親 - ノード「Z」) に対して実行されます。再度回転を実行し、「元の」祖父を赤、親を黒に再ペイントします。 コードに戻りましょう。insert() メソッド

public void insert(int item) {
//        Сохраняем ссылку на header в current, parent и grand
        current = parent = grand = header;
//        Инициализируем все пустые элементы дерева (листы NIL) числом, которое мы хотим вставить
        EMPTY.element = item;
//        Итерируемся в цикле до тех пор, пока meaning текущего element не станет равно добавляемому (item)
        while (current.element != item) {
//        Изменяем значения 4 ссылок в цикле для итерации в глубину дерева
//        (прадеда на деда, деда на отца, отца на текущий узел)
            great = grand;
            grand = parent;
            parent = current;
//        текущий узел на его правого or левого сына в зависимости от того,
//        больше ли текущий элемент добавляемого or меньше,
//        то есть идем в левое поддерево, если меньше, or в правое, если больше
            current = item > current.element ? current.right : current.left;
//          На каждой итерации проверяем левый сын текущего element и правый сын текущего element красные
            if (current.left.color == Color.RED && current.right.color == Color.RED) {
//           Если да, то вызываем метод для исправления и переориентации дерева относительно текущего element
//           Который записан в current на текущей итерации
                reorient(item);
            }
        }
/*  При выходе из цикла проверяем, является ли current узел пустым листом.
    Если meaning добавляемого числа оказалось равно текущему узлу,
    но при этом мы не дошли до листа (current != Empty),
    значит в дереве уже существует узел с добавляемым meaningм и мы просто выходим из метода.
    Cобственно поэтому при каждом входе в метод, мы перезаписываем ссылки на корневой узел.*/
        if (current != EMPTY) {
            return;
        }
//      Если мы все же дошли до пустого листа, создаем новый узел и инициализируем его потомков пустыми листами
        current = new Node(item, EMPTY, EMPTY);
//      Проверяем, Howим сыном будет являться текущий узел, левым or правым
        if (item < parent.element) {
            parent.left = current;
        } else {
            parent.right = current;
        }
//      красим текущий узел в красный, его листы в чёрный, а также осуществляем перебалансировку
//      в случаях, если parent оказался красным
        reorient(item);
    }

最も難しい部分はreorient()メソッドで発生します。このメソッドは、ノードの色付けと回転の実行を処理します。このメソッドは、本体内で -> rotate(int item, Nodeparent)メソッドを参照し、次に、rotateWithLeftNode(Node 要素)またはrotateWithRightNode(Node 要素)を呼び出します。メソッドは、追加された要素の値が祖父の左または右の子、つまり現在の要素の親の値より小さいか大きいかによって決まります。メソッドコード:

protected void reorient(int item) {
//      Первоначально красим текущий узел, до которого мы дошли в методе insert в красный, а его потомков в черный
        current.color = Color.RED;
        current.left.color = Color.BLACK;
        current.right.color = Color.BLACK;
//      Если цвет родителя current оказывается красным, то нам необходимо провести ротацию узлов
        if (parent.color == Color.RED) {
//          красим дедушку в красный
            grand.color = Color.RED;
//          Если текущий элемент левее родителя, но правее деда or наоборот, то вызываем ротацию для родителя.
//          То есть фактически определяем, Howого вида балансировку применить первого or второго
            if (item < grand.element != item < parent.element) {
//          Если второго, то сначала передаем дедушку текущего element и осуществляем поворот влево or вправо,
//          одновременно изменяя ссылку на parent, в результате родителем станет сам current
                parent = rotate(item, grand);
            }
//          Осуществляем ротацию первого вида. Поскольку в результате такого поворота дедушка станет потомком родителя
//          текущего element, то нам нужно перезаписать ссылку на нашего родителя у прадедушки, поэтому мы и передаем
//          ссылку именно на прадеда. Если прадеда в нашем маленьком дереве еще нет, то на него будет указывать HEAD

//          Если балансировка идет по первому виду, то current'ом станет родитель текущего current
//          Если по второму, то current'ом будет сам вставляемый элемент, на него же будет храниться link в parent
            current = rotate(item, great);
//          красим текущий узел в чёрный
            current.color = Color.BLACK;
        }
//      красим корень в черный, если в результате ротаций, например, How в сценарии № 2 дедушкой оказался корень
//      который мы ранее покрасor в красный
        header.right.color = Color.BLACK;
    }

rotate(int item, Nodeparent) メソッドは、親パラメーターとして渡されたものに応じて、2 番目のタイプのバランス調整の場合のように Great か、最初のタイプのバランス調整の場合のようにGrandに応じて異なる方法で実行されます。メソッドコード:

private Node rotate(int item, Node parent) {
        // Проверяем в Howом поддереве относительно grand/great узла находится текущий элемент
//        Если меньше, значит, гарантированно в левом, если больше - в правом
        if (item < parent.element) {
//          Получаем ссылку на родителя левого поддерева
            Node node = parent.left;
//          Проверяем Howим образом выполнить ротацию - справа
//          если вставляемый элемент больше, чем элемент родителя,
//          or слева, если вставляемый элемент меньше
            Node resultNode = item < node.element ? rotateWithLeftNode(node) : rotateWithRightNode(node);
//          присваиеваем переданному дедушке or прадедушке ссылку на узел, который стал новым родителем
            parent.left = resultNode;
            return parent.left;
        } else {
//           Получаем ссылку на родителя правого поддерева
            Node node = parent.right;
//           Проделываем аналогичные действия, но для правого поддерева
            Node resultNode = item < node.element ? rotateWithLeftNode(node) : rotateWithRightNode(node);
            parent.right = resultNode;
            return parent.right;
        }
    }

rotateWithLeftNode(Node 要素)メソッドとrotateWithRightNode(Node 要素) メソッドは、次のアクションを実行します。

private Node rotateWithLeftNode(Node element) {
//      Передаваемым элементом может быть либо родитель current узла, либо его дедушка
//      Получаем ссылку на левого потомка передаваемого в параметр element.
        Node left = element.left;
//      Назначаем нового левого потомка текущему элементу.
//      Новым потомком становится правый потомок левого потомка
        element.left = left.right;
//      Правый потомок левого потомка теперь ссылается на передаваемый в параметр элемент (дедушку or прадедушку)
//      то есть дедушка or прадедушка становится его правым потомком
        left.right = element;
//      возвращаем левый потомок передаваемого узла
        return left;
    }

private Node rotateWithRightNode(Node element) {
//      Получаем ссылку на правого потомка передаваемого в параметр element.
//      Действия аналогичны
        Node right = element.right;
        element.right = right.left;
        right.left = element;
        return right;
    }

それらを明確に見てみましょう。最初のタイプでは、条件(item < grand.element != item <parent.element)を入力しない 場合、回転は次のようになります。 2 番目のタイプでは、grand (grandfather) パラメータをパラメータを使用すると、回転は次のようになります。 親ノードが上書きされ、現在の を指すようになっていることに注意してください。回転が完了した後も木のバランスが取れていないため、前の図と同様に、最初のタイプに従って回転を再度実行します。 「なぜ、rotateWithLeftNodeメソッドが呼び出されたときは実際にノードを右に回転させ、rotateWithRightNodeメソッドが呼び出されたときは左に回転するのでしょうか?」という疑問が生じるかもしれません。これは、rotatWithLeftNode が、渡されたノードの左側の子、 rotateWithRightNode の右側の子に対するそれぞれの回転を暗黙的に意味するためです。回転方向はメソッド名では考慮されません。この単純な方法で、より複雑な場合でも回転が実行されます。 役立つ資料とリンク: 1. Wiki の記事 2. 赤黒ツリー ビジュアライザー 3. KChD に関する素晴らしい記事 4. KChD は本当にバランスが取れているかどうかについての疑問 5. JavaRush アカウントを持っていない KChD プログラム コード 6. による優れたビデオ非常に才能のある先生 (AVL について話しますが、原理は KChD に似ています) 7. デバイス、挿入、回転メカニズムに関する一連のビデオ 著者の連絡先: Telegram Mail: realyte95@gmail.com