Forked from
Chaabane Djeraba / Projet - L3 - S6
32 commits ahead of the upstream repository.
-
Mamadu-lamarana Bah authoredMamadu-lamarana Bah authored
Node.py 9.02 KiB
from util import recherche_dichotomique
#from Visualization import *
#from BTree import *
class Node() :
def __init__(self, keys, childs = []) :
self.keys = keys
self.childs = childs
def isLeaf(self):
"""
>>> Node([12, 42]).isLeaf()
True
>>> Node([12, 42], [Node([1]), Node([25]), Node([50])]).isLeaf()
False
"""
return (len(self.childs) == 0)
def getSize(self) :
return len(self.keys)
def search(self, value):
"""
Exemple(s):
>>> Node([5,25]).search(5)
(Node([5, 25]), 0)
>>> Node([12, 42]).search(12)
(Node([12, 42]), 0)
>>> Node([12, 42]).search(1)
>>> Node([12, 42], [Node([1]), Node([25]), Node([50])]).search(1)
(Node([1]), 0)
>>> Node([12, 42], [Node([1]), Node([25]), Node([50])]).search(2)
"""
(found, index) = recherche_dichotomique(value, self.keys)
if (found):
return (self, index)
elif ( self.isLeaf() ):
return None
else :
return self.childs[index].search(value)
def is_ArbreB(self, k, is_root = False):
"""
Verification de l'équilibrage de l'arbre
Params :
k => number of keys in node
Return :
(ok, height, mini, maxi)
Exemple(s) :
>>> Node([5]).is_ArbreB(2)
(True, 0, 5, 5)
>>> Node([5,25]).is_ArbreB(2)
(True, 0, 5, 25)
>>> node = Node([12, 42], [Node([2, 4], [Node([0, 1]), Node([3]), Node([7, 8])]), Node([25]), Node([50])])
>>> node.is_ArbreB(2)
(False, 2, 0, 50)
>>> Node([5,25,3]).is_ArbreB(2)
(False, 0, 5, 3)
>>> Node([5, 25], [Node([0, 1, 2]), Node([3, 2, 5])]).is_ArbreB(2)
(False, 1, 0, 5)
>>> Node([5], [Node([0]), Node([7], [Node([6]), Node([8])])]).is_ArbreB(2)
(False, 2, 0, 8)
>>> Node([12,25,50], [Node([1,11]), Node([20]), Node([30]), Node([100])]).is_ArbreB(3)
(True, 1, 1, 100)
"""
ok = (is_root or (k//2) <= len(self.keys)) and len(self.keys) <= k
ok = ok and all(self.keys[i] < self.keys[i+1] for i in range(len(self.keys) - 1))
if (self.isLeaf()):
height = 0
mini, maxi = self.keys[0], self.keys[-1]
else:
results = [child.is_ArbreB( k, False ) for child in self.childs]
mins = [mini for (_, _, mini, _) in results]
maxs = [maxi for (_, _, _, maxi) in results]
ok = ok and all(self.keys[i] > maxs[i] and self.keys[i] < mins[i+1] for i in range(len(self.keys) - 1))
heights = [h for (_, h, _, _) in results]
ok = ok and all(heights[i] == heights[i+1] for i in range(len(heights)-1))
height = 1 + max(heights)
mini = min(mins)
maxi = max(maxs)
return (ok, height, mini, maxi)
def insert(self, value, k):
"""
Return : (node, index) or Nothing
Exemple(s):
>>> node = Node([])
>>> node.insert(5,1)
(True, None, None, None)
>>> node.insert(20, 2)
(True, None, None, None)
>>> node.search(20)
(Node([5, 20]), 1)
>>> Node([5,15]).insert(12, 2)
(False, 12, Node([5]), Node([15]))
>>> node.search(12)
>>> node = Node([12, 42], [Node([3]), Node([25]), Node([50])])
>>> node.insert(52, 2)
(True, None, None, None)
>>> node.search(52)
(Node([50, 52]), 1)
>>> node = Node([12, 42], [Node([2, 3]), Node([25]), Node([50])])
>>> node.insert(1, 2)
(False, 12, Node([2], [Node([1]), Node([3])]), Node([42], [Node([25]), Node([50])]))
>>> node.search(1)
(Node([1]), 0)
>>> node = Node([12, 42], [Node([2, 4], [Node([0, 1]), Node([3]), Node([7, 8])]), Node([25]), Node([50])])
>>> node.insert(6, 2)
(False, 12, Node([4], [Node([2], [Node([0, 1]), Node([3])]), Node([7], [Node([6]), Node([8])])]), Node([42], [Node([25]), Node([50])]))
>>> node = Node([12, 42], [Node([2, 3, 4]), Node([25]), Node([50])])
>>> node.insert(1, 3)
(True, None, None, None)
"""
(found, index) = recherche_dichotomique(value, self.keys)
if (not found) :
if (self.isLeaf()):
self.keys.insert(index, value)
if ( len(self.keys) > k):
milieu, g, d = self.splitNode()
return False, milieu, g, d
return True, None, None, None
else:
(fini, milieu, g, d) = self.childs[index].insert(value, k)
if (not fini) :
self.keys.insert(index, milieu)
self.childs[index] = g
self.childs.insert(index+1, d)
if ( len(self.keys) > k) :
milieu, g, d = self.splitNode()
return False, milieu, g, d
else:
return True, None, None, None
else :
return True, None, None, None
else :
return True, None, None, None
def suppression(self, value, k, is_root=False) :
"""
Exemple(s):
>>> node = Node([42], [Node([14]), Node([50])])
>>> node.suppression(14, 2)
True
>>> node
Node([12, 42], [Node([3, 4]), Node([25, 26]), Node([58])])
"""
(found, index) = recherche_dichotomique(value, self.keys)
if (self.isLeaf()) :
removed = self.keys.pop(index)
ok = is_root or k//2 <= len(self.keys)
else:
(ok) = self.childs[index].suppression(value, k, False)
if (not ok):
# left sibling lookup
if(index - 1 >= 0 and (len(self.childs[index-1].keys) - 1 >= k//2)):
borrowed = self.childs[index-1].keys.pop()
replaced = self.keys.pop(index-1)
self.keys.insert(index-1, borrowed)
self.childs[index].keys.insert(index-1, replaced) #
# right sibling lookup
elif(index + 1 < len(self.childs) and (len(self.childs[index+1].keys) - 1 >= k//2)):
borrowed = self.childs[index+1].keys.pop(index-1)
replaced = self.keys.pop()
self.keys.insert(len(self.keys), borrowed)
self.childs[index].keys.insert(len(self.childs[index].keys), replaced) # len(self.childs)
# when deletion of the key violates the property of the minimum number of keys
# merge
else:
# right sibling lookup
if(index-1 >= 0):
replaced = self.keys.pop(index-1)
borrowed = self.childs[index-1].keys.pop()
self.childs[index].keys.insert(len(self.childs[index].keys), replaced)
self.childs[index].keys.insert(index-1, borrowed)
del self.childs[index-1]
# left sibling lookup
elif(index + 1 < len(self.childs)):
print("icic")
replaced = self.keys.pop(index)
borrowed = self.childs[index+1].keys.pop()
self.childs[index].keys.insert(index, replaced)
self.childs[index].keys.insert(len(self.childs[index].keys), borrowed)
del self.childs[index+1]
ok = not ok
return ok
def splitNode(self) :
"""
>>> Node([10,20,25]).splitNode()
(20, Node([10]), Node([25]))
>>> Node([12, 20, 22, 40]).splitNode()
(22, Node([12, 20]), Node([40]))
>>> Node([3, 5]).splitNode()
(5, Node([3]), Node([]))
"""
milieu = len(self.keys) //2
g = Node(self.keys[:milieu], self.childs[:milieu+1])
d = Node(self.keys[milieu+1:], self.childs[milieu+1:])
return (self.keys[milieu], g, d)
def linearisation(self):
"""
Exemple(s):
>>> Node([12, 42], [Node([2, 3]), Node([13, 15]), Node([45])]).linearisation()
[2, 3, 12, 13, 15, 42, 45]
>>> Node([12, 42], [Node([2, 3]), Node([25]), Node([50])]).linearisation()
[2, 3, 12, 25, 42, 50]
"""
if (self.isLeaf()):
res = self.keys
else:
res = []
for i in range(0, len(self.keys)):
res.extend(self.childs[i].linearisation())
res.append(self.keys[i])
res.extend(self.childs[len(self.childs)-1].linearisation())
return res
def __repr__(self) :
return (f"Node({self.keys}"
+ (f", {self.childs})" if len(self.childs) > 0 else ")"))
if __name__ == '__main__':
import doctest
doctest.testmod(verbose=False)