目录标题
二叉排序树 Binary Sort Tree
- 二叉查找树，也称二叉搜索树
- 性质
- 或是一棵空树
- 如果左子树不为空，则左子树上所有结点的值均小于它根结点的值
- 如果右子树不为空，则右子树上所有结点的值均大于它根结点的值
- 左右子树也都为二叉排序树
- 树中没有值相同的结点
- 二叉排序树的示意图
二叉排序树的插入
基本思想：已知一关键字为key的结点node
-
- 若二叉树为空树，则结点node成为二叉排序树的根
-
- 若二叉树非空树，则将node.key与二叉排序树根结点的关键字进行比较
- 如果key的值等于根结点的值，则停止插入
- 如果key的值小于根结点的值，则将结点node插入左子树
- 如果key的值大于根结点的值，则将结点node插入右子树
-
二叉排序树的插入操作
二叉排序树的插入代码
def insert(self, key):
"""
插入新结点
:param key: 待插入元素
:return:
"""
node = Node(key)
# 如果二叉排序树为空树
if self.root == None:
self.root = node
# 如果二叉树不为空树
else:
# 创建一个指针指向根结点
cur = self.root
# cur不为空
while cur != None:
# 判断key与cur.val的大小
if key > cur.val:
# 在右子树中插入新结点
if cur.right == None:
cur.right = node
break
cur = cur.right
else:
# 在左子树插入新结点
if cur.left == None:
cur.left = node
break
cur = cur.left
二叉树排序树的删除
核心操作：
- 删除结点不在二叉排序树中，则不做任何操作
- 否则，假设需要删除的结点为key，key的双亲结点为keyParent，假设key为keyParent的左孩子结点
- 1.若key为叶子结点，则直接删除
- 2.若key只有左子树，可将key的左子树直接改为其双亲结点keyParent的左子树
- 若key有左右子树
- 找到key在中序序列中的前驱结点pre
- 将key的左子树改为结点keyParent的左子树
- 将key的右子树改为中序序列中的前驱结点pre的右子树
- 二叉排序树的删除操作
- 二叉排序树的删除代码
def delete(self, key):
"""
二叉排序树的删除
:param key: 删除的元素值
:return:
"""
if self.root is None:
return
# target指向根结点
target = self.root
# targetParent指向target的双亲结点
targetParent = None
# 从树根开始逐层向下查找待删除的数值为key的结点
while target and target.val != key:
targetParent = target
# 找到对应结点则退出循环
# 在左子树中继续查找
if key < target.val:
target = target.left
else:
# 在右子树中继续查找
target = target.right
if target is None: # 未找到节点
return
# 情况1：目标节点是叶子节点
if target.left is None and target.right is None:
if targetParent is None: # 根节点
self.root = None
elif targetParent.left == target:
targetParent.left = None
else:
targetParent.right = None
# 情况2：目标节点是单分支节点
elif target.left is None or target.right is None:
child = target.left if target.left else target.right
if targetParent is None: # 根节点
self.root = child
elif targetParent.left == target:
targetParent.left = child
else:
targetParent.right = child
# 情况3：目标节点是双分支节点
else:
# 找到左子树的最大节点（中序前驱）
predecessor_parent = target
predecessor = target.left
while predecessor.right:
predecessor_parent = predecessor
predecessor = predecessor.right
# 用前驱节点的值替换目标节点值
target.val = predecessor.val
# 删除前驱节点（前驱节点无右子树）
if predecessor_parent.left == predecessor:
predecessor_parent.left = predecessor.left
else:
predecessor_parent.right = predecessor.left
二叉排序树的查找
基本思想：将待查关键字key与根结点关键字val进行比较
- key == val，则返回根结点地址
- key < val，则进一步查找左子树
- key > val，则进一步查找右子树
二叉排序树的平均查找长度ASL在最好的情况下为 O ( l o g 2 n ) O(log_2 n) O(log2n)
二叉排序树的查找操作
二叉排序树的代码
def contains(self, key):
"""
查找
:param key:
:return:
"""
if self.root == None:
return False
cur = self.root
while cur != None:
#如果key等于cur指针指向的结点数值
if key == cur.val:
return True
# 如果大于其数值
elif key > cur.val:
# 将cur指针指向的结点的右孩子结点
cur = cur.right
else:
# 否则指向左孩子结点
cur = cur.left
# 查找失败的情况
return False
二叉排序树的调试与代码集合
class Node(object):
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BinarySortTree(object):
def __init__(self):
self.root = None
def insert(self, key):
"""
插入新结点
:param key: 待插入元素
:return:
"""
node = Node(key)
# 如果二叉排序树为空树
if self.root == None:
self.root = node
# 如果二叉树不为空树
else:
# 创建一个指针指向根结点
cur = self.root
# cur不为空
while cur != None:
# 判断key与cur.val的大小
if key > cur.val:
# 在右子树中插入新结点
if cur.right == None:
cur.right = node
break
cur = cur.right
else:
# 在左子树插入新结点
if cur.left == None:
cur.left = node
break
cur = cur.left
def getMinNode(self, node):
"""
获取二叉排序树中的数值最小结点
:param node: 根结点
:return:
"""
# 如果根结点的左子树为空，因此根结点数值最小
if node.left == None:
return node.val
# 如果根结点的左子树不为空，数值最小的结点一定在根结点的左子树
# 用指针cur指向根结点的左孩子结点
cur = node.left
while cur.left != None:
cur = cur.left
# 如果当前结点的左子树为空，则当前结点数值为最小值
return cur.val
def getMaxNode(self, node):
"""
获取二叉排序树中数值最大的结点
:param node: 根结点
:return:
"""
# 如果根结点的右子树为空树，则根结点数值最大
if node.right == None:
return node.val
# 如果根结点的右子树不为空树，数值最大的结点一定在根结点的右子树
# 用指针cur指向根结点的右孩子结点
cur = node.right
while cur.right != None:
cur = cur.right
# 如果当前结点的右子树为空树，则当前结点数值为最大值
return cur.val
def preorder_iterator(self,node):
"""
先序遍历
:param node: 二叉顺序树的根结点
:return:
"""
if node != None:
print(node.val, end=" ")
self.preorder_iterator(node.left)
self.preorder_iterator(node.right)
def inorder_iterator(self, node):
"""
中序遍历
:param node: 二叉树的根结点
:return:
"""
if node != None:
self.inorder_iterator(node.left)
print(node.val, end=" ")
self.inorder_iterator(node.right)
def postorder_iterator(self, node):
"""
后序遍历
:param node: 二叉树的根结点
:return:
"""
if node != None:
self.postorder_iterator(node.left)
self.postorder_iterator(node.right)
print(node.val, end=" ")
def delete(self, key):
"""
二叉排序树的删除
:param key: 删除的元素值
:return:
"""
if self.root is None:
return
# target指向根结点
target = self.root
# targetParent指向target的双亲结点
targetParent = None
# 从树根开始逐层向下查找待删除的数值为key的结点
while target and target.val != key:
targetParent = target
# 找到对应结点则退出循环
# 在左子树中继续查找
if key < target.val:
target = target.left
else:
# 在右子树中继续查找
target = target.right
if target is None: # 未找到节点
return
# 情况1：目标节点是叶子节点
if target.left is None and target.right is None:
if targetParent is None: # 根节点
self.root = None
elif targetParent.left == target:
targetParent.left = None
else:
targetParent.right = None
# 情况2：目标节点是单分支节点
elif target.left is None or target.right is None:
child = target.left if target.left else target.right
if targetParent is None: # 根节点
self.root = child
elif targetParent.left == target:
targetParent.left = child
else:
targetParent.right = child
# 情况3：目标节点是双分支节点
else:
# 找到左子树的最大节点（中序前驱）
predecessor_parent = target
predecessor = target.left
while predecessor.right:
predecessor_parent = predecessor
predecessor = predecessor.right
# 用前驱节点的值替换目标节点值
target.val = predecessor.val
# 删除前驱节点（前驱节点无右子树）
if predecessor_parent.left == predecessor:
predecessor_parent.left = predecessor.left
else:
predecessor_parent.right = predecessor.left
def contains(self, key):
"""
查找
:param key:
:return:
"""
if self.root == None:
return False
cur = self.root
while cur != None:
#如果key等于cur指针指向的结点数值
if key == cur.val:
return True
# 如果大于其数值
elif key > cur.val:
# 将cur指针指向的结点的右孩子结点
cur = cur.right
else:
# 否则指向左孩子结点
cur = cur.left
# 查找失败的情况
return False
if __name__ == "__main__":
print('PyCharm')
bstree = BinarySortTree()
temp = [53, 78, 65, 17, 87, 9, 81, 15]
# 插入结点
for i in temp:
bstree.insert(i)
# 删除操作
bstree.delete(17)
# 查找操作
num = 77
print(f"查找的元素：{num}在二叉树中的查找情况为{bstree.contains(num)}")
print("先序遍历:", end="")
bstree.preorder_iterator(bstree.root)
print()
print("中序遍历:", end="")
bstree.inorder_iterator(bstree.root)
print()
print("后序遍历:", end="")
bstree.postorder_iterator(bstree.root)
print()
min_num = bstree.getMinNode(bstree.root)
print('二叉排序树的最小结点值为:', min_num)
max_num = bstree.getMaxNode(bstree.root)
print("二叉排序树的最大结点值为:", max_num)
平衡二叉树-AV树
- 满足任何一个结点的左子树和右子树的高度差的绝对值不超过1的二叉排序树.
- 性质
- 或是一棵空树
- 左子树与右子树的高度差的绝对值小于或等于1；
- 左子树和右子树也都是平衡树
- 1.有n个结点的平衡二叉树的高度为 l o g 2 n log_2 n log2n
- 2.在有n个结点的平衡二叉树中搜索一个结点的时间复杂度为 O ( l o g 2 n ) O(log_2 n) O(log2n)
- 3.将一个新结点插入一棵有n个结点的平衡二叉树中，可得到一棵有n+1个结点的平衡二叉树，且插入的时间复杂度 O ( l o g 2 n ) O(log_2 n) O(log2n)
- 4.从一棵有n个结点的平衡二叉树删除一个结点，可得到一棵有n-1个结点的平衡二叉树，且删除的时间复杂度为 O ( l o g 2 n ) O(log_2 n) O(log2n)
- 5.结点的平衡因子BF：定义为结点左子树与右子树高度之差；在平衡二叉树中任一结点的BF值只能是-1,0，和1.
平衡二叉树的平衡化旋转
- 平衡二叉树的创建
- 若在平衡二叉树中插入一个新结点，则会造成不平衡，需要进行平衡化旋转.
- 平衡化旋转
- 单旋转(LL旋转和RR旋转)
- 双旋转(LR旋转和RL旋转)
- LL：用于处理左子树的左子树过高
- RR：用于处理左子树的左子树过高
- LR：用于处理左子树的右子树过高
- RL：用于处理右子树的左子树过高
平衡二叉树的代码调试与代码集合
class Node(object):
def __init__(self, data):
self.data = data
self.left = None
self.right = None
self.height = 1 # 初始高度为1（叶子节点）
class AVLTree(object):
def __init__(self):
self.root = None
def height(self, node):
if node is None:
return 0
return node.height
def update_height(self, node):
"""更新节点高度"""
node.height = max(self.height(node.left), self.height(node.right)) + 1
def balance_factor(self, node):
"""计算平衡因子"""
if node is None:
return 0
return self.height(node.left) - self.height(node.right)
def is_balance(self, node):
"""验证AVL树是否平衡"""
if node is None:
return True
left_height = self.height(node.left)
right_height = self.height(node.right)
if abs(left_height - right_height) > 1:
return False
return self.is_balance(node.left) and self.is_balance(node.right)
# ---------------------- 遍历方法 ----------------------
def preorder_iterator(self, node):
if node is not None:
print(node.data, end=" ")
self.preorder_iterator(node.left)
self.preorder_iterator(node.right)
def inorder_iterator(self, node):
if node is not None:
self.inorder_iterator(node.left)
print(node.data, end=" ")
self.inorder_iterator(node.right)
def postorder_iterator(self, node):
if node is not None:
self.postorder_iterator(node.left)
self.postorder_iterator(node.right)
print(node.data, end=" ")
def LL(self, node):
"""左左旋转（右旋）"""
new_root = node.left
node.left = new_root.right
new_root.right = node
self.update_height(node)
self.update_height(new_root)
return new_root
def RR(self, node):
"""右右旋转（左旋）"""
new_root = node.right
node.right = new_root.left
new_root.left = node
self.update_height(node)
self.update_height(new_root)
return new_root
def LR(self, node):
"""左右旋转（先左旋后右旋）"""
node.left = self.RR(node.left)
return self.LL(node)
def RL(self, node):
"""右左旋转（先右旋后左旋）"""
node.right = self.LL(node.right)
return self.RR(node)
def find_min(self, node):
"""查找最小节点"""
if node is None or node.left is None:
return node
return self.find_min(node.left)
def insert(self, data, node):
"""插入节点并平衡"""
if node is None:
return Node(data)
if data < node.data:
node.left = self.insert(data, node.left)
elif data > node.data:
node.right = self.insert(data, node.right)
else:
return node # 重复值不插入
# 更新高度
self.update_height(node)
# 检查平衡因子
balance = self.balance_factor(node)
# 左子树不平衡
if balance > 1:
if self.balance_factor(node.left) >= 0: # 左左型
return self.LL(node)
else: # 左右型
return self.LR(node)
# 右子树不平衡
if balance < -1:
if self.balance_factor(node.right) <= 0: # 右右型
return self.RR(node)
else: # 右左型
return self.RL(node)
return node
def remove(self, data, node):
"""删除节点并平衡"""
if node is None:
return None
if data < node.data:
node.left = self.remove(data, node.left)
elif data > node.data:
node.right = self.remove(data, node.right)
else:
# 找到目标节点
if node.left is None or node.right is None:
# 单分支或叶子节点
child = node.left if node.left else node.right
if child is None:
node = None
else:
node = child
else:
# 双分支节点：用右子树最小值替换并删除
min_node = self.find_min(node.right)
node.data = min_node.data
node.right = self.remove(min_node.data, node.right)
if node is None:
return None
# 更新高度
self.update_height(node)
# 检查平衡因子
balance = self.balance_factor(node)
# 左子树不平衡
if balance > 1:
if self.balance_factor(node.left) >= 0: # 左左型
return self.LL(node)
else: # 左右型
return self.LR(node)
# 右子树不平衡
if balance < -1:
if self.balance_factor(node.right) <= 0: # 右右型
return self.RR(node)
else: # 右左型
return self.RL(node)
return node
# ---------------------- 测试用例 ----------------------
if __name__ == "__main__":
avltree = AVLTree()
data = [16, 3, 7, 11, 9, 26, 18, 14, 15]
# 插入节点
for num in data:
avltree.root = avltree.insert(num, avltree.root)
assert avltree.is_balance(avltree.root), f"插入{num}后树不平衡!"
print("初始树结构：")
print("前序遍历：", end="")
avltree.preorder_iterator(avltree.root)
print("\n中序遍历：", end="")
avltree.inorder_iterator(avltree.root)
print("\n后序遍历：", end="")
avltree.postorder_iterator(avltree.root)
print("\n")
# 删除节点
avltree.root = avltree.remove(7, avltree.root) # 删除中间节点
avltree.root = avltree.remove(16, avltree.root) # 删除根节点
print("删除后树结构：")
print("前序遍历：", end="")
avltree.preorder_iterator(avltree.root)
print("\n中序遍历：", end="")
avltree.inorder_iterator(avltree.root)
print("\n后序遍历：", end="")
avltree.postorder_iterator(avltree.root)
B树
- 多路平衡查找树
- 需要满足一下要求，定义出一棵m阶的B树
- 或一棵空树
- 1.树中每个结点最多有m棵子树(m>=2)
- 2.根结点至少有两个子结点
- 3.除根结点外，结点中关键字的个数取值范围为(m/2)-1到m-1(m/2向上取整)
- 4.所有叶子结点都在同一层
- 5.除根结点和叶子结点外，如果结点有k-1个关键字，这个结点就有k个子结点，关键字按递增顺序排序
Ｂ树的查找
- 把根结点读出，在根结点所包含的关键字中进行查找给定元素关键字，找到则查找成功
- 否则，确定要查找关键字大小的范围，根据指针指向子结点，在子结点中继续查找，如果查找到叶子结点仍未找到，表示查找失败.
- 查找示意图
B树的插入
- 先确定插入元素在B树是否已经存在，若不存在则进行插入操作
- 若找到插入的位置结点空间足够，则顺利完成插入；否则无法插入.
B+树和B*树
- B+树和B数的差异
- 1.有k个子结点的B+树中含有k个关键字，非叶子结点中的每个关键字不保存数据，只用来索引，所有数据都保存在叶子结点中.
- 2.所有的叶子结点包含全部关键字信息，以及指向含有这些关键字的指针，且叶子结点本身是依关键字值递增的链表
- 3.所有的非终端结点可以视为索引，结点中仅含其子树根结点中最大或最小的关键字.
- B*与B+树
- B是B+树的一种变形，在B+树的基础上，B树为非根结点和非叶子结点增加了指向兄弟结点的指针
- B*树定义了非叶子结点的关键字数量至少为(2/3)×m，即块的最低使用率为2/3(B+树的使用率为1/2).