Code in Python:

red and black trees

a class Node for representing nodes of a tree: these carry key-value pairs as well as pointers to left and right children. In contrast to most implementations of red-black trees, however, there is no pointer from a node to its parent. We are able to dispense with this (and so save some space) by implementing insert with the help of a stack that keeps track of the relevant path through the tree. Type Node(5,five) to the Python prompt. Youll see a readable representation of the node this has created, with the colour initialized to red. Note, however, that this representation isnt itself a valid Python expression that could be used to construct a node. Near the end of the file, you will see some commands to construct a tree directly by hand. Typing sampleTree to the prompt will reveal a (semi-)readable representation of this tree, with subtrees indicated by square brackets. (Once again, this isnt a valid Python expression.) Building trees directly in this way is useful for testing and debugging, but is of course unsafe in that theres nothing here to enforce the rules for red-black trees. The safe way will be to start from the empty tree (created by RedBlackTree()) and repeatedly call the insert method, once you have implemented this.

You can also type

sampleTree.keysLtoR() 

to compute a list of all the keys present, obtained by traversing the tree from left to right. Within the class RedBlackTree itself, study the provided code for the methods repr

(which creates the readable representation) and keysLtoR. These provide examples of meth- ods implemented using a recursive helper function: this is the pattern you should follow in your implementation of lookup and insert.

At the point marked # TODO: Task 2, implement a method

 plainInsert(self,key,value) 

that inserts a new key-value pair into the ordered tree at the correct position, without worrying about colour information or the rules specific to red-black trees. The new node should be built using the Node constructor. If the given key is already present in the tree, the method should simply overwrite the existing value with the one given in this case it should not create a new node or make any other change to the tree.

You may follow the example of the insert method for plain binary trees from lectures. The case of inserting into an initially empty tree will need special treatment.

Once you have got the basic form of this method working, you should add suitable commands so that the path from the root to the new (or updated) node is recorded as a list in the self.stack field. Specifically, after calling the method, this field should contain the list of Node objects from the root to the new node, alternating with strings l or r to indicate the left or right branches. (We take advantage of the fact that Python permits mixed-type lists.) For example, calling

 sampleTree.plainInsert(5,five) sampleTree.showStack() 

should result in the list

 [2:two:B, r, 4:four:R, r, 6:six:B, l, 5:five:R] 

If the tree is initially empty, the stack after the insertion should contain just one node.

Of course, the tree resulting from plainInsert may not be a legal red-black tree. The purpose of Tasks 3 and 4 is to do the fix-up needed to obtain a legal tree.

Code in Python:

Red, Black = True, False

def colourStr(c): return 'R' if c==Red else 'B'

Left, Right = 0, 1

def opposite(branch): return 1 - branch

branchLabels = ['l','r']

class Node(): def __init__(self,key,value): self.key = key self.value = value self.colour = Red self.left = None self.right = None def getChild(self,branch): if branch==Left: return self.left else: return self.right

def setChild(self,branch,y): if branch==Left: self.left = y else: self.right = y

def __repr__(self): return str(self.key) +':'+ str(self.value) +':'+ colourStr(self.colour)

# Use None for all trivial leaf nodes

def colourOf(x): if x is None: return Black else: return x.colour

class RedBlackTree():

def __init__ (self): self.root = None self.stack = []

# TODO: Task 2. # plainInsert(self,key,value)