B树
B树
"""
B树:
拥有最多子节点的节点的子节点数列称为B树的阶
B树是一颗多路查找树,满足以下条件:
1. 定义任意非叶节点最多只有M个子节点, 且 M > 2
2. 根节点的子节点数为[2, M]
3. 除根节点以外的非叶节点的子节点数为[M/2,M]
4. 每个节点存放至少M/2 - 1(向上取整)和至多M-1个数据(至少两个数据)
5. 非叶节点的数据个数=指向子节点的指针个数-1
6. 非叶节点的数据:K[1],K[2],K[3]...K[M-1] 且 K[i]<K[i-1]
7. 非叶节点的指针:P[1],P[2]...P[M] 其中P[1]指向数据小于K[1]的子树,P[M]指向数据大于K[M-1]的子树
其他P[i]指向数据属于(K[i-1],K[i])的子树
8. 所有叶节点位于同一层
"""
1. 节点作为子节点
"""
3阶B树
"""
# B树节点
class BNode():
def __init__(self, value=None):
# 左值
self.leftValue = value
# 右值
self.rightValue = None
# 左子结点
self.leftNode = None
# 中间子节点
self.midNode = None
# 右子节点
self.rightNode = None
def __str__(self):
return f'left={self.leftValue}, right={self.rightValue}'
def isLeaf(self):
"""
判断是否是叶子节点
:return:
"""
return self.leftNode is None and self.midNode is None and self.rightNode is None
def isFull(self):
"""
判断节点是否满阶
:return:
"""
return self.rightValue is not None
def getChild(self, value):
"""
根据给定的值获取子节点
:param value:
:return:
"""
# 给定的值比左值小
if value < self.leftValue:
return self.leftNode
# 给定值比右值小
elif self.rightValue is None or value < self.rightValue:
return self.midNode
# 给定值不比右值小
else:
return self.rightNode
class BTree():
def __init__(self, data_list):
self.root = None
for i in data_list:
self.put(i)
def put(self, value):
# 根节点为空
if self.root is None:
self.root = BNode(value)
else:
# 寻找添加位置
p_value, p_ref = self._put(self.root, value)
# 拆分节点操作
if p_value is not None:
new_node = BNode(p_value)
new_node.leftNode = self.root
new_node.midNode = p_ref
self.root = new_node
def _put(self, node, value):
"""
从node处开始寻找位置并插入值
:param node:
:param value:
:return:
"""
# node 是叶子节点
if node.isLeaf():
return self._addValueToNode(node, value, None)
else:
# 获取子节点
child = node.getChild(value)
p_value, p_ref = self._put(child, value)
if p_value is None:
return None, None
else:
return self._addValueToNode(node, p_value, p_ref)
def _addValueToNode(self, node, value, p_ref):
"""
将值添加到节点
:param node:
:param value:
:param p_ref:
:return:
"""
# 节点已满阶
if node.isFull():
return self._splitNode(node, value, p_ref)
else:
# 节点不是满阶 肯定没有右节点
# 给定值小于左值
if value < node.leftValue:
# 直接存入左值位置 原数据存为右值
node.rightValue = node.leftValue
node.leftValue = value
if p_ref is not None:
node.rightNode = node.midNode
node.midNode = p_ref
# 给定值存为右值
else:
node.rightValue = value
# 新节点为右子节点
if p_ref is not None:
node.rightNode = p_ref
return None, None
def _splitNode(self, node, value, p_ref):
"""
满阶后继续添加需要向上拆分
:param node:
:param value:
:param p_ref:
:return:
"""
# 初始化新节点
new_node = BNode()
# 给定值小于左值
if value < node.leftValue:
# 取出左值
p_value = node.leftValue
# 将给定值存为左值
node.leftValue = value
# 将右值给新节点
new_node.leftValue = node.rightValue
if p_ref is not None:
new_node.leftNode = node.midNode
new_node.midNode = node.rightNode
node.midNode = p_ref
# 给定值小于右值
elif value < node.rightValue:
p_value = value
new_node.leftValue = node.rightValue
if p_ref is not None:
new_node.leftNode = p_ref
new_node.midNode = node.rightNode
# 给定值大于右值
else:
p_value = node.rightValue
new_node.leftValue = value
if p_ref is not None:
new_node.leftNode = node.rightNode
new_node.midNode = p_ref
node.rightValue = None
return p_value, new_node
2. 列表作为子节点 可扩展多阶
# B树节点
class BNode():
def __init__(self, value=None):
# 左值
self.leftValue = value
# 右值
self.rightValue = None
# 左 中 右子结点
self.childNode = [None] * 3
def __str__(self):
return f'left={self.leftValue}, right={self.rightValue}'
def isLeaf(self):
"""
判断是否是叶子节点
:return:
"""
return self.childNode[0] is None and self.childNode[1] is None and self.childNode[2] is None
def isFull(self):
"""
判断节点是否满阶
:return:
"""
return self.rightValue is not None
def getChild(self, value):
"""
根据给定的值获取子节点
:param value:
:return:
"""
# 给定的值比左值小
if value < self.leftValue:
return self.childNode[0]
# 给定值比右值小
elif self.rightValue is None or value < self.rightValue:
return self.childNode[1]
# 给定值不比右值小
else:
return self.childNode[2]
class BTree():
def __init__(self, data_list):
self.root = None
for i in data_list:
self.put(i)
def put(self, value):
# 根节点为空
if self.root is None:
self.root = BNode(value)
else:
# 寻找添加位置
p_value, p_ref = self._put(self.root, value)
# 拆分节点操作
if p_value is not None:
new_node = BNode(p_value)
new_node.childNode[0] = self.root
new_node.childNode[1] = p_ref
self.root = new_node
def _put(self, node, value):
"""
从node处开始寻找位置并插入值
:param node:
:param value:
:return:
"""
# node 是叶子节点
if node.isLeaf():
return self._addValueToNode(node, value, None)
else:
# 获取子节点
child = node.getChild(value)
p_value, p_ref = self._put(child, value)
if p_value is None:
return None, None
else:
return self._addValueToNode(node, p_value, p_ref)
def _addValueToNode(self, node, value, p_ref):
"""
将值添加到节点
:param node:
:param value:
:param p_ref:
:return:
"""
# 节点已满阶
if node.isFull():
return self._splitNode(node, value, p_ref)
else:
# 节点不是满阶 肯定没有右节点
# 给定值小于左值
if value < node.leftValue:
# 直接存入左值位置 原数据存为右值
node.rightValue = node.leftValue
node.leftValue = value
if p_ref is not None:
node.childNode[2] = node.childNode[1]
node.childNode[1] = p_ref
# 给定值存为右值
else:
node.rightValue = value
# 新节点为右子节点
if p_ref is not None:
node.childNode[2] = p_ref
return None, None
def _splitNode(self, node, value, p_ref):
"""
满阶后继续添加需要向上拆分
:param node:
:param value:
:param p_ref:
:return:
"""
# 初始化新节点
new_node = BNode()
# 给定值小于左值
if value < node.leftValue:
# 取出左值
p_value = node.leftValue
# 将给定值存为左值
node.leftValue = value
# 将右值给新节点
new_node.leftValue = node.rightValue
if p_ref is not None:
new_node.childNode[0] = node.childNode[1]
new_node.childNode[1] = node.childNode[2]
node.childNode[1] = p_ref
# 给定值小于右值
elif value < node.rightValue:
p_value = value
new_node.leftValue = node.rightValue
if p_ref is not None:
new_node.childNode[0] = p_ref
new_node.childNode[1] = node.childNode[2]
# 给定值大于右值
else:
p_value = node.rightValue
new_node.leftValue = value
if p_ref is not None:
new_node.childNode[0] = node.childNode[2]
new_node.childNode[1] = p_ref
node.rightValue = None
return p_value, new_node
# 递归遍历 先遍历根左边层级 再遍历根右边层级
def traverse_b_tree(self, node, level=0):
# 打印当前节点及其层级
print('Level {}: {}'.format(level, node))
# 遍历所有孩子并递归
for child in node.childNode:
if child is not None:
self.traverse_b_tree(child, level + 1)
if __name__ == '__main__':
data_list = [7, 6, 2, 4, 8, 9, 1, 3, 5]
bt = BTree(data_list)
bt.traverse_b_tree(bt.root)
控制台输出
Level 0: left=6, right=None
Level 1: left=2, right=4
Level 2: left=1, right=None
Level 2: left=3, right=None
Level 2: left=5, right=None
Level 1: left=8, right=None
Level 2: left=7, right=None
Level 2: left=9, right=None