# Implementation of B-trees

import matplotlib.pyplot as plt import numpy as np

class BTree: # Constructor def __init__(self, max_items = 5): self.data = [] self.child = [] self.max_items = max_items

def find_subtree(self, k): # Determines value of c (an integer), such that if k is in the BTree, it must be in subtree self.child[c] for c in range(len(self.data)): if self.data[c]>k: return c return len(self.data)

def is_full(self): return len(self.data) >= self.max_items

def extend(self,L): for item in L: self.insert(item)

def insert(self, i, parent=None): if self.is_full(): m, right_child = self.split() if parent==None: # Spliting the root left_child = BTree(self.max_items) left_child.data = self.data left_child.child = self.child self.data = [m] self.child = [left_child, right_child] if i

def split(self): mid = self.max_items // 2 m = self.data[mid] right_side = BTree(self.max_items) right_side.data = self.data[mid + 1:] right_side.child = self.child[mid + 1:] self.data = self.data[:mid] self.child = self.child[:mid+1] return m, right_side

def _leaves(self): if len(self.child)==0: return [self.data] s = [] for c in self.child: s = s + c._leaves() return s

def _set_x(self, dx): if len(self.child)>0: for c in self.child: c._set_x(dx) d = (dx[self.child[0].data[0]] + dx[self.child[-1].data[0]] + 10 * len(self.child[-1].data)) / 2 dx[self.data[0]] = d - 10 * len(self.data) / 2

def draw_(self, dx, y, y_inc, fs, ax): # Function to display b-tree to the screen # It works fine for trees with up to about 70 data items xs = dx[self.data[0]] if len(self.child)==0: for itm in self.data: ax.plot([xs, xs + 10, xs + 10, xs, xs], [y, y, y - 10, y - 10, y], linewidth=1, color='k') ax.text(xs + 5, y - 5, str(itm), ha="center", va="center", fontsize=fs) xs += 10 else: for i,d in enumerate(self.data): xc = dx[self.child[i].data[0]] + 5 * len(self.child[i].data) ax.plot([xs, xs + 10, xs + 10, xs, xs], [y, y, y - 10, y - 10, y], linewidth=1, color='k') ax.text(xs + 5, y - 5, str(d), ha="center", va="center", fontsize=fs) ax.plot([xs, xc], [y - 10, y - y_inc], linewidth=1, color='k') self.child[i].draw_(dx, y - y_inc, y_inc, fs, ax) xs += 10 xc = dx[self.child[-1].data[0]] + 5 * len(self.child[-1].data) ax.plot([xs, xc], [y - 10, y - y_inc], linewidth=1, color='k') self.child[-1].draw_(dx, y - y_inc, y_inc, fs, ax)

def draw(self,title=''): # Find x-coordinates of leaves ll = self._leaves() dx = {} d = 0 for l in ll: dx[l[0]] = d d += 10 * (len(l) + 1) # Find x-coordinates of internal nodes self._set_x(dx) fig, ax = plt.subplots() if len(self.child)==0: c = len(self.data)*5 ax.plot([-80+c,80+c],[-25,-70],linewidth=1,color='w') fs = max(8, 15-5*self.height()) max_x = dx[ll[-1][0]] self.draw_(dx, -30, 30, fs, ax) ax.set_aspect(1.0) ax.axis('off') ax.set_title(title) plt.tight_layout() plt.show()

def print_tree(self,space=''): print(space,self.data) for c in self.child: c.print_tree(space+' ')

def height(self): if len(self.child)==0: return 0 return 1+self.child[0].height()

def find(self, k): if k in self.data: return self if len(self.child)==0: return None return self.child[self.find_subtree(k)].find(k)

def from_list(L): T = BTree() T.extend(L) return T

Write the function in_leaf_vO(T,k) that determines if integer k is in a leaf node in B-tree T. Use the find function in the BTree class. Write the recursive function in_leaf (T,k) that determines if integer k is in a leaf node in B-tree T. You may not use the find function; however, the find_subtree function may be useful. Write the recursive function num_nodes (T) that returns the number of nodes in B-tree T. Write the recursive function num_items(T) that returns the number of items stored in B-tree T. Write the recursive function full_nodes (T) that returns the nodes in B-tree T that are full (that is, their data attribute has length T.max_items) Write the function num_leaves(T) that returns the number of leaf nodes in B-tree T. Write the function find_depth (T,k) that receives a reference to the root of a B-tree T and an item k and returns the depth of the node where k is found in the tree, or 1 if k is not in the tree. Write the function print_descending (T) that prints all the items in B-tree T in descending order