레드 블랙 트리. 속성, 구성 원리, 삽입 메커니즘.

레드 -블랙 트리 의 개념 레드-블랙 트리는 이진 트리의 한 유형 으로 , 주요 본질은 자체 균형 능력입니다. 자체 균형 트리에는 여러 가지 유형이 있지만 이 기사에서는 레드-블랙 트리(RCB)만 다루겠습니다. 균형은 트리 노드의 추가 속성인 "색상"을 도입하여 달성됩니다. 요소 외에도 각 트리 노드는 노드가 빨간색인지 검은색인지에 대한 1비트 정보를 저장하며 이는 색상뿐만 아니라 한 노드 유형을 다른 노드와 구별할 수 있는 기타 정보일 수도 있습니다. 예를 들어 1 또는 0, 참 또는 거짓 등입니다. KChD의 구성(속성) 원칙: 1. 트리의 루트는 검은색입니다 . 2. 데이터를 포함하지 않는 모든 잎은 검은색입니다 . 3. 각 빨간색 노드 의 두 자식은 모두 검은색 입니다. 4. 검은색 노드 의 깊이는 모든 하위 트리에서 동일합니다. 트리에서 수행되는 주요 작업은 다음과 같습니다. 1. 검색 2. 삽입 요소 3 요소 삭제(delete) 마지막 두 작업은 분명히 트리 구조의 변경으로 이어지므로 결과적으로 트리의 불균형이 발생할 수 있습니다. 시간과 공간의 복잡성. 시간 복잡도 QCD의 삽입, 삭제 및 검색 작업은 O(log n)입니다 . 여기서 n은 트리의 노드 수입니다. 이를 수행하려면 원하는 노드에 도달하고 각 하위 트리 중 하나를 버려야 하기 때문입니다. 단계. 삽입이나 삭제로 인해 CCH의 속성이 침해되는 경우에는 리밸런싱을 수행해야 합니다. 균형 조정은 O(1) 다시 칠하기와 O(1) 회전이라는 두 가지 작업으로 구성됩니다. 각 균형 조정 작업은 하위 요소와 상위 요소의 링크와 해당 색상에 대한 정보를 다시 작성하는 작업으로 구성되므로 일정한 시간이 걸립니다. 그러나 요소를 추가하거나 삭제할 때 가장 낮은 노드부터 루트까지 트리의 균형을 맞춰야 하는 상황이 발생할 수 있습니다. n개의 노드로 구성된 CCH의 최대 높이는 2log(n + 1) 이하가 보장되므로 최악의 경우 재조정에 log(n) - 작업이 필요할 수 있습니다. 삽입 시 메모리 비용 은 새 노드 생성만 포함되므로 O(1) 입니다. 균형 조정 및 다시 그리기 작업에는 추가 메모리가 필요하지 않습니다. 나무가 균형을 잃었는지 어떻게 알 수 있나요? KChD의 경우 앞서 설명한 모든 속성이 충족되면 균형 상태에 있습니다. 불균형 상태에는 4가지 유형이 있습니다. 1. 좌우 불균형(LL) 2. 좌우 불균형(RR) 3. 좌우 불균형(LR) 4. 좌우 불균형(RL) 처음 두 상태도 다음과 같습니다 . 선형 (Line ) 이라고 함, 시각적으로 한쪽으로 기울어진 직선 가지로 표현될 수 있기 때문입니다. 나머지 두 개를 삼각형 이라고 합니다 . CCH를 균형 상태로 만들려면 회전이라는 조작을 수행해야 합니다. 이 4가지 유형의 균형을 맞추기 위해 두 가지 유형의 회전이 사용됩니다. 1. LL 및 RR의 경우 2. LR 및 RL의 경우 첫 번째 유형은 가운데가 맨 위에 오도록 첫 번째 노드를 아래로 당기는 것입니다. 시각적으로 이는 노드가 실제로 못에 매달린 밧줄의 노드인 것처럼 나타낼 수 있습니다. 회전 자체는 다음과 같습니다. 복잡한 LL 회전의 경우 노드에도 자손이 있는 경우 원리는 동일하게 유지되지만 오른쪽 부모가 되는 노드의 자식은 당겨지는 노드의 왼쪽/오른쪽 자식이 됩니다 . 예: 두 번째 유형(LR,RL)은 2단계로 구성되며 먼저 트리를 첫 번째 상태로 가져온 다음 첫 번째 노드를 아래로 당기는 것으로 구성됩니다. 이 그림을 보면 단순히 이동하고 있음을 알 수 있습니다. 맨 아래 노드를 맨 위로 이동하여 "새" 할아버지를 만들고, "이전" 할아버지를 왼쪽 또는 오른쪽 자식으로 만듭니다. 예: 복잡한 LR/RL 회전의 경우 노드에도 자손이 있으면 원칙은 동일하게 유지되지만 "새" 상위의 이전 자손이 하위 노드의 자손 중 비어 있는 자리를 차지합니다. 예: 레드 -블랙 트리 의 프로그램 코드 이론에 대해 이야기했습니다. 이제 CNC 장치가 JAVA 프로그래밍 언어로 어떻게 구성되어 있는지 살펴보겠습니다. Red-Black 트리 메커니즘은 특히 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 의 증조부 , 트리 헤더 의 루트에 대한 포인터에 대한 참조가 포함되어 있습니다 .

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.삼촌 = 검정색(삼각형). 삽입된 요소의 삼촌은 검은색 이며 요소를 삽입한 후 트리는 RL 또는 LR 형태로 불균형이 되었습니다. 시각적으로 다음과 같습니다. 가능한 4가지 사례 각각에 대해 상황을 수정하는 방법을 더 자세히 살펴보겠습니다. 사건 번호 1 . 뿌리만 검은색으로 칠합니다 사례 2. 할아버지는 빨간색 , 삼촌은 검은색으로 칠합니다. 노드의 할아버지가 루트이면 할아버지의 색이 다시 검은색으로 칠해집니다. 사건 번호 3 . 1 번 유형에 따라 회전을 수행합니다. 즉, 할아버지의 매듭을 아래로 당깁니다. "A"는 "B"를 대신하고 "이전" 할아버지 노드는 빨간색 으로, 부모 노드는 검정색으로 다시 칠합니다 . 사건 번호 4 . 여러 단계로 구성되어 있어서 가장 어렵습니다. 먼저, 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, Node parent) 메서드를 참조하고 , 이어서 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, Node parent) 메소드는 상위 매개 변수 로 전달된 내용에 따라 다르게 실행됩니다 ( 두 번째 유형의 균형 조정에서처럼 훌륭하거나 첫 번째 유형의 균형 조정에서처럼 그랜드 ). 메소드 코드:

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(노드 요소) 및 RotateWithRightNode(노드 요소) 메서드는 다음 작업을 수행합니다.

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)을 입력하지 않으면 회전은 다음과 같습니다. 두 번째 유형의 경우 grand(할아버지) 매개변수를 매개변수를 사용하면 회전은 다음과 같이 표시됩니다. 상위 노드 가 덮어쓰기되어 이제 현재 를 가리 킵니다 . 회전이 완료된 후에도 여전히 나무의 균형이 맞지 않기 때문에 이전 그림과 같이 다시 첫 번째 유형에 따라 회전을 수행합니다 . 의문이 생길 수 있습니다: 왜 RotateWithLeftNode 메소드가 호출될 때 실제로 노드를 오른쪽으로 회전하고, RotateWithRightNode - 왼쪽으로 회전합니까? 이는 rotatWithLeftNode가 각각 전달된 노드인 rotateWithRightNode 의 왼쪽 자식과 오른쪽 노드의 회전을 의미하기 때문입니다. 메소드 이름에는 회전 방향이 고려되지 않습니다 . 이 간단한 방법으로 더 복잡한 경우에도 회전이 수행됩니다. 유용한 자료 및 링크: 1. Wiki 기사 2. Red-black tree 시각화 도우미 3. KChD에 대한 좋은 기사 4. KChD가 실제로 균형을 이루고 있는지에 대한 질문 5. JavaRush 계정이 없는 KChD 프로그램 코드 6. 작성자의 훌륭한 비디오 매우 재능 있는 교사(AVL에 대해 이야기하지만 원리는 KChD와 유사함) 7. 장치, 삽입 및 회전 메커니즘에 대한 일련의 비디오 작성자 연락처: Telegram Mail: realyte95@gmail.com