Raudonai-juodas medis

Šioje pamokoje sužinosite, kas yra raudonai juodas medis. Be to, rasite įvairių operacijų, atliktų raudonai juodam medžiui C, C ++, Java ir Python, pavyzdžius.

Raudonai-juodas medis yra savaime subalansuotas dvejetainis paieškos medis, kuriame kiekviename mazge yra papildomas bitas, žymintis mazgo spalvą - raudoną arba juodą.

Raudonai juodas medis atitinka šias savybes:

  1. Raudona / juoda ypatybė: kiekvienas mazgas yra raudonos arba juodos spalvos.
  2. Šaknies savybė: šaknis yra juoda.
  3. Lapo savybė: kiekvienas lapas (NIL) yra juodas.
  4. Raudona nuosavybė: jei raudonas mazgas turi vaikų, vaikai visada būna juodi.
  5. Gylio ypatybė: kiekvienam mazgui bet koks paprastas kelias nuo šio mazgo iki bet kurio jo palikuonio lapo turi tą patį juodo gylio (juodų mazgų skaičių).

Raudonai juodo medžio pavyzdys yra:

Raudonas juodas medis

Kiekvienas mazgas turi šiuos atributus:

  • spalva
  • Raktas
  • palikoVaikas
  • dešinėVaikas
  • pagrindinis (išskyrus šakninį mazgą)

Kaip raudonai juodas medis išlaiko savęs balansavimo savybę?

Raudona-juoda spalva skirta balansuoti medį.

Mazgo spalvų apribojimai užtikrina, kad bet koks paprastas kelias nuo šaknies iki lapo būtų ne daugiau kaip dvigubai ilgesnis nei bet kuris kitas toks kelias. Tai padeda išlaikyti savaime subalansuotą raudonai juodo medžio savybę.

Operacijos su raudonai juodu medžiu

Įvairios operacijos, kurias galima atlikti su raudonai juodu medžiu, yra šios:

Raudonų-juodų medžių posmių sukimas

Sukimosi operacijoje porūšio mazgų pozicijos yra keičiamos.

Sukimosi operacija naudojama raudonai juodo medžio savybėms palaikyti, kai jas pažeidžia kitos operacijos, pavyzdžiui, įterpimas ir pašalinimas.

Yra dviejų tipų pasukimai:

Pasukti kairėn

Sukant kairėje, mazgų išdėstymas dešinėje transformuojamas į kairio mazgo išdėstymus.

Algoritmas

  1. Tegu pradinis medis būna: Pradinis medis
  2. Jei y turi kairįjį pomedį, priskirkite x kaip y kairio potemio tėvą. Paskirkite x kaip kairiojo y potemio tėvą
  3. Jei x yra vienas iš tėvų NULL, padarykite y kaip medžio šaknį.
  4. Jei ne, x yra kairysis p vaikas, padarykite y kaip kairįjį p vaiką.
  5. Kitu atveju priskirkite y tinkamą vaiką p. Pakeiskite x tėvą į y
  6. Padarykite y kaip x tėvą. Priskirkite y kaip x tėvą.

Pasukti dešinėn

Sukant į dešinę, mazgų išdėstymas kairėje transformuojamas į dešiniojo mazgo išdėstymus.

  1. Tegu pradinis medis būna: Pradinis medis
  2. Jei x turi dešinį potentį, priskirkite y kaip dešiniojo x medžio tėvą. Priskirkite y kaip dešiniojo x potemio tėvą
  3. Jei y yra tėvas NULL, padarykite x kaip medžio šaknį.
  4. Kitu atveju, jei y yra tinkamas jo tėvų p vaikas, padarykite x kaip tinkamą p vaiką.
  5. Kitu atveju priskirkite x kaip kairįjį p. Paskirkite y tėvą kaip x tėvą
  6. Padarykite x kaip y tėvą. Paskirkite x kaip y tėvą

Pasukite kairę-dešinę ir dešinę-kairę

Sukant kairėn-dešinėn, išdėstymai pirmiausia perkeliami į kairę, tada į dešinę.

  1. Sukite kairę kairėje xy. Kairysis sukasi xy
  2. Darykite dešinę sukdami yz. Dešinėn pasukite zy

Sukant dešinėje ir kairėje, išdėstymai pirmiausia perkeliami į dešinę, o paskui į kairę.

  1. Darykite dešinę sukimosi kryptį xy. Pasukite dešinėn xy
  2. Sukite kairę zy. Kairysis sukasi zy

Elemento įterpimas į raudonai juodą medį

Įterpiant naują mazgą, naujas mazgas visada įterpiamas kaip RED mazgas. Įterpus naują mazgą, jei medis pažeidžia raudonai juodo medžio savybes, atliekame šias operacijas.

  1. Perdažyti
  2. Sukimas

Algoritmas įterpti mazgą

Atliekami šie veiksmai, norint įterpti naują elementą į raudonai juodą medį:

  1. Tegu y yra NILmedžio lapas (ty. ), O x - medžio šaknis.
  2. Patikrinkite, ar medis tuščias (ty ar x yra NIL). Jei taip, įterpkite „newNode“ kaip šakninį mazgą ir nuspalvinkite jį juodai.
  3. Kitu atveju pakartokite veiksmus, kol NILpasieksite lapą ( ).
    1. Palyginkite „newKey“ su „rootKey“.
    2. Jei „newKey“ yra didesnis nei „rootKey“, eikite per dešinį potemį.
    3. Kitos eina per kairįjį potemį.
  4. Priskirkite lapo tėvą kaip „newNode“ tėvą.
  5. Jei „leafKey“ yra didesnis nei „newKey“, „newNode“ padarykite kaip „rightChild“.
  6. Kitaip, padarykite newNode kaip leftChild.
  7. Priskirkite NULLkairę ir dešinę newNode vaiką.
  8. Priskirkite raudoną spalvą „newNode“.
  9. Norėdami pažeisti raudonai juodo medžio savybę, iškvieskite „InsertFix“ algoritmą.

Kodėl naujai įterpti mazgai raudonai juodame medyje visada yra raudoni?

Taip yra todėl, kad įterpus raudoną mazgą nepažeidžiama raudonai juodo medžio gylio savybė.

Jei prie raudono mazgo pritvirtinsite raudoną mazgą, taisyklė bus pažeista, tačiau šią problemą lengviau išspręsti nei problemą, įvestą pažeidus gylio ypatybę.

Algoritmas raudonai juodai savybei išlaikyti po įterpimo

Šis algoritmas naudojamas raudonai juodo medžio savybei išlaikyti, jei įterpus newNode pažeidžiama ši savybė.

  1. Atlikite šiuos veiksmus, kol „newNode p“ tėvas yra RAUDONAS.
  2. Jei p yra kairysis „grandParent gP“ z vaikas, atlikite šiuos veiksmus.
    I atvejis:
    1. Jei dešiniojo gP z vaiko vaikas yra RAUDONAS, nustatykite, kad abiejų vaikų gP spalva būtų juoda, o gP spalva - RED.
    2. Priskirkite gP „newNode“.
      II atvejis:
    3. Kitu atveju, jei „newNode“ yra tinkamas p vaikas, priskirkite p „newNode“.
    4. Kairėje pusėje pasukti newNode.
      III atvejis:
    5. Nustatykite p spalvą kaip JUODĄ, o gP spalvą - RED.
    6. Pasukite dešinėn gP.
  3. Kitu atveju atlikite šiuos veiksmus.
    1. Jei kairiojo gP z z vaiko spalva yra RAUDONA, nustatykite abiejų gP vaikų spalvą kaip JUODĄ, o gP - RED.
    2. Priskirkite GP prie „newNode“.
    3. Kitu atveju, jei „newNode“ yra kairysis p vaikas, priskirkite p „newNode“ ir dešiniuoju būdu pasukite naują
    4. Nustatykite p spalvą kaip JUODĄ, o gP spalvą - RED.
    5. Pasukite kairėn gP.
  4. Medžio šaknį nustatykite kaip JUODĄ.

Elemento ištrynimas iš raudonai juodo medžio

Ši operacija pašalina mazgą iš medžio. Ištrynus mazgą, raudona-juoda ypatybė vėl išlaikoma.

Algoritmas ištrinti mazgą

  1. Išsaugokite „nodeToBeDeleted“ spalvą origrinalColor.
  2. Jei kairysis nodeToBeDeleted vaikas yra NULL
    1. Priskirkite tinkamą „nodeToBeDeleted“ vaiką prie x.
    2. Transplantacijos mazgasToBeDeleted su x.
  3. Kitaip, jei yra tinkamas „nodeToBeDeleted“ vaikas NULL
    1. Priskirkite kairįjį „nodeToBeDeleted“ vaiką į x.
    2. Transplantacijos mazgasToBeDeleted su x.
  4. Kitas
    1. Priskirkite minimalų dešinį „noteToBeDeleted“ potemį į y.
    2. Išsaugokite y spalvą originalColor.
    3. Priskirkite „rightChild of y“ į x.
    4. Jei y yra „nodeToBeDeleted“ vaikas, tada x tėvą nustatykite kaip y.
    5. Kitaip, persodinkite y su dešiniuoju vaiku.
    6. Transplantacijos mazgasToBeDeleted su y.
    7. Nustatykite y spalvą naudodami „originalColor“.
  5. Jei „originalColor“ yra JUODA, paskambinkite „DeleteFix“ (x).

Algoritmas išlaikyti raudonai-juodą nuosavybę po ištrynimo

Šis algoritmas yra įgyvendinamas pašalinus juodą mazgą, nes jis pažeidžia raudonai juodo medžio juodojo gylio savybę.

Šis pažeidimas ištaisomas darant prielaidą, kad mazgas x (kuris užima pradinę y padėtį) turi papildomą juodą spalvą. Dėl to mazgas x nėra nei raudonas, nei juodas. Tai dvigubai juoda arba juodai raudona. Tai pažeidžia raudonai juodas savybes.

Tačiau spalvos atributas x nekeičiamas, o papildomai juoda spalva vaizduojama x rodant į mazgą.

Papildoma juoda spalva gali būti pašalinta, jei

  1. Jis pasiekia šaknies mazgą.
  2. Jei x rodo raudonai juodą mazgą. Šiuo atveju x yra juodos spalvos.
  3. Atliekami tinkami pasukimai ir perdažymas.

Šis algoritmas išlaiko raudonai juodo medžio savybes.

  1. Atlikite šiuos veiksmus, kol x nėra medžio šaknis, o x spalva yra JUODA
  2. Jei x yra kairysis jo tėvų vaikas,
    1. Priskirkite x x broliui.
    2. Jei tinkamas x tėvų vaikas yra RED,
      I atvejis:
      1. Tinkamo x tėvo vaiko vaiko spalvą nustatykite kaip JUODĄ.
      2. Nustatykite x tėvų spalvą kaip RED.
      3. Kairėje pusėje pasukite x tėvą.
      4. Priskirkite „x“ tėvų teisę „ChildC“.
    3. Jei tiek dešiniojo, tiek kairiojo w vaikas yra juoda,
      II atvejis:
      1. Nustatykite w spalvą kaip RED
      2. Priskirkite x tėvą x.
    4. Kitu atveju, jei dešiniojo vaiko spalva yra JUODA
      III atvejis:
      1. Kairiojo vaiko w spalvą nustatykite kaip JUODĄ
      2. Nustatykite w spalvą kaip RED
      3. Pasukite dešinėn.
      4. Priskirkite „x“ tėvų teisę „ChildC“.
    5. Jei kuris nors iš aukščiau išvardytų atvejų neatsiranda, atlikite šiuos veiksmus.
      IV atvejis:
      1. Nustatykite w spalvą kaip x tėvų spalvą.
      2. X tėvų spalvą nustatykite kaip JUODĄ.
      3. Tinkamo vaiko vaiko spalvą nustatykite kaip JUODĄ.
      4. Kairėje pusėje pasukite x tėvą.
      5. Nustatykite x kaip medžio šaknį.
  3. Kitaip, kaip nurodyta aukščiau, dešinę pakeitus į kairę ir atvirkščiai.
  4. X spalvą nustatykite kaip JUODĄ.

Daugiau paaiškinimų su pavyzdžiais ieškokite įterpimo ir ištrynimo operacijose.

„Python“, „Java“ ir „C / C ++“ pavyzdžiai

„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(); )

Raudonai-juodo medžio programos

  1. Įgyvendinti baigtinius žemėlapius
  2. Norėdami įdiegti „Java“ paketus: java.util.TreeMapirjava.util.TreeSet
  3. Įdiegti standartines šablonų bibliotekas (STL) C ++: multiset, map, multimap
  4. „Linux“ branduolyje

Įdomios straipsniai...