Sarkanmelns koks

Šajā apmācībā jūs uzzināsiet, kas ir sarkanmelns koks. Jūs atradīsit arī dažādu sarkano-melno koku veikto darbību piemērus C, C ++, Java un Python.

Sarkanmelns koks ir pašbalansējošs binārs meklēšanas koks, kurā katrā mezglā ir papildu bits, lai apzīmētu mezgla krāsu - vai nu sarkanu, vai melnu.

Sarkanmelns koks atbilst šādām īpašībām:

  1. Sarkanā / melnā īpašība: katrs mezgls ir krāsains, vai nu sarkans, vai melns.
  2. Saknes īpašums: sakne ir melna.
  3. Lapu īpašums: Katra lapa (NIL) ir melna.
  4. Sarkanais īpašums: ja sarkanā mezglā ir bērni, tad bērni vienmēr ir melni.
  5. Dziļuma īpašība: Katram mezglam jebkuram vienkāršam ceļam no šī mezgla uz jebkuru tā pēcnācēju lapu ir vienāds melnais dziļums (melno mezglu skaits).

Sarkanmelna koka piemērs ir:

Sarkans melns koks

Katram mezglam ir šādi atribūti:

  • krāsa
  • taustiņu
  • pa kreisiBērns
  • rightBērns
  • vecāks (izņemot saknes mezglu)

Kā sarkanmelnais koks uztur sevis līdzsvarošanas īpašību?

Sarkanmelnā krāsa ir paredzēta koka līdzsvarošanai.

Mezglu krāsu ierobežojumi nodrošina, ka jebkurš vienkāršs ceļš no saknes līdz lapai ir ne vairāk kā divas reizes garāks nekā jebkurš cits šāds ceļš. Tas palīdz saglabāt sarkanbalts koka pašbalansējošo īpašību.

Operācijas ar sarkani melnu koku

Dažādas darbības, kuras var veikt ar sarkani melnu koku, ir:

Apakškoku pagriešana sarkanmelnā kokā

Rotācijas darbībā apakškoku mezglu pozīcijas tiek apmainītas.

Rotācijas darbību izmanto, lai saglabātu sarkanmelna koka īpašības, ja tās pārkāpj citas darbības, piemēram, ievietošana un dzēšana.

Ir divu veidu rotācijas:

Pagriezt pa kreisi

Pagriežot pa kreisi, mezglu izvietojums labajā pusē tiek pārveidots par kreisā mezgla izvietojumiem.

Algoritms

  1. Ļaujiet sākotnējam kokam būt: Sākotnējam kokam
  2. Ja y ir kreisā apakškoku, piešķiriet x kā y kreisās apakškoka vecāku. Piešķiriet x kā vecumu y kreisajai apakškokai
  3. Ja x vecāks ir NULL, izveidojiet y kā koka sakni.
  4. Citādi, ja x ir p kreisais bērns, izveidojiet y kā p kreiso bērnu.
  5. Citādi piešķiriet y kā pareizo p. Mainiet x vecāku uz y
  6. Izveidojiet y kā x vecāku. Piešķiriet y kā x vecāku.

Pagriezt pa labi

Pagriežot pa labi, kreisajā pusē esošo mezglu izvietojums tiek pārveidots par labā mezgla izvietojumiem.

  1. Ļaujiet sākotnējam kokam būt: Sākotnējam kokam
  2. Ja x ir labais apakškoks, piešķiriet y kā x labās apakškokas vecāku. Piešķiriet y kā x labās apakškopa vecāku
  3. Ja y vecāks ir NULL, izveidojiet x kā koka sakni.
  4. Citādi, ja y ir vecāka p pareizais bērns, izveidojiet x kā p pareizais bērns.
  5. Cits piešķir x kā kreiso bērnu p. Piešķiriet y vecāku kā x vecāku
  6. Izveidojiet x kā y vecāku. Piešķiriet x kā y vecāku

Pagriezt pa kreisi-pa labi un pa labi-pa kreisi

Pagriežot pa kreisi un pa labi, kārtojums vispirms tiek pārvietots pa kreisi un pēc tam pa labi.

  1. Veiciet kreiso pagriezienu pa xy. Pagriezieties pa kreisi xy
  2. Veiciet labo pagriezienu uz yz. Pagrieziet pa labi zy

Labajā un kreisajā rotācijā kārtība vispirms tiek pārvietota pa labi un pēc tam pa kreisi.

  1. Veiciet labo pagriezienu uz xy. Pagrieziet pa labi xy
  2. Veiciet kreiso rotāciju zy. Pa kreisi pagriezt zy

Elementa ievietošana sarkan-melnā kokā

Ievietojot jaunu mezglu, jaunais mezgls vienmēr tiek ievietots kā RED mezgls. Pēc jauna mezgla ievietošanas, ja koks pārkāpj sarkanmelnā koka īpašības, mēs veicam šādas darbības.

  1. Pārkrāsot
  2. Rotācija

Algoritms mezgla ievietošanai

Lai ievietotu jaunu elementu sarkanmelnā kokā, tiek veiktas šādas darbības:

  1. Ļaujiet y būt NILkoka lapai (ti. ) Un x - koka saknei.
  2. Pārbaudiet, vai koks ir tukšs (ti, vai x ir NIL). Ja jā, ievietojiet newNode kā saknes mezglu un iekrāsojiet to melnā krāsā.
  3. Citas darbības atkārto šīs darbības, līdz NILtiek sasniegta lapa ( ).
    1. Salīdziniet newKey ar rootKey.
    2. Ja newKey ir lielāks par rootKey, pārvietojieties pa labo apakškoku.
    3. Pārējie šķērso kreiso apakškoku.
  4. Piešķiriet lapas vecāku kā newNode vecāku.
  5. Ja leafKey ir lielāks par newKey, izveidojiet newNode kā rightChild.
  6. Citādi izveidojiet newNode kā leftChild.
  7. Piešķirt NULLnewNode kreisajam un labajam bērnam.
  8. Piešķirt RED krāsu newNode.
  9. Lai pārkāptu sarkano-melno koku īpašību, izsauciet algoritmu InsertFix.

Kāpēc nesen ievietotie mezgli sarkanā-melnā kokā vienmēr ir sarkani?

Tas ir tāpēc, ka, ievietojot sarkanu mezglu, netiek pārkāpts sarkanmelnā koka dziļuma īpašums.

Ja pie sarkanā mezgla pievienojat sarkanu mezglu, tiek pārkāpts noteikums, taču šo problēmu ir vieglāk novērst nekā problēmu, kas ieviesta, pārkāpjot īpašību dziļums.

Algoritms sarkanmelnās īpašības saglabāšanai pēc ievietošanas

Šo algoritmu izmanto sarkanmelna koka rekvizītu saglabāšanai, ja newNode ievietošana pārkāpj šo īpašību.

  1. Veiciet šādas darbības, kamēr newNode p vecākam ir RED.
  2. Ja p ir vecā vecāka gP z kreisais bērns, rīkojieties šādi.
    I gadījums:
    1. Ja labā zP g zīdaiņa krāsa ir RED, iestatiet gan gP bērnu krēslu kā BLACK, gan gP krāsu kā RED.
    2. Piešķiriet gP newNode.
      II lieta:
    3. Citādi, ja newNode ir pareizais p bērns, piešķiriet p newNode.
    4. Pagriezt pa kreisi pa kreisiNode.
      III lieta:
    5. Iestatiet p krāsu kā MELNU un gP krāsu - RED.
    6. Pagriezt pa labi pa labi.
  3. Pārējie rīkojieties šādi.
    1. Ja gP kreisā bērna z krāsa ir SARKANA, iestatiet gan gP bērnu bērnu krāsu kā MELNU, gan gP krāsu - RED.
    2. Piešķiriet gP newNode.
    3. Citādi, ja newNode ir p kreisais bērns, piešķiriet p newNode un Pagrieziet pa labi NewNode.
    4. Iestatiet p krāsu kā MELNU un gP krāsu - RED.
    5. Pagriezt pa kreisi pa kreisi.
  4. Iestatiet koka sakni kā MELNU.

Elementa dzēšana no sarkan-melna koka

Šī darbība noņem koku no mezgla. Pēc mezgla dzēšanas sarkanmelnā īpašība atkal tiek saglabāta.

Mezgla dzēšanas algoritms

  1. Saglabājiet nodeToBeDeleted krāsu origrinalColor.
  2. Ja mezglaToBeDeleted kreisais bērns ir NULL
    1. Piešķiriet nodeToBeDeleted labo bērnu x.
    2. Pārstādīšanas mezglsToBeDeleted ar x.
  3. Citādi, ja nodeToBeDeleted pareizais bērns ir NULL
    1. Piešķiriet nodeToBeDeleted kreiso bērnu x.
    2. Pārstādīšanas mezglsToBeDeleted ar x.
  4. Cits
    1. Piešķiriet minimālo labo apakškopa noteToBeDeleted apakšgrupā y.
    2. Saglabājiet y krāsu oriģinālajā krāsā.
    3. Piešķiriet y labo bērnu ar x.
    4. Ja y ir nodeToBeDeleted bērns, tad iestatiet x vecāku kā y.
    5. Pārējā gadījumā pārstādiet y ar labo bērnu.
    6. Pārstādīšanas mezglsToBeDeleted ar y.
    7. Iestatiet y krāsu ar oriģinālo krāsu.
  5. Ja originalColor ir MELNA, izsauciet DeleteFix (x).

Algoritms, lai pēc dzēšanas saglabātu sarkano-melno īpašību

Šis algoritms tiek ieviests, kad melnais mezgls tiek dzēsts, jo tas pārkāpj sarkanmelnā koka melnā dziļuma īpašību.

Šis pārkāpums tiek labots, pieņemot, ka mezglā x (kas aizņem y sākotnējo stāvokli) ir īpaši melns. Tas padara mezglu x ne sarkanu, ne melnu. Tas ir vai nu divreiz melns, vai melnbalts. Tas pārkāpj sarkanmelnās īpašības.

Tomēr x krāsas atribūts netiek mainīts, bet papildu melnais ir attēlots x norādot uz mezglu.

Papildu melno var noņemt, ja

  1. Tas sasniedz saknes mezglu.
  2. Ja x norāda uz sarkanu-melnu mezglu. Šajā gadījumā x ir melnā krāsā.
  3. Tiek veiktas piemērotas rotācijas un pārkrāsošana.

Šis algoritms saglabā sarkanmelnā koka īpašības.

  1. Veiciet šādas darbības, līdz x nav koka sakne un x krāsa ir MELNA
  2. Ja x ir vecāka kreisais bērns,
    1. Piešķiriet x x brālim un māsai.
    2. Ja x vecāku pareizais bērns ir RED,
      I gadījums:
      1. Iestatiet x vecāku labā bērna krāsu kā MELNU.
      2. Iestatiet x vecāka krāsu kā RED.
      3. Pagrieziet pa kreisi x vecāku.
      4. Piešķiriet x vecāka tiesībasBērns w.
    3. Ja labās un kreisās puses w bērns ir melns,
      II gadījums:
      1. Iestatiet w krāsu kā RED
      2. Piešķiriet x vecāku x.
    4. Citādi, ja labā bērna w krāsa ir MELNA,
      III gadījums:
      1. Iestatiet kreisāBērna w krāsu kā MELNU
      2. Iestatiet w krāsu kā RED
      3. Pagriezt pa labi
      4. Piešķiriet x vecāka tiesībasBērns w.
    5. Ja kāds no iepriekš minētajiem gadījumiem nenotiek, rīkojieties šādi.
      IV gadījums:
      1. Iestatiet w krāsu kā vecāku x krāsu.
      2. Iestatiet x vecāka krāsu kā MELNU.
      3. Iestatiet w labā bērna krāsu kā MELNU.
      4. Pagrieziet pa kreisi x vecāku.
      5. Iestatiet x kā koka sakni.
  3. Cits tas pats, kas iepriekš, ar labo pusi mainīts uz kreiso un otrādi.
  4. Iestatiet x krāsu kā MELNU.

Plašāku skaidrojumu ar piemēriem, lūdzu, skatiet ievietošanas un dzēšanas darbībās.

Python, Java un C / C ++ piemēri

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

Sarkanmelnā koka lietojumi

  1. Lai ieviestu ierobežotas kartes
  2. Lai ieviestu Java pakotnes: java.util.TreeMapunjava.util.TreeSet
  3. Lai ieviestu standarta veidņu bibliotēkas (STL) C ++: multiset, map, multimap
  4. Linux kodolā

Interesanti raksti...