Imported Code

class treeNode: def __init__(self, parent=None, leftright=None, superroot=True): self.value = None self.leftNode = None self.rightNode = None self.parent = parent self.leftright = leftright self.superroot = superroot if superroot: self.setValue(None) def clearTree(self): if self.superroot: self.setValue(None) def getNode(self, i): if self.superroot: return self.leftNode if self.value > i: return self.leftNode return self.rightNode def free(self): if self.superroot: return False if not self.value is None: return False return True def printTree(self, space=""): if self.superroot: self.leftNode.printTree(space) return if self.value is None: return self.rightNode.printTree(space + " ") print (space + self.value.__str__()) self.leftNode.printTree(space + " ") def setValue(self, i): self.value = i self.leftNode = self.__class__(self, "left", False) if not self.superroot: self.rightNode = self.__class__(self, "right", False) def setNode(self, node, leftright): if self.superroot: leftright = "left" if leftright == "left": self.leftNode = node self.leftNode.parent = self self.leftNode.leftright = "left" return self.rightNode = node self.rightNode.parent = self self.rightNode.leftright = "right" def sibling(self, child): if child.leftright == "left": return self.rightNode return self.leftNode def insertValue(self, i): if self.superroot: self.leftNode.insertValue(i) return if self.free(): self.setValue(i) return self.getNode(i).insertValue(i) def insertArray(self, a): if not self.superroot: self.parent.insertArray(a) return for i in a: self.insertValue(i) def insertFile(self, filename): f = open(filename) l = f.readline() l = l.split() a = [] for i in l: a.append(int(i)) self.insertArray(a) def searchPrint(self, k, complete=False, findString=""): if self.superroot: self.getNode(k).searchPrint(k, complete, findString) return if not self.parent.superroot: findString += " -> " findString += self.value.__str__() if self.value == k: print findString return if self.value is None: if complete: print(findString) else: print("the input number was not found in the BST") return self.getNode(k).searchPrint(k, complete, findString) def searchPrintComplete(self, k): self.searchPrint(k, True) def heightOfNode(self): if self.superroot: return self.leftNode.heightOfNode() if self.value is None: return -1 return max(self.leftNode.heightOfNode(), self.rightNode.heightOfNode()) + 1 def balancedNode(self): if self.superroot: if self.leftNode.balancedNode() == -2: return False return True if self.value is None: return -1 left = self.leftNode.balancedNode() right = self.rightNode.balancedNode() if (left == -2) or (right == -2): return -2 if abs(left - right) > 1: return -2 return max(left, right) + 1

Project Code

class rbTreeNode(treeNode): def __init__(self, parent=None, leftright=None, superroot=True): treeNode.__init__(self, parent, leftright, superroot) self.colour = None def printTree(self, space=""): if self.superroot: self.leftNode.printTree(space) return if self.value is None: return self.rightNode.printTree(space + " ") if self.colour == "red": print (space + 'R' + ' ' + self.value.__str__()) else: print (space + 'B' + ' ' + self.value.__str__()) self.leftNode.printTree(space + " ") def setValue(self, i): treeNode.setValue(self, i) self.setColour("red") def setColour(self, colour): if self.superroot: return self.colour = colour if self.parent.superroot: self.colour = "black" return if self.colour == "red" and self.parent.colour == "red": sib = self.parent.parent.sibling(self.parent) grand = self.parent.parent parent = self.parent if sib.colour == "red": sib.setColour("black") parent.setColour("black") grand.setColour("red") else: if parent.leftright == "right": if self.leftright == "right": if grand.leftright == "right": grand.parent.setNode(parent, "right") else: grand.parent.setNode(parent, "left") grand.setNode(parent.leftNode, "right") parent.setNode(grand, "left") parent.setColour("black") grand.setColour("red") else: if grand.leftright == "right": grand.parent.setNode(self, "right") else: grand.parent.setNode(self, "left") parent.setNode(self.rightNode, "left") grand.setNode(self.leftNode, "right") self.setNode(grand, "left") self.setNode(parent, "right") self.setColour("black") grand.setColour("red") else: if self.leftright == "right": if grand.leftright == "right": grand.parent.setNode(self, "right") else: grand.parent.setNode(self, "left") parent.setNode(self.leftNode, "right") grand.setNode(self.rightNode, "left") self.setNode(grand, "right") self.setNode(parent, "left") self.setColour("black") grand.setColour("red") else: if grand.leftright == "right": grand.parent.setNode(parent, "right") else: grand.parent.setNode(parent, "left") grand.setNode(parent.rightNode, "left") parent.setNode(grand, "right") parent.setColour("black") grand.setColour("red")

Commands

tree = rbTreeNode() tree.insertValue(1) tree.printTree() print '' tree.insertValue(2) tree.printTree() print '' tree.insertValue(3) tree.printTree() print '' tree.insertValue(4) tree.printTree() print '' tree.insertValue(5) tree.printTree() print '' tree.insertValue(6) tree.printTree() print '' tree.insertValue(7) tree.printTree() print '' tree.insertValue(8) tree.printTree() print '' tree.insertValue(9) tree.printTree() print '' tree.insertValue(0) tree.printTree()

Run

Output