1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
{
"metadata": {
"name": "ch10"
},
"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": "'''\nexample 10.1\ndemonstrates 234 tree\n'''\nclass DataItem:\n def __init__(self,dd):\n self.dData = dd\n\n def displayItem(self):\n print '/' ,self.dData\n\nclass 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\nclass 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\ntheTree = Tree234()\ntheTree.insert(50)\ntheTree.insert(40)\ntheTree.insert(60)\ntheTree.insert(30)\ntheTree.insert(70)\nwhile(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": [],
"prompt_number": "*"
},
{
"cell_type": "code",
"collapsed": false,
"input": "",
"language": "python",
"metadata": {},
"outputs": []
}
],
"metadata": {}
}
]
}
|
