CS代考 Tutorial: Red-black Tree Implementation

Tutorial: Red-black Tree Implementation

Sample: Red-black Tree

Copyright By PowCoder代写 加微信 powcoder

Create a red-black tree by inserting [8,18,5,15,17,25,40,80]

Every node is either red or black.
The root is black.
Every leaf(NIL) is black.
No two consecutive nodes are red.
For each node x, all simple paths from the node to descendant leaves contain the same number of black nodes.

def RB_insert(self, x):
        self.root = self.rec_RB_insert(self.root,x)
        self.root.color = “black” 
        self.size += 1
def rec_RB_insert(self, v,x):
if v.is_a_leaf():
return NBnode(x)

Violate rule 4
Case 1: The Aunt/Uncle Node is RED
def RB_insert(self, x):
        self.root = self.rec_RB_insert(self.root,x)
        self.root.color = “black” 
        self.size += 1

Case 2: The Aunt/Uncle Node is Right Case

Case 1: The Aunt/Uncle Node is RED

/docProps/thumbnail.jpeg

程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com