Red-Black Ağacı

Düğümleri kırmızı ve siyaha boyayarak yüksekliği O(log n) tutan, TreeMap ve std::map'in kullandığı dengeli arama ağacı.

Önce bunlara göz at

#Nasıl çalışır?

Red-black ağacı, her düğümü kırmızı ya da siyah renkle işaretleyerek kendini dengeleyen bir ikili arama ağacıdır. Java'nın TreeMap'i, C++'ın std::map'i ve Linux çekirdeğinin zamanlayıcısı red-black ağacı kullanır.

Beş kural vardır: (1) her düğüm kırmızı ya da siyahtır, (2) kök siyahtır, (3) boş (null) yapraklar siyah sayılır, (4) kırmızı bir düğümün çocukları siyahtır, yani iki kırmızı art arda gelemez, (5) bir düğümden aşağıdaki tüm null yapraklara giden yollarda aynı sayıda siyah düğüm vardır.

Bu kurallar, en uzun yolun en kısa yolun iki katını geçmemesini sağlar; ağaç tam dengeli olmasa da yüksekliği O(log n) kalır.

Yeni düğüm hep kırmızı eklenir. Ebeveyni de kırmızıysa kural 4 bozulur ve amcanın rengine bakılır: amca kırmızıysa yeniden boyanır, siyahsa bir ya da iki rotasyon yapılır.

#Kendin dene

$ red_black-tree --interactive

Bir değer ekle: yeni düğüm kırmızı başlar. Kırmızı bir düğümün kırmızı çocuğu olamaz; bu kural yeniden boyama ve rotasyonlarla korunur.

Eleman: 6/12GeziliyorYeniÇıkarılıyorBulundu / okunan

#Temel işlemler

insert(x)
BST gibi kırmızı bir düğüm ekler; kırmızı-kırmızı çakışmasını yeniden boyama ve rotasyonlarla giderir, en sonda kökü siyaha boyar.
search(x)
Sıradan BST araması; renkler aramayı etkilemez.
delete(x)
BST gibi siler; siyah bir düğüm çıkarsa "çift siyah" durumunu kardeşin rengine göre rotasyon ve boyamalarla düzeltir. Eklemeden daha fazla durum içerir.
recolor
Amca kırmızıysa ebeveyn ve amca siyaha, dede kırmızıya boyanır; sorun yukarı taşınır.

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

from typing import Optional

RED, BLACK = "R", "B"


class Node:
    def __init__(self, value: int) -> None:
        self.value = value
        self.color = RED  # new nodes start red
        self.left: Optional["Node"] = None
        self.right: Optional["Node"] = None
        self.parent: Optional["Node"] = None


class RedBlackTree:
    def __init__(self) -> None:
        self.root: Optional[Node] = None

    def _rotate_left(self, x: Node) -> None:
        y = x.right
        x.right = y.left
        if y.left:
            y.left.parent = x
        self._replace(x, y)
        y.left = x
        x.parent = y

    def _rotate_right(self, x: Node) -> None:
        y = x.left
        x.left = y.right
        if y.right:
            y.right.parent = x
        self._replace(x, y)
        y.right = x
        x.parent = y

    def _replace(self, old: Node, new: Node) -> None:
        """Puts `new` where `old` hangs from its parent."""
        new.parent = old.parent
        if old.parent is None:
            self.root = new
        elif old is old.parent.left:
            old.parent.left = new
        else:
            old.parent.right = new

    def insert(self, value: int) -> None:
        # 1. Plain BST insert of a red node.
        node, parent, cur = Node(value), None, self.root
        while cur:
            parent = cur
            if value == cur.value:
                return
            cur = cur.left if value < cur.value else cur.right
        node.parent = parent
        if parent is None:
            self.root = node
        elif value < parent.value:
            parent.left = node
        else:
            parent.right = node
        # 2. Fix red-red conflicts.
        while node.parent and node.parent.color == RED:
            parent = node.parent
            grand = parent.parent
            parent_is_left = parent is grand.left
            uncle = grand.right if parent_is_left else grand.left
            if uncle and uncle.color == RED:  # recolour and move up
                parent.color = uncle.color = BLACK
                grand.color = RED
                node = grand
                continue
            if parent_is_left and node is parent.right:  # inner child: make it outer
                self._rotate_left(parent)
                node, parent = parent, node
            elif not parent_is_left and node is parent.left:
                self._rotate_right(parent)
                node, parent = parent, node
            parent.color, grand.color = BLACK, RED  # outer child: rotate grandparent
            if parent_is_left:
                self._rotate_right(grand)
            else:
                self._rotate_left(grand)
        self.root.color = BLACK


def preorder(node: Optional[Node], out: list) -> list:
    if node:
        out.append(f"{node.value}{node.color}")
        preorder(node.left, out)
        preorder(node.right, out)
    return out


tree = RedBlackTree()
for v in [10, 20, 30, 15, 25, 5]:
    tree.insert(v)
print(" ".join(preorder(tree.root, [])))  # value + colour, root first

#Karmaşıklık

İşlemSüre
searchO(log n)
insertO(log n), en fazla 2 rotasyon
deleteO(log n), en fazla 3 rotasyon
BellekO(n) + düğüm başına 1 bit renk

Siyah yükseklik kuralı sayesinde ağacın yüksekliği en fazla 2 · log2(n + 1) olur. Ekleme ve silme sabit sayıda rotasyon yapar; yeniden boyama yukarı doğru O(log n) kez tekrarlanabilir ama ucuzdur. AVL'den daha gevşek dengelidir: aramalar biraz daha uzun sürebilir, güncellemeler daha az rotasyon ister.

#Ne zaman kullanılır?

Ekleme ve silmenin sık olduğu sıralı yapılarda standart seçimdir: Java TreeMap/TreeSet, C++ std::map/std::set, Linux CFS zamanlayıcısı ve birçok veritabanının bellek içi indeksleri. Sadece arama ağırlıklı bir iş yükünde AVL biraz daha hızlı olabilir.

#Alıştırma

Soruları cevaplamak ve ilerlemeni kaydetmek için giriş yap.

Kolay

1/3

Red-black ağacında yeni eklenen düğüm hangi renkle başlar?

  • 1Kırmızı
  • 2Siyah
  • 3Ebeveyninin rengi
  • 4Rastgele

Orta

1/1

Yeni kırmızı düğümün ebeveyni ve amcası kırmızıysa ne yapılır?

  • 1Ebeveyn ve amca siyah, dede kırmızı yapılır
  • 2Dede etrafında rotasyon yapılır
  • 3Yeni düğüm siyah yapılır
  • 4Hiçbir şey; kural bozulmaz

Zor

1/1

Red-black ağacı AVL'ye göre neden ekleme/silmede genellikle daha hızlıdır?

  • 1Daha gevşek dengelidir, daha az rotasyon gerekir
  • 2Arama daha kısadır
  • 3Daha az bellek kullanır
  • 4Rotasyon hiç yapmaz