Punainen-musta puu

Tässä opetusohjelmassa opit, mikä on punainen-musta puu. Löydät myös toimivia esimerkkejä erilaisista toiminnoista, jotka on suoritettu punamustalla puulla C, C ++, Java ja Python.

Puna-musta puu on itsetasapainotettu binäärihakupuu, jossa jokainen solmu sisältää ylimääräisen bitin solmun värin, joko punaisen tai mustan, merkitsemiseksi.

Puna-musta puu täyttää seuraavat ominaisuudet:

  1. Punainen / musta ominaisuus: Jokainen solmu on värillinen, joko punainen tai musta.
  2. Root-ominaisuus: Juuri on musta.
  3. Lehtien ominaisuus: Jokainen lehti (NIL) on musta.
  4. Punainen ominaisuus: Jos punaisella solmulla on lapsia, lapset ovat aina mustia.
  5. Syvyysominaisuus: Jokaisella solmulla kaikilla yksinkertaisilla polkuilla tästä solmusta mille tahansa sen jälkeläiselle on sama mustasyvyys (mustien solmujen lukumäärä).

Esimerkki puna-mustasta puusta on:

Punainen musta puu

Jokaisella solmulla on seuraavat määritteet:

  • väri-
  • avain
  • leftLapsi
  • oikeaLapsi
  • vanhempi (paitsi juurisolmu)

Kuinka punamusta puu ylläpitää itsetasapainon ominaisuutta?

Punainen-musta väri on tarkoitettu puun tasapainottamiseen.

Solmuväreille asetetut rajoitukset varmistavat, että mikään yksinkertainen polku juuresta lehteen on enintään kaksi kertaa niin pitkä kuin mikä tahansa muu tällainen polku. Se auttaa ylläpitämään puna-mustan puun itsetasapainoa.

Operaatiot puna-mustalla puulla

Puna-mustalle puulle voidaan suorittaa useita toimintoja:

Puunmusta puun osapuiden pyörittäminen

Kiertooperaatiossa osapuun solmujen sijainnit vaihdetaan.

Kiertooperaatiota käytetään ylläpitämään punamustan puun ominaisuuksia, kun muut toiminnot, kuten lisäys ja poisto, rikkovat niitä.

Kierroksia on kahdenlaisia:

Kierrä vasemmalle

Vasemmalla kiertämällä oikeanpuoleisten solmujen järjestely muutetaan vasemman solmun järjestelyiksi.

Algoritmi

  1. Olkoon alkuperäinen puu: Alkuperäinen puu
  2. Jos y: llä on vasen alipuu, määritä x y: n vasemman osapuun vanhemmaksi. Määritä x y: n vasemman alipuun vanhemmaksi
  3. Jos x: n vanhempi on NULL, tee puun juureksi y.
  4. Muutoin, jos x on p: n vasen lapsi, tee y p: n vasemmaksi lapseksi.
  5. Määritä muuten y p: n oikealle lapselle. Muuta x: n vanhempi y: ksi
  6. Tee y x: n vanhemmaksi. Määritä y x: n vanhemmaksi.

Kierrä oikealle

Oikeakierrossa vasemmalla olevien solmujen järjestely muutetaan oikean solmun järjestelyiksi.

  1. Olkoon alkuperäinen puu: Alkuperäinen puu
  2. Jos x: llä on oikea alipuu, määritä y x: n oikean osapuun vanhemmaksi. Määritä y x: n oikean alipuun vanhemmaksi
  3. Jos y: n vanhempi on NULL, tee x puun juureksi.
  4. Muuten, jos y on vanhemmansa p oikea lapsi, tee x p: n oikealla lapsella.
  5. Määritä muutoin x p: n vasemmaksi lapseksi. Määritä y: n vanhempi x: n vanhemmaksi
  6. Tee x y: n vanhemmaksi. Määritä x y: n vanhemmaksi

Vasen-oikea ja oikea-vasen kääntyvät

Vasemman ja oikean käänteessä järjestelyt siirretään ensin vasemmalle ja sitten oikealle.

  1. Tee vasemmalle kiertäminen xy: llä. Kierrä vasemmalle xy
  2. Kiertää oikealla puolella yz. Kierrä oikealle zy

Oikean ja vasemman käännöksen yhteydessä järjestelyt siirretään ensin oikealle ja sitten vasemmalle.

  1. Käännä oikealle xy. Kierrä oikealle xy
  2. Tee vasemmalle kiertäminen zy: llä. Kierrä vasemmalle zy

Elementin lisääminen puna-mustaan ​​puuhun

Uuden solmun lisäyksen aikana uusi solmu lisätään aina PUNAISEKSI. Uuden solmun lisäämisen jälkeen teemme seuraavat toimenpiteet, jos puu rikkoo punamustan puun ominaisuuksia.

  1. Väritä uudelleen
  2. Kierto

Algoritmi solmun lisäämiseksi

Seuraavat vaiheet tehdään uuden elementin lisäämiseksi puna-mustaan ​​puuhun:

  1. Olkoon y NILpuun lehti (ts. ) Ja x puun juuri.
  2. Tarkista, onko puu tyhjä (ts. Onko x NIL). Jos kyllä, lisää newNode juurisolmuksi ja väritä se mustaksi.
  3. Toista vaiheet seuraavasti, kunnes lehti ( NIL) saavutetaan.
    1. Vertaa newKey-tiedostoa rootKey-koodiin.
    2. Jos newKey on suurempi kuin rootKey, kulje oikean alipuun läpi.
    3. Muut kulkevat vasemman osapuun läpi.
  4. Määritä lehden vanhempi newNoden vanhemmaksi.
  5. Jos leafKey on suurempi kuin newKey, tee newNode oikeaksi lapseksi.
  6. Muuten tee uusi solmu vasemmaksi lapseksi.
  7. Määritä NULLnewNoden vasemmalle ja oikealle lapselle.
  8. Määritä PUNAINEN väri newNodelle.
  9. Kutsu InsertFix-algoritmi ylläpitämään punamustan puun ominaisuutta, jos sitä rikotaan.

Miksi äskettäin asetetut solmut ovat aina punaisia ​​mustassa puussa?

Tämä johtuu siitä, että punaisen solmun lisääminen ei riko puna-mustan puun syvyysominaisuutta.

Jos liität punaisen solmun punaiseen solmuun, sääntöä rikotaan, mutta ongelman korjaaminen on helpompaa kuin syvyysominaisuuden rikkomisen aiheuttama ongelma.

Algoritmi puna-mustan ominaisuuden ylläpitämiseksi lisäyksen jälkeen

Tätä algoritmia käytetään ylläpitämään puna-mustan puun ominaisuutta, jos newNode-lisäys rikkoo tätä ominaisuutta.

  1. Tee seuraava, kun newNode p: n ylätaso on PUNAINEN.
  2. Jos p on z: n grandParent gP: n vasen lapsi, toimi seuraavasti.
    Tapaus I:
    1. Jos z: n oikean lapsen gP: n väri on PUNAINEN, aseta sekä gP: n lasten väri MUSTAKSI että gP: n väri PUNAISEKSI.
    2. Määritä gP newNodelle.
      Tapaus II:
    3. Muussa tapauksessa määritä p uudelle solmulle, jos newNode on p: n oikea lapsi.
    4. Kierrä vasemmalle newNode.
      Tapaus III:
    5. Aseta p: n väri MUSTAKSI ja gP: n väri PUNAISEKSI.
    6. Kierrä oikealle gP.
  3. Toisin, tee seuraava.
    1. Jos z: n gP: n vasemman lapsen väri on PUNAINEN, aseta molempien gP: n lasten väri MUSTAKSI ja gP: n PUNAISEKSI.
    2. Määritä gP newNodelle.
    3. Muussa tapauksessa, jos newNode on p: n vasen lapsi, määritä p uudelle solmulle ja Kierrä oikealle uudelle solmulle.
    4. Aseta p: n väri MUSTAKSI ja gP: n väri PUNAISEKSI.
    5. Kierrä vasemmalle gP.
  4. Aseta puun juureksi MUSTA.

Elementin poistaminen puna-mustasta puusta

Tämä toiminto poistaa solmun puusta. Solmun poistamisen jälkeen puna-musta ominaisuus säilyy uudelleen.

Algoritmi solmun poistamiseksi

  1. Tallenna nodeToBeDeleted-väri origrinalColor-tiedostoon.
  2. Jos solmunToBeDeleted vasen lapsi on NULL
    1. Määritä solmunToBeDeleted oikea lapsi x: ksi.
    2. SiirtosolmuToBePoistettu x: llä.
  3. Muuten, jos solmunToBeDeleted oikea lapsi on NULL
    1. Määritä solmunToBeDeleted vasen lapsi x: ksi.
    2. SiirtosolmuToBePoistettu x: llä.
  4. Muu
    1. Määritä y: ksi noteToBeDeleted-oikean alaosan vähimmäispuu.
    2. Tallenna y-väri alkuperäiseen väriin.
    3. Määritä y: n rightChild x: ksi.
    4. Jos y on solmunToBeDeleted lapsi, aseta x: n vanhempi y: ksi.
    5. Muuten siirrä y oikealla lapsella.
    6. SiirtosolmuToBePoistettu y: llä.
    7. Aseta y: n väri originalColor-värillä.
  5. Jos originalColor on MUSTA, soita DeleteFix (x).

Algoritmi puna-mustan ominaisuuden ylläpitämiseksi poistamisen jälkeen

Tämä algoritmi otetaan käyttöön, kun musta solmu poistetaan, koska se rikkoo puna-mustan puun mustan syvyyden ominaisuutta.

Tämä rikkomus korjataan olettaen, että solmulla x (joka on y: n alkuperäisessä asemassa) on ylimääräinen musta. Tämä ei tee solmusta x punaiseksi eikä mustaksi. Se on joko kaksinkertaisesti mustaa tai mustaa ja punaista. Tämä rikkoo puna-mustia ominaisuuksia.

X: n väriominaisuutta ei kuitenkaan muuteta, vaan ylimääräinen musta näkyy x: n osoittamassa solmuun.

Ylimääräinen musta voidaan poistaa, jos

  1. Se saavuttaa juurisolmun.
  2. Jos x osoittaa puna-mustaa solmua. Tässä tapauksessa x on väriltään musta.
  3. Suoritetaan sopivat kierrot ja värjäys.

Seuraava algoritmi säilyttää punamustan puun ominaisuudet.

  1. Toimi seuraavasti, kunnes x ei ole puun juuri ja x: n väri on MUSTA
  2. Jos x on vanhemmansa vasen lapsi,
    1. Määritä w x: n sisarukselle.
    2. Jos x: n vanhemman oikea lapsi on PUNAINEN,
      tapaus I:
      1. Aseta x: n vanhemman oikean lapsen väriksi MUSTA.
      2. Aseta x: n ylätason väri PUNAISEKSI.
      3. Kierrä vasemmalla x: n vanhempaa.
      4. Määritä x: n vanhemman rightChild lapseksi.
    3. Jos w: n sekä oikean että vasemman lapsen väri on MUSTA,
      tapaus II:
      1. Aseta w: n väri PUNAISEKSI
      2. Määritä x: n ylätaso x: lle.
    4. Muuten, jos w: n oikean lapsen väri on MUSTA
      tapaus III:
      1. Aseta w: n vasemman lapsen väri MUSTAKSI
      2. Aseta w: n väri PUNAISEKSI
      3. Kierrä oikealle w.
      4. Määritä x: n vanhemman rightChild lapseksi.
    5. Jos jotakin yllä olevista tapauksista ei esiinny, toimi seuraavasti.
      Tapaus IV:
      1. Aseta w: n väri x: n ylätason väriksi.
      2. Aseta x: n ylätason väri MUSTA.
      3. Aseta w: n oikean lapsen väri MUSTAKSI.
      4. Kierrä vasemmalla x: n vanhempaa.
      5. Aseta x puun juureksi.
  3. Muuten sama kuin yllä, oikea vaihdetaan vasemmalle ja päinvastoin.
  4. Aseta x: n väriksi MUSTA.

Katso lisää selityksiä esimerkeistä lisäys- ja poistotoiminnoista.

Python-, Java- ja C / C ++ -esimerkkejä

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

Puna-musta puu -sovellukset

  1. Rajoitettujen karttojen toteuttaminen
  2. Java-pakettien käyttöönotto: java.util.TreeMapjajava.util.TreeSet
  3. Tavallisten mallikirjastojen (STL) käyttöönotto C ++: ssa: multiset, map, multimap
  4. Linux-ytimessä

Mielenkiintoisia artikkeleita...