#!/bin/env python3.1 # Bradley N. Miller, David L. Ranum # Introduction to Data Structures and Algorithms in Python # Copyright 2005, 2010 # class BinarySearchTree: ''' Author: Brad Miller Date: 1/15/2005 Description: Imlement a binary search tree with the following interface functions: __contains__(y) <==> y in x __getitem__(y) <==> x[y] __init__() __len__() <==> len(x) __setitem__(k,v) <==> x[k] = v clear() get(k) items() keys() values() put(k,v) in del <==> ''' def __init__(self): self.root = None self.size = 0 def put(self,key,val): if self.root: self._put(key,val,self.root) else: self.root = TreeNode(key,val) self.size = self.size + 1 def _put(self,key,val,currentNode): if key < currentNode.key: if currentNode.hasLeftChild(): self._put(key,val,currentNode.leftChild) else: currentNode.leftChild = TreeNode(key,val,parent=currentNode) else: if currentNode.hasRightChild(): self._put(key,val,currentNode.rightChild) else: currentNode.rightChild = TreeNode(key,val,parent=currentNode) def __setitem__(self,k,v): self.put(k,v) def get(self,key): if self.root: res = self._get(key,self.root) if res: return res.payload else: return None else: return None def _get(self,key,currentNode): if not currentNode: return None elif currentNode.key == key: return currentNode elif key < currentNode.key: return self._get(key,currentNode.leftChild) else: return self._get(key,currentNode.rightChild) def __getitem__(self,key): res = self.get(key) if res: return res else: raise KeyError('Error, key not in tree') def __contains__(self,key): if self._get(key,self.root): return True else: return False def length(self): return self.size def __len__(self): return self.size def __iter__(self): return self.root.__iter__() def delete(self,key): if self.size > 1: nodeToRemove = self._get(key,self.root) if nodeToRemove: self.remove(nodeToRemove) self.size = self.size-1 else: raise KeyError('Error, key not in tree') elif self.size == 1 and self.root.key == key: self.root = None self.size = self.size - 1 else: raise KeyError('Error, key not in tree') def __delitem__(self,key): self.delete(key) def remove(self,currentNode): if currentNode.isLeaf(): #leaf if currentNode == currentNode.parent.leftChild: currentNode.parent.leftChild = None else: currentNode.parent.rightChild = None elif currentNode.hasBothChildren(): #interior succ = currentNode.findSuccessor() succ.spliceOut() currentNode.key = succ.key currentNode.payload = succ.payload else: # this node has one child if currentNode.hasLeftChild(): if currentNode.isLeftChild(): currentNode.leftChild.parent = currentNode.parent currentNode.parent.leftChild = currentNode.leftChild elif currentNode.isRightChild(): currentNode.leftChild.parent = currentNode.parent currentNode.parent.rightChild = currentNode.leftChild else: currentNode.replaceNodeData(currentNode.leftChild.key, currentNode.leftChild.payload, currentNode.leftChild.leftChild, currentNode.leftChild.rightChild) else: if currentNode.isLeftChild(): currentNode.rightChild.parent = currentNode.parent currentNode.parent.leftChild = currentNode.rightChild elif currentNode.isRightChild(): currentNode.rightChild.parent = currentNode.parent currentNode.parent.rightChild = currentNode.rightChild else: currentNode.replaceNodeData(currentNode.rightChild.key, currentNode.rightChild.payload, currentNode.rightChild.leftChild, currentNode.rightChild.rightChild) def inorder(self): self._inorder(self.root) def _inorder(self,tree): if tree != None: self._inorder(tree.leftChild) print(tree.key) self._inorder(tree.rightChild) def postorder(self): self._postorder(self.root) def _postorder(self, tree): if tree: self._postorder(tree.rightChild) self._postorder(tree.leftChild) print(tree.key) def preorder(self): self._preorder(self,self.root) def _preorder(self,tree): if tree: print(tree.key) self._preorder(tree.leftChild) self._preorder(tree.rightChild) class TreeNode: def __init__(self,key,val,left=None,right=None,parent=None): self.key = key self.payload = val self.leftChild = left self.rightChild = right self.parent = parent self.balanceFactor = 0 def hasLeftChild(self): return self.leftChild def hasRightChild(self): return self.rightChild def isLeftChild(self): return self.parent and self.parent.leftChild == self def isRightChild(self): return self.parent and self.parent.rightChild == self def isRoot(self): return not self.parent def isLeaf(self): return not (self.rightChild or self.leftChild) def hasAnyChildren(self): return self.rightChild or self.leftChild def hasBothChildren(self): return self.rightChild and self.leftChild def replaceNodeData(self,key,value,lc,rc): self.key = key self.payload = value self.leftChild = lc self.rightChild = rc if self.hasLeftChild(): self.leftChild.parent = self if self.hasRightChild(): self.rightChild.parent = self def findSuccessor(self): succ = None if self.hasRightChild(): succ = self.rightChild.findMin() else: if self.parent: if self.isLeftChild(): succ = self.parent else: self.parent.rightChild = None succ = self.parent.findSuccessor() self.parent.rightChild = self return succ def spliceOut(self): if self.isLeaf(): if self.isLeftChild(): self.parent.leftChild = None else: self.parent.rightChild = None elif self.hasAnyChildren(): if self.hasLeftChild(): if self.isLeftChild(): self.parent.leftChild = self.leftChild else: self.parent.rightChild = self.leftChild self.leftChild.parent = self.parent else: if self.isLeftChild(): self.parent.leftChild = self.rightChild else: self.parent.rightChild = self.rightChild self.rightChild.parent = self.parent def findMin(self): current = self while current.hasLeftChild(): current = current.leftChild return current def __iter__(self): """The standard inorder traversal of a binary tree.""" if self: if self.hasLeftChild(): for elem in self.leftChild: yield elem yield self.key if self.hasRightChild(): for elem in self.rightChild: yield elem