Axel PERCIBALLI Python B+Tree

#!/usr/bin/env python
#-*- coding:UTF-8-*-
import sys

class Item:
    def __init__(self, key, value):
        self.key=key
        self.value=value


class Node:
    def __init__(self, parent=None, nextNode=None):
        self.parent   = parent
        self.children = []
        self.keys     = []
        self.values   = []
        self.nextNode = nextNode


    def add(self,item):
        if (not self.children) : # Leaf
            if (len(self.keys)<3): # Hardcoded to look like the one in the example
                self.keys.append(item.key)
                self.keys.sort()
                self.values.insert(self.keys.index(item.key),item.value) #inserting the value at same index as key

            else:
                #LEAF SPLIT
                newparentnode=Node()
                if (not self.parent): #case where leaf is root

                    if (self.keys[2]<item.key): #if our item has a smaller key than the biggest key of the node
                        newparentnode.keys=[self.keys[2]] #[1,5,8] + 9 becomes [1,5] [8,9]
                        print "New node created with node key :",self.keys[2]

                        newchildrennode=Node(newparentnode) # creating following children node
                        newchildrennode.keys=[self.keys[2],item.key]
                        newchildrennode.values=[self.values[2],item.value]


                    else: # if our item has a bigger key than the node's biggest key
                        newparentnode.keys=[item.key]
                        print "New node created with node key :",item.key

                        newchildrennode=Node(newparentnode)
                        newchildrennode.keys=[item.key,self.keys[2]]
                        newchildrennode.values=[item.value,self.values[2]]
                    self.parent=newparentnode
                    newchildrennode.parent=newparentnode
                    newparentnode.children=[self,newchildrennode]
                    self.values.pop() # removing last value of the node
                    self.keys.pop() #removing last key of the node
                    self.nextNode=newchildrennode
                    t.root=newparentnode

                else: #case where leaf is not root

                    #preparing the two new nodes
                    if (self.keys[2]<item.key):
                        newchildrennode=Node(newparentnode) # creating following children node
                        newchildrennode.keys=[self.keys[2],item.key]
                        newchildrennode.values=[self.values[2],item.value]
                    else:
                        newchildrennode=Node(newparentnode)
                        newchildrennode.keys=[item.key,self.keys[2]]
                        newchildrennode.values=[item.value,self.values[2]]

                    #if former node parent is not full
                    if (len(self.parent.keys)<3):
                        newchildrennode.parent=self.parent
                        self.parent.children.append(newchildrennode)
                        self.parent.keys.append(newchildrennode.keys[0])
                        self.values.pop() # removing last value of the node
                        self.keys.pop() #removing last key of the node
                        self.nextNode=newchildrennode

                    #if former node parent is full, we create a new node and attach it to the previous parent's parent
                    else:
                        newchildrennode.parent=Node()
                        newchildrennode.parent.keys=[self.key]
                        newchildrennode.parent.children=newchildrennode
                        self.values.pop() # removing last value of the node
                        self.keys.pop() #removing last key of the node
                        self.nextNode=newchildrennode
                        self.parent.add(newchildrennode.parent)#recursive split the level above



        else: #not a leaf

            for child in self.keys:
                if item.key<child: #if we're behind an item with a bigger key than ours
                    self.children[self.keys.index(child)].add(item)
                    return 0

            self.children[len(self.children)-1].add(item) # if our item has a bigger key than the biggest of the node

        return 0


    def search(self,key):

        if (not self.children): #leaf node
            for x in self.keys:
                if (key==x):
                    return self.values[self.keys.index(x)]
        else: #not leaf nodes
            for x in self.keys:
                if (key<x):
                    return self.children[self.keys.index(x)].search(key) #terminal recursivity
                return self.children[len(self.keys)].search(key)


    def printnode(self):
        toprint=""
        if (not self.children): #leaf
            for key in self.keys:
                return str((key,self.values[self.keys.index(key)]))
        else:
            for children in self.children:
                toprint += "\n\t A child with keys :"

                for key in children.keys:
                    toprint+=str(key)+" "
        return "Root has the key(s) : "+str(t.root.keys)+toprint #Not done yet


class Tree:
    def __init__(self):
        self.root = None # We init the tree with an empty node
        print "Empty tree created"

    def insert(self, item):
        if (not self.root): # First node inserted in tree
            self.root=Node()
            self.root.add(item)
            print "Added root node to tree"
        else:
            self.root.add(item)

    def search(self,key):
        if (not self.root):
            print "You need to add an item first."
            return -1
        else:
            return self.root.search(key)

    def printree(self):
        print "\n \nCalling print tree method "
        print(self.root.printnode())



print("\n\n")
t=Tree()
i=Item(1,(1,2))
i2=Item(2,(3,4))
i3=Item(4,(5,6))
i4=Item(5,(7,8))
i5=Item(6,(9,10))
i6=Item(3,(11,12))
i7=Item(7,(13,14))
i8=Item(8,(15,16))
i9=Item(9,(17,18))
i10=Item(10,(19,20))
i11=Item(11,(21,22))

t.insert(i)
#t.printree()

t.insert(i2)
#t.printree()

t.insert(i3)
#t.printree()

t.insert(i4)
#t.printree()

t.insert(i5)
#t.printree()

t.insert(i6)
#t.printree()

t.insert(i7)
#t.printree()

t.insert(i8)
#t.printree()

t.insert(i9)
#t.printree()

t.insert(i10)
t.printree()

#Non-leaf node split has some issues
#t.insert(i11)
#t.printree()

print("\n")
print("Item with key 1 has the values : "+str(t.search(1)))
print("Item with key 8 has the values : "+str(t.search(8)))
print("Item with key 10 has the values : "+str(t.search(10)))

print "\nProgram ending.\n"