B樹(或稱B-樹)是一種適用于外查找的樹，它是一種平衡的多叉樹。
階為M的B樹具有下列結構特征：
1.樹的根或者是一片樹葉，或者其兒子數在2和M之間。
2.除根節點外的所有非樹葉節點兒子數在┌M/2┐和 M之間。
3.所有的樹葉都在相同的高度。
4.節點中包括n個關鍵字，n+1個指針，一般形式為： （n,P0,K1,P1,K2,P2,…,Kn,Pn）。每個結點中關鍵字從小到大排列，并且當該結點的孩子是非葉子結點時，該k-1個關鍵字正好是k個兒子包含的關鍵字的值域的分劃。
對于任意一顆包含n個關鍵字的M階B樹，高度h滿足：
h≤log┌m/2┐((N+1)/2 )+1
當B樹的分支因子很大時，可以大大降低樹的高度，B樹的查找效率非常之高。
搜索B樹與搜索二叉查找樹的操作很類似，只是在每個節點所做的不是個二叉分支決定，而是根據該節點的子女數所做的多路分支決定。
1.向未滿的節點插入關鍵字
2.向已滿的節點添加關鍵字，需要將節點分裂為兩個節點：
分裂一個節點有三種情況：
A：父節點未滿
有兩種情況，分裂leftchild與分裂middlechild：
B：父節點已滿，需要將父節點分裂
有三種情況：
最后，特殊情況，產生新的根：
代碼：
class Node(object): def __init__(self,key): self.key1=key self.key2=None self.left=None self.middle=None self.right=None def isLeaf(self): return self.left is None and self.middle is None and self.right is None def isFull(self): return self.key2 is not None def hasKey(self,key): if (self.key1==key) or (self.key2 is not None and self.key2==key): return True else: return False def getChild(self,key): if key<self.key1: return self.left elif self.key2 is None: return self.middle elif key<self.key2: return self.middle else: return self.rightclass 2_3_Tree(object): def __init__(self): self.root=None def get(self,key): if self.root is None: return None else: return self._get(self.root,key) def _get(self,node,key): if node is None: return None elif node.hasKey(key): return node else: child=node.getChild(key) return self._get(child,key) def put(self,key): if self.root is None: self.root=Node(key) else: pKey,PRef=self._put(self.root,key) if pKey is not None: newnode=Node(pKey) newnode.left=self.root newnode.middle=pRef self.root=newnode def _put(self,node,key): if node.hasKey(key): return None,None elif node.isLeaf(): return self._addtoNode(node,key,None) else: child=node.getChild(key) pKey,pRef=self._put(child,key) if pKey is None: return None,None else: return self._addtoNode(node,pKey,pRef) def _addtoNode(self,node,key,pRef): if node.isFull(): return self._splitNode(node,key,pRef) else: if key<node.key1: node.key2=node.key1 node.key1=key if pRef is not None: node.right=node.middle node.middle=pRef else: node.key2=key if pRef is not None: node.right=Pref return None,None def _splitNode(self,node,key,pRef): newnode=Node(None) if key<node.key1: pKey=node.key1 node.key1=key newnode.key1=node.key2 if pRef is not None: newnode.left=node.middle newnode.middle=node.right node.middle=pRef elif key<node.key2: pKey=key newnode.key1=node.key2 if pRef is not None: newnode.left=Pref newnode.middle=node.right else: pKey=node.key2 newnode.key1=key if pRef is not None: newnode.left=node.right newnode.middle=pRef node.key2=None return pKey,newnode
新聞熱點
疑難解答
