树结构与递归学习笔记二
-
学习内容:
- 平衡树：
- AVL树、红黑树的概念及实现原理。
- 平衡树在搜索和插入操作中的优势。
- 堆（Heap）：
- 堆的基本概念、二叉堆、堆排序。
- 优先队列的实现原理及应用场景。
- 平衡树：
-
实践:
- 实现一个简单的AVL树或红黑树，理解自平衡的过程。
- 实现堆排序，理解其在优先队列中的应用。
1. 平衡树
1.1 平衡树的定义与重要性:
- 平衡树是一种二叉搜索树，其特性是在执行插入、删除操作后，通过旋转等手段保持树的高度平衡，以保证搜索、插入、删除操作的时间复杂度保持在O(log n)。
1.2 AVL树:
- AVL树是最早被发明的自平衡二叉搜索树，以其发明者Adelson-Velsky和Landis命名。
- 特点:
- 对于任意节点，其左右子树的高度差（平衡因子）最多为1。
- 每次插入或删除操作后，通过旋转操作（左旋、右旋）来重新平衡树。
- 旋转操作:
- 单旋转: 左旋或右旋，用于简单的不平衡情况。
- 双旋转: 先左旋后右旋或先右旋后左旋，用于复杂的不平衡情况。
- 优势:
- 保持平衡后，搜索、插入、删除操作的最坏时间复杂度为O(log n)。
1.3 红黑树:
- 红黑树是一种更为复杂的自平衡二叉搜索树，广泛应用于各大编程语言的标准库（如Java的TreeMap、C++的std::map）。
- 特点:
- 每个节点要么是红色，要么是黑色。
- 根节点为黑色。
- 红色节点不能有红色子节点（红色节点的子节点必须为黑色）。
- 从根节点到所有叶子节点的路径上，黑色节点的数量相同。
- 旋转与重新着色:
- 在插入和删除操作后，红黑树通过重新着色和旋转来维持平衡。
- 优势:
- 平衡性较AVL树稍差，但插入和删除操作更高效，平均情况下也能保证O(log n)的时间复杂度。
学习要点:
- AVL树适合需要频繁查找的场景，红黑树适合需要频繁插入和删除的场景。
- 掌握旋转操作是理解平衡树的关键。
2. 堆（Heap）
2.1 堆的基本概念:
- 堆是一种特殊的完全二叉树，分为最大堆和最小堆。
- 最大堆: 每个节点的值都大于或等于其子节点的值，堆顶为最大值。
- 最小堆: 每个节点的值都小于或等于其子节点的值，堆顶为最小值。
2.2 二叉堆:
- 二叉堆是一种常见的堆的实现，基于数组实现，适合存储在连续内存中的数据。
- 插入操作:
- 将新元素添加到堆的末尾，然后上浮调整，以维持堆的性质。
- 删除操作:
- 移除堆顶元素，将最后一个元素移到堆顶，然后下沉调整。
2.3 堆排序:
- 堆排序是一种基于堆的数据排序算法，时间复杂度为O(n log n)。
- 排序步骤:
- 将无序数组构造成一个堆。
- 重复从堆顶取出最大元素（对于最大堆），并将其移到数组的末尾，调整堆结构。
- 优势:
- 不需要额外的空间（原地排序），适合大数据排序。
2.4 优先队列:
- 优先队列是一种基于堆的数据结构，用于按优先级处理元素。
- 应用场景:
- 任务调度、网络流量管理等需要处理优先级的数据结构。
学习要点:
- 理解堆的上浮和下沉操作，是实现堆和堆排序的基础。
- 堆在优先队列中的应用广泛，是理解堆的重要实践内容。
3. 实践部分
3.1 实现AVL树:
-
实现思路:
- 实现基本的二叉搜索树插入和删除操作。
- 添加平衡因子的计算和更新。
- 实现左旋、右旋、双旋转等平衡操作。
-
伪代码示例:
class AVLNode:def __init__(self, key):self.key = keyself.left = Noneself.right = Noneself.height = 1class AVLTree:def insert(self, root, key):# 标准BST插入if not root:return AVLNode(key)if key < root.key:root.left = self.insert(root.left, key)else:root.right = self.insert(root.right, key)# 更新高度root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))# 获取平衡因子balance = self.get_balance(root)# 左左情况if balance > 1 and key < root.left.key:return self.right_rotate(root)# 右右情况if balance < -1 and key > root.right.key:return self.left_rotate(root)# 左右情况if balance > 1 and key > root.left.key:root.left = self.left_rotate(root.left)return self.right_rotate(root)# 右左情况if balance < -1 and key < root.right.key:root.right = self.right_rotate(root.right)return self.left_rotate(root)return root
3.2 实现红黑树:
- 实现思路:
- 实现基本的二叉搜索树插入和删除操作。
- 添加节点颜色属性。
- 实现插入和删除操作后的重新着色和旋转操作。
3.3 实现堆排序:
-
实现思路:
- 构造一个最大堆（或最小堆）。
- 重复取出堆顶元素并调整堆。
-
伪代码示例:
def heapify(arr, n, i):largest = il = 2 * i + 1r = 2 * i + 2if l < n and arr[i] < arr[l]:largest = lif r < n and arr[largest] < arr[r]:largest = rif largest != i:arr[i], arr[largest] = arr[largest], arr[i]heapify(arr, n, largest)def heap_sort(arr):n = len(arr)# 构造最大堆for i in range(n // 2 - 1, -1, -1):heapify(arr, n, i)# 一个个取出元素for i in range(n-1, 0, -1):arr[i], arr[0] = arr[0], arr[i]heapify(arr, i, 0)