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