{ "metadata": { "name": "", "signature": "sha256:8fd742e3911255005d5cc80d3e792a10aed91d6e12fc125e66cc3c416b974be7" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "heading", "level": 1, "metadata": {}, "source": [ "Chapter 10 : 2-3-4 Trees and External Storage" ] }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "Example 10.1 Page No : 478" ] }, { "cell_type": "code", "collapsed": false, "input": [ " \n", "class DataItem:\n", " def __init__(self,dd):\n", " self.dData = dd\n", "\n", " def displayItem(self):\n", " print '/' ,self.dData\n", "\n", "class Node:\n", " def __init__(self):\n", " self.ORDER = 4\n", " self.numItems = 0\n", " self.parent = None\n", " self.childArray = [None,None,None,None]\n", " self.itemArray = [None,None,None]\n", "\n", " def connectChild(self,childNum,child):\n", " self.childArray[childNum] = child\n", " if(child != None):\n", " child.parent = self\n", "\n", " def disconnectChild(self,childNum):\n", " tempNode = self.childArray[childNum]\n", " self.childArray[childNum] = None\n", " return tempNode\n", "\n", " def getChild(self,childNum):\n", " return self.childArray[childNum]\n", "\n", " def getParent(self):\n", " return self.parent\n", "\n", " def isLeaf(self):\n", " if self.childArray[0]==None:\n", " return True \n", " return False \n", "\n", " def getNumItems(self):\n", " return self.numItems\n", "\n", " def getItem(self,index): # get DataItem at index\n", " return self.itemArray[index] \n", "\n", " def isFull(self):\n", " if self.numItems==self.ORDER-1:\n", " return True\n", " return False\n", "\n", " def findItem(self,key): # return index of # item (within node)\n", " for j in range(self.ORDER-1): \n", " if(self.itemArray[j] == None):\n", " break\n", " elif(self.itemArray[j].dData == key):\n", " return j\n", " return -1\n", "\n", " def insertItem(self,newItem):\n", " #assumes node is not full\n", " self.numItems += 1 # will add new item\n", " newKey = newItem.dData # key of new item\n", " j = self.ORDER - 2\n", " while j>=0:\n", " if(self.itemArray[j] == None):\n", " continue\n", " else:\n", " itsKey = self.itemArray[j].dData\n", " if(newKey < itsKey):\n", " self.itemArray[j+1] = self.itemArray[j]\n", " else:\n", " self.itemArray[j+1] = newItem\n", " return j+1 # return index to\n", " j -= 1\n", "\n", " self.itemArray[0] = newItem # insert new item\n", " return 0\n", "\n", " def removeItem(self): # remove largest item\n", " temp = self.itemArray[self.numItems-1] # save item\n", " self.itemArray[self.numItems-1] = None # disconnect it\n", " self.numItems -= 1 # one less item\n", " return temp # return item\n", "\n", " def displayNode(self):\n", " for j in range(self.numItems):\n", " self.itemArray[j].displayItem()\n", " print ''\n", "\n", "class Tree234:\n", " def __init__(self):\n", " self.root = Node() # make root node\n", "\n", " def find(self,key):\n", " curNode = self.root\n", " childNumber = 0\n", " while(True):\n", " childNumber=curNode.findItem(key) \n", " if(childNumber != -1):\n", " return childNumber # found it\n", " elif( curNode.isLeaf() ):\n", " return -1 # cant find it\n", " else: # search deeper\n", " curNode = getNextChild(curNode, key)\n", "\n", " def insert(self,dValue):\n", " curNode = self.root\n", " tempItem = DataItem(dValue)\n", " while(True):\n", " if( curNode.isFull() ):\n", " split(curNode)\n", " curNode = curNode.getParent()\n", " curNode = getNextChild(curNode, dValue)\n", " elif( curNode.isLeaf() ): # if node is leaf,\n", " break\n", " else:\n", " curNode = getNextChild(curNode, dValue)\n", " curNode.insertItem(tempItem)\n", "\n", " def split(self,thisNode): # split the node\n", " # assumes node is full\n", " itemC = thisNode.removeItem() # remove items from\n", " itemB = thisNode.removeItem() # this node\n", " child2 = thisNode.disconnectChild(2) # remove children\n", " child3 = thisNode.disconnectChild(3) # from this nodeJava Code for a 2-3-4 Tree\n", " newRight = Node() # make new node\n", " if(thisNode==self.root):\n", " self.root = Node()\n", " parent = self.root\n", " self.root.connectChild(0, thisNode)\n", " else:\n", " parent = thisNode.getParent()\n", " itemIndex = parent.insertItem(itemB) # item B to parent\n", " n = parent.getNumItems()\n", " j = n-1\n", " while j > itemIndex:\n", " temp = parent.disconnectChild(j) # one child\n", " parent.connectChild(j+1, temp)\n", " j -= 1\n", "\n", " parent.connectChild(itemIndex+1, newRight) # deal with newRight\n", " newRight.insertItem(itemC) # item C to newRight\n", " newRight.connectChild(0, child2) # connect to 0 and 1\n", " newRight.connectChild(1, child3) # on newRight\n", "\n", " def getNextChild(self,theNode,theValue):\n", " # assumes node is not empty, not full, not a leaf\n", " numItems = theNode.getNumItems() \n", " for j in range(numItems): # for each item in node\n", " if( theValue < theNode.getItem(j).dData ):\n", " return theNode.getChild(j) # return left child\n", " return theNode.getChild(j)\n", "\n", " def displayTree(self):\n", " self.recDisplayTree(self.root, 0, 0)\n", "\n", " def recDisplayTree(self,thisNode,level, childNumber):\n", " print 'level=' ,level ,' child=',childNumber , ' '\n", " thisNode.displayNode()\n", " numItems = thisNode.getNumItems()\n", " for j in range(numItems+1):\n", " nextNode = thisNode.getChild(j)\n", " if(nextNode != None):\n", " self.recDisplayTree(nextNode, level+1, j)\n", " else:\n", " return\n", "theTree = Tree234()\n", "theTree.insert(50)\n", "theTree.insert(40)\n", "theTree.insert(60)\n", "theTree.insert(30)\n", "theTree.insert(70)\n", "while(True):\n", " print 'Enter first letter of show, '\n", " print 'insert, find, or display: ',\n", " choice = raw_input()\n", " if choice == 's':\n", " theTree.displayTree()\n", " elif choice == 'i':\n", " print 'Enter value to insert: '\n", " value = int(raw_input())\n", " theTree.insert(value)\n", " elif choice == 'f':\n", " print 'Enter value to find: ',\n", " value = int(raw_input())\n", " found = theTree.find(value)\n", " if(found != -1):\n", " print 'Found: ', value\n", " else:\n", " print 'Could not find', value \n", " else:\n", " print 'Invalid entry'\n" ], "language": "python", "metadata": {}, "outputs": [] }, { "cell_type": "code", "collapsed": false, "input": [], "language": "python", "metadata": {}, "outputs": [] } ], "metadata": {} } ] }