Puna-must puu

Selles õpetuses saate teada, mis on punane-must puu. Samuti leiate toimivaid näiteid erinevatest toimingutest, mis on tehtud punaselt mustal puul C, C ++, Java ja Python.

Punamust puu on isetasakaalustuv kahendotsingupuu, milles iga sõlm sisaldab lisabitti sõlme värvi tähistamiseks, kas punase või mustana.

Punane-must puu vastab järgmistele omadustele:

  1. Punane / must omadus: iga sõlm on värviline, kas punane või must.
  2. Juureomadus: juur on must.
  3. Lehe omadus: iga leht (NIL) on must.
  4. Punane omadus: kui punasel sõlmel on lapsi, on lapsed alati mustad.
  5. Sügavuse omadus: iga sõlme puhul on selle sõlme mis tahes järeltulijale lihtsal teel sama mustsügavus (mustade sõlmede arv).

Punamust puu näide on:

Punane must puu

Igal sõlmel on järgmised atribuudid:

  • värv
  • võti
  • leftChild
  • rightChild
  • vanem (välja arvatud juursõlm)

Kuidas punane-must puu säilitab isetasakaalustamise omaduse?

Punane-must värv on mõeldud puu tasakaalustamiseks.

Sõlmevärvidele seatud piirangud tagavad, et mis tahes lihtne tee juurest leheni on kuni kaks korda pikem kui mis tahes muu selline tee. See aitab säilitada punase-musta puu isetasakaalustavat omadust.

Operatsioonid puna-mustal puul

Punaselt mustal puul saab teha erinevaid toiminguid:

Alampuude pööramine punases-mustas puus

Pöörlemisoperatsioonis vahetatakse alampuu sõlmede asukohad.

Pöörlemistoimingut kasutatakse punase-musta puu omaduste säilitamiseks, kui neid muud toimingud, näiteks sisestamine ja kustutamine, rikuvad.

Pöördeid on kahte tüüpi:

Vasakule pööramine

Vasakpoolses pöörlemises muudetakse parempoolsete sõlmede paigutus vasaku sõlme paigutusteks.

Algoritm

  1. Olgu algpuu: Algpuu
  2. Kui y-l on vasak alampuu, määrake x y-i vasaku alampuu vanemaks. Määra x y vasakpoolse alampuu vanemaks
  3. Kui xi vanem on NULL, siis tehke puu juureks y.
  4. Muul juhul, kui x on p p vasak laps, tehke y p vasakpoolseks lapseks.
  5. Muul juhul määrake y p-i õigeks lapseks. Muutke xi vanem y-ks
  6. Tehke y x-i vanemaks. Määra y x-i vanemaks.

Paremale pöörake

Paremal pööramisel muudetakse vasakpoolsete sõlmede paigutus parempoolse sõlme paigutusteks.

  1. Olgu algpuu: Algpuu
  2. Kui x-l on parem alampuu, määrake x-i parema alampuu vanemaks y. Määra y x-i parema alampuu vanemaks
  3. Kui y on vanem NULL, siis tehke puu juureks x.
  4. Muul juhul, kui y on oma vanema p õige laps, tehke x p-i õige lapsena.
  5. Muul juhul määrake x vasakule lapsele x. Määrake x vanemaks y vanem
  6. Tehke y vanemana x. Määrake x vanemaks y

Vasak-parem ja parem-vasak pööramine

Vasakul-paremal pööramisel nihutatakse paigutus kõigepealt vasakule ja seejärel paremale.

  1. Tehke vasakul pööramine xy-l. Vasakul pöörake xy
  2. Tehke parempoolne pöörlemine yz-l. Paremale pöörake zy

Parema ja vasaku pööramise korral nihutatakse seaded kõigepealt paremale ja seejärel vasakule.

  1. Pöörake xy-l paremale. Paremale pöörake xy
  2. Tehke vasak pööramine zy-l. Vasakul pöörake zy

Elemendi lisamine puna-mustasse puusse

Uue sõlme sisestamise ajal sisestatakse uus sõlm alati PUNASEKS. Pärast uue sõlme sisestamist teeme järgmised toimingud, kui puu rikub punase-musta puu omadusi.

  1. Värvida
  2. Pööramine

Algoritm sõlme sisestamiseks

Uue elemendi lisamiseks puna-musta puusse järgitakse järgmisi samme:

  1. Olgu y leht (st. NIL) Ja x puu juur.
  2. Kontrollige, kas puu on tühi (st kas x on NIL). Kui jah, sisestage juursõlmeks newNode ja värvige see mustaks.
  3. Muul juhul korrake järgmisi samme, kuni NILon saavutatud leht ( ).
    1. Võrdle newKey juurklahviga.
    2. Kui newKey on suurem kui rootKey, liikuge läbi parema alampuu.
    3. Muul viisil läbitakse vasakpoolne alampuu.
  4. Määrake lehe vanem newNode'i vanemaks.
  5. Kui leafKey on suurem kui newKey, tehke newNode nimega rightChild.
  6. Muidu tehke uusNode vasaklapsena.
  7. Määrake NULLnewNode'i vasakule ja paremale lapsele.
  8. Määrake newNode'ile PUNANE värv.
  9. Helistades sisestage algoritm InsertFix, et säilitada rikkumise korral punase-musta puu omadus.

Miks äsja sisestatud sõlmed on punases-mustas puus alati punased?

Seda seetõttu, et punase sõlme sisestamine ei riku punase-musta puu sügavuse omadust.

Kui kinnitate punase sõlme punase sõlme külge, siis reeglit rikutakse, kuid selle probleemi lahendamine on lihtsam kui omaduse sügavus rikkumise korral.

Algoritm punase-musta omaduse säilitamiseks pärast sisestamist

Seda algoritmi kasutatakse punase-musta puu atribuudi säilitamiseks, kui newNode'i sisestamine rikub seda omadust.

  1. Tehke järgmist, kui newNode p vanem on PUNANE.
  2. Kui p on z vanavanema gP vasak laps, tehke järgmist.
    Juhtum I:
    1. Kui z parema lapse gP väärtus on PUNANE, määrake nii gP laste värv mustaks kui ka gP värv Punaseks.
    2. Määrake gP uuele sõlmele.
      II juhtum:
    3. Muul juhul, kui newNode on p õige poeg, määrake p newNode'ile.
    4. Pöörake vasakule newNode.
      III juhtum:
    5. Määrake p värviks MUST ja gP värviks PUNANE.
    6. Parem pöörake gP.
  3. Muidu tehke järgmist.
    1. Kui gP vasakpoolse lapse värv z on PUNANE, määrake nii gP laste värv mustaks kui ka gP värv Punaseks.
    2. Määrake gP uuele sõlmele.
    3. Muul juhul, kui newNode on p vasak vasak laps, määrake p newNode'ile ja paremale pöörake newNode.
    4. Määrake p värviks MUST ja gP värviks PUNANE.
    5. Vasakule pööramine gP.
  4. Määrake puu juureks MUST.

Punasest-mustast puust elemendi kustutamine

See toiming eemaldab puult sõlme. Pärast sõlme kustutamist säilitatakse punane-must omadus uuesti.

Algoritm sõlme kustutamiseks

  1. Salvestage nodeToBeDeleted värv originaaliColor.
  2. Kui nodeToBeDeleted vasak laps on NULL
    1. Määrake nodeToBeDeleted õige laps väärtuseks x.
    2. Siirdamise sõlmToBeDelted x-ga.
  3. Muul juhul, kui nodeToBeDeleted õige laps on NULL
    1. Määrake nodeToBeDeleted vasak laps x -iks.
    2. Siirdamise sõlmToBeDelted x-ga.
  4. Muidu
    1. Määrake y-sse notToBeDeleted parempoolse alampuu miinimum.
    2. Salvestage y värv originaaliColor.
    3. Määrake y-ga rightChild väärtuseks x.
    4. Kui y on nodeToBeDeleted laps, siis määrake x-i vanemaks y.
    5. Muul juhul siirdage y parempoolse lapsega.
    6. SiirdamissõlmToBeKustutatud y-ga.
    7. Määrake y värv OriginalColor abil.
  5. Kui originalColor on MUST, helistage DeleteFix (x).

Algoritm punase-musta omaduse säilitamiseks pärast kustutamist

See algoritm rakendatakse musta sõlme kustutamisel, kuna see rikub punase-musta puu musta sügavuse omadust.

See rikkumine parandatakse eeldades, et sõlmel x (mis hõivab y algset positsiooni) on ekstra must. See muudab sõlme x ei punaseks ega mustaks. See on kas kahekordselt must või must-punane. See rikub punase-musta omadusi.

Kuid x värvi atribuuti ei muudeta, vaid ekstra must on esindatud x-s sõlme osutamisel.

Eriti musta saab eemaldada, kui

  1. See jõuab juursõlmesse.
  2. Kui x osutab punasele-mustale sõlmele. Sellisel juhul on x musta värvi.
  3. Tehakse sobivad pööramised ja värvimine.

Järgmine algoritm säilitab punase-musta puu omadused.

  1. Tehke järgmist, kuni x ei ole puu juur ja x värv on MUST
  2. Kui x on vanema vasak laps,
    1. Määrake w x-i vennale.
    2. Kui x-i vanema õige laps on PUNANE, siis
      :
      1. Määrake x vanema parema lapse värviks MUST.
      2. Määrake x vanema värviks PUNANE.
      3. Pöörake vasakule x-i vanemat.
      4. Määrake x-i vanema rightChild w-le.
    3. Kui w-i parema ja vasakpoolse lapse värv on MUST,
      juhtum II:
      1. Määrake w värviks PUNANE
      2. Määrake x-i vanem x -iks.
    4. Muul juhul, kui parema lapse w värv on MUST
      Juhtum III:
      1. Määrake vasaku lapse w värviks MUST
      2. Määrake w värviks PUNANE
      3. Paremale pööramine
      4. Määrake x-i vanema rightChild w-le.
    5. Kui mõnda ülalnimetatud juhtumist ei esine, tehke järgmist.
      IV juhtum:
      1. Määrake x vanema värviks w värv.
      2. Määrake x vanema värviks must.
      3. Parema w-lapse lapse värviks määrake MUST.
      4. Pöörake vasakule x-i vanemat.
      5. Määra puu juureks x.
  3. Muul viisil nagu ülal, paremal vasakule ja vastupidi.
  4. Määrake x värviks MUST.

Lisateavet näidete kohta leiate lisamis- ja kustutamistoimingutest.

Pythoni, Java ja C / C ++ näited

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

Punase-musta puu rakendused

  1. Lõplike kaartide rakendamiseks
  2. Java-pakettide juurutamiseks: java.util.TreeMapjajava.util.TreeSet
  3. Rakendada standardseid malliraamatukogusid (STL) C ++ -s: multiset, map, multimap
  4. Linuxi tuumas

Huvitavad Artiklid...