Kırmızı-Siyah Ağaç

Bu eğitimde kırmızı-siyah ağacın ne olduğunu öğreneceksiniz. Ayrıca, C, C ++, Java ve Python'da kırmızı-siyah bir ağaç üzerinde gerçekleştirilen çeşitli işlemlerin çalışma örneklerini bulacaksınız.

Kırmızı-Siyah ağaç, her düğümün, düğümün rengini kırmızı veya siyah olarak belirtmek için fazladan bir bit içerdiği, kendi kendini dengeleyen bir ikili arama ağacıdır.

Kırmızı-siyah bir ağaç aşağıdaki özellikleri karşılar:

  1. Kırmızı / Siyah Özelliği: Her düğüm kırmızı veya siyah renklidir.
  2. Kök Özelliği: Kök siyahtır.
  3. Yaprak Özelliği: Her yaprak (NIL) siyahtır.
  4. Kırmızı Özellik: Kırmızı düğümün çocukları varsa, çocuklar her zaman siyahtır.
  5. Derinlik Özelliği: Her düğüm için, bu düğümden alt yaprağından herhangi birine giden herhangi bir basit yol aynı siyah derinliğe (siyah düğüm sayısı) sahiptir.

Kırmızı-siyah ağaçlara bir örnek:

Kırmızı Siyah Ağaç

Her düğüm aşağıdaki özniteliklere sahiptir:

  • renk
  • anahtar
  • leftChild
  • rightChild
  • ebeveyn (kök düğüm hariç)

Kırmızı-siyah ağaç kendi kendini dengeleme özelliğini nasıl korur?

Kırmızı-siyah renk, ağacı dengelemek içindir.

Düğüm renklerine getirilen sınırlamalar, kökten yaprağa giden herhangi bir basit yolun, bu tür diğer yolların iki katından daha uzun olmamasını sağlar. Kırmızı-siyah ağacın kendi kendini dengeleme özelliğini korumaya yardımcı olur.

Kırmızı-Siyah Ağaç Üzerinde İşlemler

Kırmızı-siyah bir ağaç üzerinde yapılabilecek çeşitli işlemler şunlardır:

Kırmızı-Siyah Ağaçta alt ağaçları döndürmek

Döndürme işleminde, bir alt ağacın düğümlerinin pozisyonları değiştirilir.

Döndürme işlemi, kırmızı-siyah bir ağacın özelliklerini, ekleme ve silme gibi diğer işlemlerle ihlal edildiğinde korumak için kullanılır.

İki tür rotasyon vardır:

Sola Döndür

Sola dönüşte sağdaki düğümlerin dizilişi, sol düğümdeki düzenlemelere dönüştürülür.

Algoritma

  1. İlk ağaç şöyle olsun: İlk ağaç
  2. Y'nin bir sol alt ağacı varsa, y'nin sol alt ağacının ebeveyni olarak x'i atayın. X'i y'nin sol alt ağacının ebeveyni olarak atayın
  3. Eğer x'in ebeveyni ise NULL, y'yi ağacın kökü olarak yapın.
  4. Aksi takdirde, x, p'nin sol çocuğu ise, y'yi p'nin sol çocuğu yapın.
  5. Aksi takdirde, y'yi p'nin doğru çocuğu olarak atayın. X'in ebeveynini y'nin ebeveyni olarak değiştirin
  6. Y'yi x'in ebeveyni yapın. Y'yi x'in ebeveyni olarak atayın.

Sağa Döndür

Sağa dönüşte, soldaki düğümlerin dizilişi, sağ düğümdeki düzenlemelere dönüştürülür.

  1. İlk ağaç şöyle olsun: İlk Ağaç
  2. Eğer x'in bir sağ alt ağacı varsa, y'yi x'in sağ alt ağacının ebeveyni olarak atayın. Y'yi x'in sağ alt ağacının ebeveyni olarak atayın
  3. Y'nin ebeveyni ise NULL, ağacın kökü olarak x yapın.
  4. Aksi takdirde, y ebeveyn p'nin doğru çocuğu ise, x'i p'nin doğru çocuğu yapın.
  5. Aksi takdirde, x'i p'nin sol çocuğu olarak atayın. Y'nin ebeveynini x'in ebeveyni olarak atayın
  6. X'i y'nin ebeveyni yapın. X'i y'nin ebeveyni olarak atayın

Sola-Sağa ve Sağa-Sola Döndür

Sol-sağ dönüşte, düzenlemeler önce sola sonra sağa kaydırılır.

  1. Xy'de sola dönüş yapın. Xy'yi sola döndür
  2. Yz'de sağa döndürme yapın. Sağa döndür zy

Sağa-sola dönüşte, düzenlemeler önce sağa sonra sola kaydırılır.

  1. Xy'de sağa döndürme yapın. Xy'yi sağa döndür
  2. Zy'de sola dönüş yapın. Sola döndürme zy

Kırmızı-Siyah Ağaca bir eleman eklemek

Yeni bir düğüm eklenirken, yeni düğüm her zaman KIRMIZI düğüm olarak eklenir. Yeni bir düğüm yerleştirildikten sonra, ağaç kırmızı-siyah ağacın özelliklerini ihlal ediyorsa, aşağıdaki işlemleri yaparız.

  1. Yeniden renklendir
  2. Rotasyon

Düğüm eklemek için algoritma

Kırmızı-siyah bir ağaca yeni bir eleman eklemek için aşağıdaki adımlar izlenir:

  1. Y yaprak (yani NIL) ve x ağacın kökü olsun.
  2. Ağacın boş olup olmadığını kontrol edin (yani x'in boş olup olmadığını NIL). Varsa, kök düğüm olarak newNode ekleyin ve siyaha boyayın.
  3. Aksi NILtakdirde, leaf ( ) 'ye ulaşılana kadar aşağıdaki adımları tekrarlayın .
    1. NewKey'i rootKey ile karşılaştırın.
    2. NewKey, rootKey'den büyükse, sağ alt ağaçtan geçin.
    3. Aksi takdirde sol alt ağaçtan geçiş yapın.
  4. Yaprağın ebeveynini newNode'un ebeveyni olarak atayın.
  5. LeafKey newKey'den büyükse, newNode'u rightChild olarak yapın.
  6. Aksi takdirde, newNode'u leftChild olarak yapın.
  7. Ata NULLsola ve newNode arasında rightChild.
  8. Yeni Düğüme KIRMIZI rengi atayın.
  9. İhlal edildiğinde kırmızı-siyah ağacın özelliğini korumak için InsertFix-algoritmasını çağırın.

Neden yeni eklenen düğümler kırmızı-siyah ağaçta her zaman kırmızıdır?

Bunun nedeni, kırmızı bir düğüm eklemenin kırmızı-siyah ağacın derinlik özelliğini ihlal etmemesidir.

Kırmızı düğüme kırmızı bir düğüm eklerseniz, kural ihlal edilir, ancak bu sorunu çözmek, derinlik özelliğini ihlal ederek ortaya çıkan sorundan daha kolaydır.

Eklemeden sonra kırmızı-siyah özelliğini korumak için algoritma

Bu algoritma, yeni bir Düğümün eklenmesi bu özelliği ihlal ederse kırmızı-siyah bir ağacın özelliğini korumak için kullanılır.

  1. NewNode p'nin ebeveyni KIRMIZI iken aşağıdakileri yapın.
  2. P, z'nin grandParent gP'sinin sol çocuğuysa, aşağıdakileri yapın.
    Durum-I:
    1. Z'nin sağ çocuğunun rengi KIRMIZI ise, hem gP'nin çocuklarının rengini SİYAH, hem de gP'nin rengini KIRMIZI olarak ayarlayın.
    2. GP'yi newNode'a atayın.
      Durum-II:
    3. Aksi takdirde newNode, p'nin sağ alt öğesi ise, p'yi newNode'a atayın.
    4. Yeni Düğümü Sola Döndür.
      Durum-III:
    5. P'nin rengini SİYAH ve gP'nin rengini KIRMIZI olarak ayarlayın.
    6. Sağa Döndürme gP.
  3. Aksi takdirde, aşağıdakileri yapın.
    1. GP'nin sol çocuğunun rengi KIRMIZI ise, hem gP'nin çocuklarının rengini SİYAH, hem de gP'nin rengini KIRMIZI olarak ayarlayın.
    2. GP'yi newNode'a atayın.
    3. Aksi takdirde newNode, p'nin sol alt öğesi ise, p'yi newNode'a ve Right-Rotate newNode'a atayın.
    4. P'nin rengini SİYAH ve gP'nin rengini KIRMIZI olarak ayarlayın.
    5. Sola Döndürme gP.
  4. Ağacın kökünü SİYAH olarak ayarlayın.

Kırmızı-Siyah Ağaçtan bir öğeyi silme

Bu işlem ağaçtan bir düğümü kaldırır. Bir düğümü sildikten sonra kırmızı-siyah özelliği yeniden korunur.

Bir düğümü silme algoritması

  1. NodeToBeDeleted'in rengini origrinalColor'a kaydedin.
  2. NodeToBeDeleted öğesinin sol alt öğesi NULL
    1. NodeToBeDeleted öğesinin doğru alt öğesini x'e atayın.
    2. Nakil nodeToBeDeleted, x.
  3. Aksi takdirde nodeToBeDeleted öğesinin doğru çocuğu NULL
    1. NodeToBeDeleted öğesinin sol alt öğesini x'e atayın.
    2. Nakil nodeToBeDeleted, x.
  4. Başka
    1. NoteToBeDeleted'in minimum sağ alt ağacını y'ye atayın.
    2. Y'nin rengini originalColor'da kaydedin.
    3. Y'nin rightChild'ini x'e atayın.
    4. Y, nodeToBeDeleted öğesinin bir alt öğesiyse, x'in ebeveynini y olarak ayarlayın.
    5. Aksi takdirde, rightChild of y ile nakli y.
    6. Nakil nodeToBeDeleted, y ile.
    7. OriginalColor ile y'nin rengini ayarlayın.
  5. Orijinal Renk SİYAH ise, DeleteFix (x) öğesini çağırın.

Silme işleminden sonra Kırmızı-Siyah özelliğini korumak için algoritma

Bu algoritma, kırmızı-siyah ağacın siyah derinlik özelliğini ihlal ettiği için siyah bir düğüm silindiğinde uygulanır.

Bu ihlal, x düğümünün (y'nin orijinal konumunu işgal eden) fazladan bir siyaha sahip olduğu varsayılarak düzeltilir. Bu, x düğümünü ne kırmızı ne de siyah yapar. Ya iki katı siyah ya da siyah-kırmızıdır. Bu, kırmızı-siyah özelliklerini ihlal ediyor.

Ancak, x'in renk özniteliği değişmez, bunun yerine fazladan siyah, x'in düğümü işaret ederek temsil edilir.

Ekstra siyah, eğer

  1. Kök düğüme ulaşır.
  2. Eğer x, kırmızı-siyah bir düğüme işaret ediyorsa. Bu durumda, x siyah renklidir.
  3. Uygun rotasyonlar ve yeniden renklendirme yapılır.

Aşağıdaki algoritma kırmızı-siyah bir ağacın özelliklerini korur.

  1. X, ağacın kökü olmayana ve x'in rengi SİYAH olana kadar aşağıdakileri yapın
  2. Eğer x, ebeveyninin sol çocuğuysa,
    1. W'yi x'in kardeşine atayın.
    2. X'in ebeveyninin doğru çocuğu RED ise,
      Durum-I:
      1. X'in ebeveyninin sağ çocuğunun rengini SİYAH olarak ayarlayın.
      2. X'in ebeveyninin rengini KIRMIZI olarak ayarlayın.
      3. X'in üst öğesini sola döndürün.
      4. X'in ebeveyninin rightChild'ini w'ye atayın.
    3. Hem sağ hem de sol çocuk w'nin rengi SİYAH ise,
      Durum-II:
      1. W'nin rengini KIRMIZI olarak ayarlayın
      2. X'in ebeveynini x'e atayın.
    4. Aksi takdirde, rightChild of w'nin rengi SİYAH
      Durum-III ise:
      1. LeftChild of w'nin rengini SİYAH olarak ayarlayın.
      2. W'nin rengini KIRMIZI olarak ayarlayın
      3. Sağa Döndür w.
      4. X'in ebeveyninin rightChild'ini w'ye atayın.
    5. Yukarıdaki durumlardan herhangi biri gerçekleşmezse, aşağıdakileri yapın.
      Durum-IV:
      1. W'nin rengini, x'in ebeveyninin rengi olarak ayarlayın.
      2. X'in ebeveyninin rengini SİYAH olarak ayarlayın.
      3. Doğru çocuğunun rengini SİYAH olarak ayarlayın.
      4. X'in üst öğesini sola döndürün.
      5. X'i ağacın kökü olarak ayarlayın.
  3. Yukarıdakinin aynısı, sağın sola dönüştüğü ve tam tersi.
  4. X'in rengini SİYAH olarak ayarlayın.

Örneklerle daha fazla açıklama için lütfen ekleme ve silme işlemlerine bakın.

Python, Java ve C / C ++ Örnekleri

Python Java C C ++ 
 # Implementing Red-Black Tree in Python import sys # Node creation class Node(): def __init__(self, item): self.item = item self.parent = None self.left = None self.right = None self.color = 1 class RedBlackTree(): def __init__(self): self.TNULL = Node(0) self.TNULL.color = 0 self.TNULL.left = None self.TNULL.right = None self.root = self.TNULL # Preorder def pre_order_helper(self, node): if node != TNULL: sys.stdout.write(node.item + " ") self.pre_order_helper(node.left) self.pre_order_helper(node.right) # Inorder def in_order_helper(self, node): if node != TNULL: self.in_order_helper(node.left) sys.stdout.write(node.item + " ") self.in_order_helper(node.right) # Postorder def post_order_helper(self, node): if node != TNULL: self.post_order_helper(node.left) self.post_order_helper(node.right) sys.stdout.write(node.item + " ") # Search the tree def search_tree_helper(self, node, key): if node == TNULL or key == node.item: return node if key < node.item: return self.search_tree_helper(node.left, key) return self.search_tree_helper(node.right, key) # Balancing the tree after deletion def delete_fix(self, x): while x != self.root and x.color == 0: if x == x.parent.left: s = x.parent.right if s.color == 1: s.color = 0 x.parent.color = 1 self.left_rotate(x.parent) s = x.parent.right if s.left.color == 0 and s.right.color == 0: s.color = 1 x = x.parent else: if s.right.color == 0: s.left.color = 0 s.color = 1 self.right_rotate(s) s = x.parent.right s.color = x.parent.color x.parent.color = 0 s.right.color = 0 self.left_rotate(x.parent) x = self.root else: s = x.parent.left if s.color == 1: s.color = 0 x.parent.color = 1 self.right_rotate(x.parent) s = x.parent.left if s.right.color == 0 and s.right.color == 0: s.color = 1 x = x.parent else: if s.left.color == 0: s.right.color = 0 s.color = 1 self.left_rotate(s) s = x.parent.left s.color = x.parent.color x.parent.color = 0 s.left.color = 0 self.right_rotate(x.parent) x = self.root x.color = 0 def __rb_transplant(self, u, v): if u.parent == None: self.root = v elif u == u.parent.left: u.parent.left = v else: u.parent.right = v v.parent = u.parent # Node deletion def delete_node_helper(self, node, key): z = self.TNULL while node != self.TNULL: if node.item == key: z = node if node.item <= key: node = node.right else: node = node.left if z == self.TNULL: print("Cannot find key in the tree") return y = z y_original_color = y.color if z.left == self.TNULL: x = z.right self.__rb_transplant(z, z.right) elif (z.right == self.TNULL): x = z.left self.__rb_transplant(z, z.left) else: y = self.minimum(z.right) y_original_color = y.color x = y.right if y.parent == z: x.parent = y else: self.__rb_transplant(y, y.right) y.right = z.right y.right.parent = y self.__rb_transplant(z, y) y.left = z.left y.left.parent = y y.color = z.color if y_original_color == 0: self.delete_fix(x) # Balance the tree after insertion def fix_insert(self, k): while k.parent.color == 1: if k.parent == k.parent.parent.right: u = k.parent.parent.left if u.color == 1: u.color = 0 k.parent.color = 0 k.parent.parent.color = 1 k = k.parent.parent else: if k == k.parent.left: k = k.parent self.right_rotate(k) k.parent.color = 0 k.parent.parent.color = 1 self.left_rotate(k.parent.parent) else: u = k.parent.parent.right if u.color == 1: u.color = 0 k.parent.color = 0 k.parent.parent.color = 1 k = k.parent.parent else: if k == k.parent.right: k = k.parent self.left_rotate(k) k.parent.color = 0 k.parent.parent.color = 1 self.right_rotate(k.parent.parent) if k == self.root: break self.root.color = 0 # Printing the tree def __print_helper(self, node, indent, last): if node != self.TNULL: sys.stdout.write(indent) if last: sys.stdout.write("R----") indent += " " else: sys.stdout.write("L----") indent += "| " s_color = "RED" if node.color == 1 else "BLACK" print(str(node.item) + "(" + s_color + ")") self.__print_helper(node.left, indent, False) self.__print_helper(node.right, indent, True) def preorder(self): self.pre_order_helper(self.root) def inorder(self): self.in_order_helper(self.root) def postorder(self): self.post_order_helper(self.root) def searchTree(self, k): return self.search_tree_helper(self.root, k) def minimum(self, node): while node.left != self.TNULL: node = node.left return node def maximum(self, node): while node.right != self.TNULL: node = node.right return node def successor(self, x): if x.right != self.TNULL: return self.minimum(x.right) y = x.parent while y != self.TNULL and x == y.right: x = y y = y.parent return y def predecessor(self, x): if (x.left != self.TNULL): return self.maximum(x.left) y = x.parent while y != self.TNULL and x == y.left: x = y y = y.parent return y def left_rotate(self, x): y = x.right x.right = y.left if y.left != self.TNULL: y.left.parent = x y.parent = x.parent if x.parent == None: self.root = y elif x == x.parent.left: x.parent.left = y else: x.parent.right = y y.left = x x.parent = y def right_rotate(self, x): y = x.left x.left = y.right if y.right != self.TNULL: y.right.parent = x y.parent = x.parent if x.parent == None: self.root = y elif x == x.parent.right: x.parent.right = y else: x.parent.left = y y.right = x x.parent = y def insert(self, key): node = Node(key) node.parent = None node.item = key node.left = self.TNULL node.right = self.TNULL node.color = 1 y = None x = self.root while x != self.TNULL: y = x if node.item < x.item: x = x.left else: x = x.right node.parent = y if y == None: self.root = node elif node.item < y.item: y.left = node else: y.right = node if node.parent == None: node.color = 0 return if node.parent.parent == None: return self.fix_insert(node) def get_root(self): return self.root def delete_node(self, item): self.delete_node_helper(self.root, item) def print_tree(self): self.__print_helper(self.root, "", True) if __name__ == "__main__": bst = RedBlackTree() bst.insert(55) bst.insert(40) bst.insert(65) bst.insert(60) bst.insert(75) bst.insert(57) bst.print_tree() print("After deleting an element") bst.delete_node(40) bst.print_tree() 
 // Implementing Red-Black Tree in Java class Node ( int data; Node parent; Node left; Node right; int color; ) public class RedBlackTree ( private Node root; private Node TNULL; // Preorder private void preOrderHelper(Node node) ( if (node != TNULL) ( System.out.print(node.data + " "); preOrderHelper(node.left); preOrderHelper(node.right); ) ) // Inorder private void inOrderHelper(Node node) ( if (node != TNULL) ( inOrderHelper(node.left); System.out.print(node.data + " "); inOrderHelper(node.right); ) ) // Post order private void postOrderHelper(Node node) ( if (node != TNULL) ( postOrderHelper(node.left); postOrderHelper(node.right); System.out.print(node.data + " "); ) ) // Search the tree private Node searchTreeHelper(Node node, int key) ( if (node == TNULL || key == node.data) ( return node; ) if (key < node.data) ( return searchTreeHelper(node.left, key); ) return searchTreeHelper(node.right, key); ) // Balance the tree after deletion of a node private void fixDelete(Node x) ( Node s; while (x != root && x.color == 0) ( if (x == x.parent.left) ( s = x.parent.right; if (s.color == 1) ( s.color = 0; x.parent.color = 1; leftRotate(x.parent); s = x.parent.right; ) if (s.left.color == 0 && s.right.color == 0) ( s.color = 1; x = x.parent; ) else ( if (s.right.color == 0) ( s.left.color = 0; s.color = 1; rightRotate(s); s = x.parent.right; ) s.color = x.parent.color; x.parent.color = 0; s.right.color = 0; leftRotate(x.parent); x = root; ) ) else ( s = x.parent.left; if (s.color == 1) ( s.color = 0; x.parent.color = 1; rightRotate(x.parent); s = x.parent.left; ) if (s.right.color == 0 && s.right.color == 0) ( s.color = 1; x = x.parent; ) else ( if (s.left.color == 0) ( s.right.color = 0; s.color = 1; leftRotate(s); s = x.parent.left; ) s.color = x.parent.color; x.parent.color = 0; s.left.color = 0; rightRotate(x.parent); x = root; ) ) ) x.color = 0; ) private void rbTransplant(Node u, Node v) ( if (u.parent == null) ( root = v; ) else if (u == u.parent.left) ( u.parent.left = v; ) else ( u.parent.right = v; ) v.parent = u.parent; ) private void deleteNodeHelper(Node node, int key) ( Node z = TNULL; Node x, y; while (node != TNULL) ( if (node.data == key) ( z = node; ) if (node.data <= key) ( node = node.right; ) else ( node = node.left; ) ) if (z == TNULL) ( System.out.println("Couldn't find key in the tree"); return; ) y = z; int yOriginalColor = y.color; if (z.left == TNULL) ( x = z.right; rbTransplant(z, z.right); ) else if (z.right == TNULL) ( x = z.left; rbTransplant(z, z.left); ) else ( y = minimum(z.right); yOriginalColor = y.color; x = y.right; if (y.parent == z) ( x.parent = y; ) else ( rbTransplant(y, y.right); y.right = z.right; y.right.parent = y; ) rbTransplant(z, y); y.left = z.left; y.left.parent = y; y.color = z.color; ) if (yOriginalColor == 0) ( fixDelete(x); ) ) // Balance the node after insertion private void fixInsert(Node k) ( Node u; while (k.parent.color == 1) ( if (k.parent == k.parent.parent.right) ( u = k.parent.parent.left; if (u.color == 1) ( u.color = 0; k.parent.color = 0; k.parent.parent.color = 1; k = k.parent.parent; ) else ( if (k == k.parent.left) ( k = k.parent; rightRotate(k); ) k.parent.color = 0; k.parent.parent.color = 1; leftRotate(k.parent.parent); ) ) else ( u = k.parent.parent.right; if (u.color == 1) ( u.color = 0; k.parent.color = 0; k.parent.parent.color = 1; k = k.parent.parent; ) else ( if (k == k.parent.right) ( k = k.parent; leftRotate(k); ) k.parent.color = 0; k.parent.parent.color = 1; rightRotate(k.parent.parent); ) ) if (k == root) ( break; ) ) root.color = 0; ) private void printHelper(Node root, String indent, boolean last) ( if (root != TNULL) ( System.out.print(indent); if (last) ( System.out.print("R----"); indent += " "; ) else ( System.out.print("L----"); indent += "| "; ) String sColor = root.color == 1 ? "RED" : "BLACK"; System.out.println(root.data + "(" + sColor + ")"); printHelper(root.left, indent, false); printHelper(root.right, indent, true); ) ) public RedBlackTree() ( TNULL = new Node(); TNULL.color = 0; TNULL.left = null; TNULL.right = null; root = TNULL; ) public void preorder() ( preOrderHelper(this.root); ) public void inorder() ( inOrderHelper(this.root); ) public void postorder() ( postOrderHelper(this.root); ) public Node searchTree(int k) ( return searchTreeHelper(this.root, k); ) public Node minimum(Node node) ( while (node.left != TNULL) ( node = node.left; ) return node; ) public Node maximum(Node node) ( while (node.right != TNULL) ( node = node.right; ) return node; ) public Node successor(Node x) ( if (x.right != TNULL) ( return minimum(x.right); ) Node y = x.parent; while (y != TNULL && x == y.right) ( x = y; y = y.parent; ) return y; ) public Node predecessor(Node x) ( if (x.left != TNULL) ( return maximum(x.left); ) Node y = x.parent; while (y != TNULL && x == y.left) ( x = y; y = y.parent; ) return y; ) public void leftRotate(Node x) ( Node y = x.right; x.right = y.left; if (y.left != TNULL) ( y.left.parent = x; ) y.parent = x.parent; if (x.parent == null) ( this.root = y; ) else if (x == x.parent.left) ( x.parent.left = y; ) else ( x.parent.right = y; ) y.left = x; x.parent = y; ) public void rightRotate(Node x) ( Node y = x.left; x.left = y.right; if (y.right != TNULL) ( y.right.parent = x; ) y.parent = x.parent; if (x.parent == null) ( this.root = y; ) else if (x == x.parent.right) ( x.parent.right = y; ) else ( x.parent.left = y; ) y.right = x; x.parent = y; ) public void insert(int key) ( Node node = new Node(); node.parent = null; node.data = key; node.left = TNULL; node.right = TNULL; node.color = 1; Node y = null; Node x = this.root; while (x != TNULL) ( y = x; if (node.data < x.data) ( x = x.left; ) else ( x = x.right; ) ) node.parent = y; if (y == null) ( root = node; ) else if (node.data < y.data) ( y.left = node; ) else ( y.right = node; ) if (node.parent == null) ( node.color = 0; return; ) if (node.parent.parent == null) ( return; ) fixInsert(node); ) public Node getRoot() ( return this.root; ) public void deleteNode(int data) ( deleteNodeHelper(this.root, data); ) public void printTree() ( printHelper(this.root, "", true); ) public static void main(String() args) ( RedBlackTree bst = new RedBlackTree(); bst.insert(55); bst.insert(40); bst.insert(65); bst.insert(60); bst.insert(75); bst.insert(57); bst.printTree(); System.out.println("After deleting:"); bst.deleteNode(40); bst.printTree(); ) )
 // Implementing Red-Black Tree in C #include #include enum nodeColor ( RED, BLACK ); struct rbNode ( int data, color; struct rbNode *link(2); ); struct rbNode *root = NULL; // Create a red-black tree struct rbNode *createNode(int data) ( struct rbNode *newnode; newnode = (struct rbNode *)malloc(sizeof(struct rbNode)); newnode->data = data; newnode->color = RED; newnode->link(0) = newnode->link(1) = NULL; return newnode; ) // Insert an node void insertion(int data) ( struct rbNode *stack(98), *ptr, *newnode, *xPtr, *yPtr; int dir(98), ht = 0, index; ptr = root; if (!root) ( root = createNode(data); return; ) stack(ht) = root; dir(ht++) = 0; while (ptr != NULL) ( if (ptr->data == data) ( printf("Duplicates Not Allowed!!"); return; ) index = (data - ptr->data)> 0 ? 1 : 0; stack(ht) = ptr; ptr = ptr->link(index); dir(ht++) = index; ) stack(ht - 1)->link(index) = newnode = createNode(data); while ((ht>= 3) && (stack(ht - 1)->color == RED)) ( if (dir(ht - 2) == 0) ( yPtr = stack(ht - 2)->link(1); if (yPtr != NULL && yPtr->color == RED) ( stack(ht - 2)->color = RED; stack(ht - 1)->color = yPtr->color = BLACK; ht = ht - 2; ) else ( if (dir(ht - 1) == 0) ( yPtr = stack(ht - 1); ) else ( xPtr = stack(ht - 1); yPtr = xPtr->link(1); xPtr->link(1) = yPtr->link(0); yPtr->link(0) = xPtr; stack(ht - 2)->link(0) = yPtr; ) xPtr = stack(ht - 2); xPtr->color = RED; yPtr->color = BLACK; xPtr->link(0) = yPtr->link(1); yPtr->link(1) = xPtr; if (xPtr == root) ( root = yPtr; ) else ( stack(ht - 3)->link(dir(ht - 3)) = yPtr; ) break; ) ) else ( yPtr = stack(ht - 2)->link(0); if ((yPtr != NULL) && (yPtr->color == RED)) ( stack(ht - 2)->color = RED; stack(ht - 1)->color = yPtr->color = BLACK; ht = ht - 2; ) else ( if (dir(ht - 1) == 1) ( yPtr = stack(ht - 1); ) else ( xPtr = stack(ht - 1); yPtr = xPtr->link(0); xPtr->link(0) = yPtr->link(1); yPtr->link(1) = xPtr; stack(ht - 2)->link(1) = yPtr; ) xPtr = stack(ht - 2); yPtr->color = BLACK; xPtr->color = RED; xPtr->link(1) = yPtr->link(0); yPtr->link(0) = xPtr; if (xPtr == root) ( root = yPtr; ) else ( stack(ht - 3)->link(dir(ht - 3)) = yPtr; ) break; ) ) ) root->color = BLACK; ) // Delete a node void deletion(int data) ( struct rbNode *stack(98), *ptr, *xPtr, *yPtr; struct rbNode *pPtr, *qPtr, *rPtr; int dir(98), ht = 0, diff, i; enum nodeColor color; if (!root) ( printf("Tree not available"); return; ) ptr = root; while (ptr != NULL) ( if ((data - ptr->data) == 0) break; diff = (data - ptr->data)> 0 ? 1 : 0; stack(ht) = ptr; dir(ht++) = diff; ptr = ptr->link(diff); ) if (ptr->link(1) == NULL) ( if ((ptr == root) && (ptr->link(0) == NULL)) ( free(ptr); root = NULL; ) else if (ptr == root) ( root = ptr->link(0); free(ptr); ) else ( stack(ht - 1)->link(dir(ht - 1)) = ptr->link(0); ) ) else ( xPtr = ptr->link(1); if (xPtr->link(0) == NULL) ( xPtr->link(0) = ptr->link(0); color = xPtr->color; xPtr->color = ptr->color; ptr->color = color; if (ptr == root) ( root = xPtr; ) else ( stack(ht - 1)->link(dir(ht - 1)) = xPtr; ) dir(ht) = 1; stack(ht++) = xPtr; ) else ( i = ht++; while (1) ( dir(ht) = 0; stack(ht++) = xPtr; yPtr = xPtr->link(0); if (!yPtr->link(0)) break; xPtr = yPtr; ) dir(i) = 1; stack(i) = yPtr; if (i> 0) stack(i - 1)->link(dir(i - 1)) = yPtr; yPtr->link(0) = ptr->link(0); xPtr->link(0) = yPtr->link(1); yPtr->link(1) = ptr->link(1); if (ptr == root) ( root = yPtr; ) color = yPtr->color; yPtr->color = ptr->color; ptr->color = color; ) ) if (ht color == BLACK) ( while (1) ( pPtr = stack(ht - 1)->link(dir(ht - 1)); if (pPtr && pPtr->color == RED) ( pPtr->color = BLACK; break; ) if (ht link(1); if (!rPtr) break; if (rPtr->color == RED) ( stack(ht - 1)->color = RED; rPtr->color = BLACK; stack(ht - 1)->link(1) = rPtr->link(0); rPtr->link(0) = stack(ht - 1); if (stack(ht - 1) == root) ( root = rPtr; ) else ( stack(ht - 2)->link(dir(ht - 2)) = rPtr; ) dir(ht) = 0; stack(ht) = stack(ht - 1); stack(ht - 1) = rPtr; ht++; rPtr = stack(ht - 1)->link(1); ) if ((!rPtr->link(0) || rPtr->link(0)->color == BLACK) && (!rPtr->link(1) || rPtr->link(1)->color == BLACK)) ( rPtr->color = RED; ) else ( if (!rPtr->link(1) || rPtr->link(1)->color == BLACK) ( qPtr = rPtr->link(0); rPtr->color = RED; qPtr->color = BLACK; rPtr->link(0) = qPtr->link(1); qPtr->link(1) = rPtr; rPtr = stack(ht - 1)->link(1) = qPtr; ) rPtr->color = stack(ht - 1)->color; stack(ht - 1)->color = BLACK; rPtr->link(1)->color = BLACK; stack(ht - 1)->link(1) = rPtr->link(0); rPtr->link(0) = stack(ht - 1); if (stack(ht - 1) == root) ( root = rPtr; ) else ( stack(ht - 2)->link(dir(ht - 2)) = rPtr; ) break; ) ) else ( rPtr = stack(ht - 1)->link(0); if (!rPtr) break; if (rPtr->color == RED) ( stack(ht - 1)->color = RED; rPtr->color = BLACK; stack(ht - 1)->link(0) = rPtr->link(1); rPtr->link(1) = stack(ht - 1); if (stack(ht - 1) == root) ( root = rPtr; ) else ( stack(ht - 2)->link(dir(ht - 2)) = rPtr; ) dir(ht) = 1; stack(ht) = stack(ht - 1); stack(ht - 1) = rPtr; ht++; rPtr = stack(ht - 1)->link(0); ) if ((!rPtr->link(0) || rPtr->link(0)->color == BLACK) && (!rPtr->link(1) || rPtr->link(1)->color == BLACK)) ( rPtr->color = RED; ) else ( if (!rPtr->link(0) || rPtr->link(0)->color == BLACK) ( qPtr = rPtr->link(1); rPtr->color = RED; qPtr->color = BLACK; rPtr->link(1) = qPtr->link(0); qPtr->link(0) = rPtr; rPtr = stack(ht - 1)->link(0) = qPtr; ) rPtr->color = stack(ht - 1)->color; stack(ht - 1)->color = BLACK; rPtr->link(0)->color = BLACK; stack(ht - 1)->link(0) = rPtr->link(1); rPtr->link(1) = stack(ht - 1); if (stack(ht - 1) == root) ( root = rPtr; ) else ( stack(ht - 2)->link(dir(ht - 2)) = rPtr; ) break; ) ) ht--; ) ) ) // Print the inorder traversal of the tree void inorderTraversal(struct rbNode *node) ( if (node) ( inorderTraversal(node->link(0)); printf("%d ", node->data); inorderTraversal(node->link(1)); ) return; ) // Driver code int main() ( int ch, data; while (1) ( printf("1. Insertion 2. Deletion"); printf("3. Traverse 4. Exit"); printf("Enter your choice:"); scanf("%d", &ch); switch (ch) ( case 1: printf("Enter the element to insert:"); scanf("%d", &data); insertion(data); break; case 2: printf("Enter the element to delete:"); scanf("%d", &data); deletion(data); break; case 3: inorderTraversal(root); printf(""); break; case 4: exit(0); default: printf("Not available"); break; ) printf(""); ) return 0; )
 // Implementing Red-Black Tree in C++ #include using namespace std; struct Node ( int data; Node *parent; Node *left; Node *right; int color; ); typedef Node *NodePtr; class RedBlackTree ( private: NodePtr root; NodePtr TNULL; void initializeNULLNode(NodePtr node, NodePtr parent) ( node->data = 0; node->parent = parent; node->left = nullptr; node->right = nullptr; node->color = 0; ) // Preorder void preOrderHelper(NodePtr node) ( if (node != TNULL) ( cout right); ) ) // Inorder void inOrderHelper(NodePtr node) ( if (node != TNULL) ( inOrderHelper(node->left); cout left); postOrderHelper(node->right); cout left, key); ) return searchTreeHelper(node->right, key); ) // For balancing the tree after deletion void deleteFix(NodePtr x) ( NodePtr s; while (x != root && x->color == 0) ( if (x == x->parent->left) ( s = x->parent->right; if (s->color == 1) ( s->color = 0; x->parent->color = 1; leftRotate(x->parent); s = x->parent->right; ) if (s->left->color == 0 && s->right->color == 0) ( s->color = 1; x = x->parent; ) else ( if (s->right->color == 0) ( s->left->color = 0; s->color = 1; rightRotate(s); s = x->parent->right; ) s->color = x->parent->color; x->parent->color = 0; s->right->color = 0; leftRotate(x->parent); x = root; ) ) else ( s = x->parent->left; if (s->color == 1) ( s->color = 0; x->parent->color = 1; rightRotate(x->parent); s = x->parent->left; ) if (s->right->color == 0 && s->right->color == 0) ( s->color = 1; x = x->parent; ) else ( if (s->left->color == 0) ( s->right->color = 0; s->color = 1; leftRotate(s); s = x->parent->left; ) s->color = x->parent->color; x->parent->color = 0; s->left->color = 0; rightRotate(x->parent); x = root; ) ) ) x->color = 0; ) void rbTransplant(NodePtr u, NodePtr v) ( if (u->parent == nullptr) ( root = v; ) else if (u == u->parent->left) ( u->parent->left = v; ) else ( u->parent->right = v; ) v->parent = u->parent; ) void deleteNodeHelper(NodePtr node, int key) ( NodePtr z = TNULL; NodePtr x, y; while (node != TNULL) ( if (node->data == key) ( z = node; ) if (node->data right; ) else ( node = node->left; ) ) if (z == TNULL) ( cout << "Key not found in the tree"  left == TNULL) ( x = z->right; rbTransplant(z, z->right); ) else if (z->right == TNULL) ( x = z->left; rbTransplant(z, z->left); ) else ( y = minimum(z->right); y_original_color = y->color; x = y->right; if (y->parent == z) ( x->parent = y; ) else ( rbTransplant(y, y->right); y->right = z->right; y->right->parent = y; ) rbTransplant(z, y); y->left = z->left; y->left->parent = y; y->color = z->color; ) delete z; if (y_original_color == 0) ( deleteFix(x); ) ) // For balancing the tree after insertion void insertFix(NodePtr k) ( NodePtr u; while (k->parent->color == 1) ( if (k->parent == k->parent->parent->right) ( u = k->parent->parent->left; if (u->color == 1) ( u->color = 0; k->parent->color = 0; k->parent->parent->color = 1; k = k->parent->parent; ) else ( if (k == k->parent->left) ( k = k->parent; rightRotate(k); ) k->parent->color = 0; k->parent->parent->color = 1; leftRotate(k->parent->parent); ) ) else ( u = k->parent->parent->right; if (u->color == 1) ( u->color = 0; k->parent->color = 0; k->parent->parent->color = 1; k = k->parent->parent; ) else ( if (k == k->parent->right) ( k = k->parent; leftRotate(k); ) k->parent->color = 0; k->parent->parent->color = 1; rightRotate(k->parent->parent); ) ) if (k == root) ( break; ) ) root->color = 0; ) void printHelper(NodePtr root, string indent, bool last) ( if (root != TNULL) ( cout << indent; if (last) ( cout << "R----"; indent += " "; ) else ( cout  right, indent, true); ) ) public: RedBlackTree() ( TNULL = new Node; TNULL->color = 0; TNULL->left = nullptr; TNULL->right = nullptr; root = TNULL; ) void preorder() ( preOrderHelper(this->root); ) void inorder() ( inOrderHelper(this->root); ) void postorder() ( postOrderHelper(this->root); ) NodePtr searchTree(int k) ( return searchTreeHelper(this->root, k); ) NodePtr minimum(NodePtr node) ( while (node->left != TNULL) ( node = node->left; ) return node; ) NodePtr maximum(NodePtr node) ( while (node->right != TNULL) ( node = node->right; ) return node; ) NodePtr successor(NodePtr x) ( if (x->right != TNULL) ( return minimum(x->right); ) NodePtr y = x->parent; while (y != TNULL && x == y->right) ( x = y; y = y->parent; ) return y; ) NodePtr predecessor(NodePtr x) ( if (x->left != TNULL) ( return maximum(x->left); ) NodePtr y = x->parent; while (y != TNULL && x == y->left) ( x = y; y = y->parent; ) return y; ) void leftRotate(NodePtr x) ( NodePtr y = x->right; x->right = y->left; if (y->left != TNULL) ( y->left->parent = x; ) y->parent = x->parent; if (x->parent == nullptr) ( this->root = y; ) else if (x == x->parent->left) ( x->parent->left = y; ) else ( x->parent->right = y; ) y->left = x; x->parent = y; ) void rightRotate(NodePtr x) ( NodePtr y = x->left; x->left = y->right; if (y->right != TNULL) ( y->right->parent = x; ) y->parent = x->parent; if (x->parent == nullptr) ( this->root = y; ) else if (x == x->parent->right) ( x->parent->right = y; ) else ( x->parent->left = y; ) y->right = x; x->parent = y; ) // Inserting a node void insert(int key) ( NodePtr node = new Node; node->parent = nullptr; node->data = key; node->left = TNULL; node->right = TNULL; node->color = 1; NodePtr y = nullptr; NodePtr x = this->root; while (x != TNULL) ( y = x; if (node->data data) ( x = x->left; ) else ( x = x->right; ) ) node->parent = y; if (y == nullptr) ( root = node; ) else if (node->data data) ( y->left = node; ) else ( y->right = node; ) if (node->parent == nullptr) ( node->color = 0; return; ) if (node->parent->parent == nullptr) ( return; ) insertFix(node); ) NodePtr getRoot() ( return this->root; ) void deleteNode(int data) ( deleteNodeHelper(this->root, data); ) void printTree() ( if (root) ( printHelper(this->root, "", true); ) ) ); int main() ( RedBlackTree bst; bst.insert(55); bst.insert(40); bst.insert(65); bst.insert(60); bst.insert(75); bst.insert(57); bst.printTree(); cout << endl << "After deleting" << endl; bst.deleteNode(40); bst.printTree(); )

Kırmızı-Siyah Ağaç Uygulamaları

  1. Sonlu haritaları uygulamak için
  2. Java paketlerini uygulamak için: java.util.TreeMapvejava.util.TreeSet
  3. Standart Şablon Kitaplıklarını (STL) C ++ 'da uygulamak için: multiset, map, multimap
  4. Linux Kernel'de

Ilginç makaleler...