二叉树 二叉平衡树 B树 B+树
1 二叉树
这是最基础的树形结构。
- 定义：每个节点最多只有两个子节点（左子树和右子树）。
- 优点：比链表快，插入和查找的平均时间复杂度是 O(log N)。
缺点：不稳定。
在极端情况下（比如插入的数据本身已经是有序的，如 6，7，8，9），它会退化成一条链表。
此时查找时间复杂度会降到 O(N)，性能急剧下降。
2 二叉平衡树
为了解决二叉树的退化问题，平衡树诞生了。
- 定义：在二叉树的基础上增加了约束：左右子树的高度差不能超过 1
- 工作原理：每次插入或删除数据时，如果平衡被破坏，它会通过旋转操作来自动调整结构，使其始终保持平衡。
- 优点：避免了二叉树退化成链表的问题，查找效率非常稳定，始终维持在 O(log N)。
- 缺点：
树太高：当数据量非常大时（例如几百万条），log N 的深度可能依然有 20-30 层。每一次从磁盘读取一层数据，就是一次磁盘 I/O，非常慢。
数据量问题：它适用于内存中的查找，但不适用于海量数据的磁盘存储。 - 平衡二叉树插入数据，导致破坏平衡型的类型分为了四种：LL、LR、RR、RL，具体解决方法可参考：参考
3 B树
当数据量大到无法全部放入内存，必须存放在磁盘上时，B 树出现了。它是一种多路搜索树。
- 核心思想：不再像二叉树那样只有一个节点一个数据，而是一个节点可以存储多个值，并且拥有多个子节点（多叉的）。
- 结构特点：
每个节点包含键值和数据（或指针）。
节点内的键值从小到大排序。
所有节点（包括根节点和中间节点）都可能存储实际的数据。 - 优点：
降低了树的高度：因为一个节点存了多个值，树变得更矮更胖，从而减少了磁盘 I/O 次数。 - 缺点：
查询不稳定：数据可能存在于根节点，也可能存在于叶子节点。查找根节点就找到的话很快，但找到叶子节点就慢一些。
范围查询麻烦：要进行范围查询（如 > 20），需要多次从根节点遍历到叶子节点（中序遍历），比较繁琐。
4 B+树
B+ 树是 B 树的升级版，也是目前关系型数据库（如 MySQL 的 InnoDB 引擎）最常用的索引结构。
- 核心改进：
数据只存储在叶子节点：非叶子节点（内节点）只存储指针和键值，不存储数据。这就意味着非叶子节点可以容纳更多的索引项，让树变得更矮更宽。
叶子节点之间形成有序链表：所有的叶子节点通过指针连接成了一个有序的链表。 - 为什么数据库用 B+ 树而不是 B 树？
1.范围查询能力极强：比如查 age > 18。B+ 树只需要在叶子节点的链表上顺序遍历即可，不需要像 B 树那样回溯到父节点。这正是数据库最常用的操作。
2.查询效率稳定：任何数据的查找都必须从根节点走到叶子节点，路径长度一样。这使得查询时间非常稳定，便于数据库优化器进行评估。
3.更充分利用磁盘预读：非叶子节点不存数据，占用的空间更小，操作系统一次 I/O 可以读取更多的索引项到内存中。
5 二叉树遍历方式
- 定义二叉树
classTreeNode:"""二叉树节点"""def__init__(self, val=0, left=None, right=None): self.val = val # 节点的值 self.left = left # 左子节点 self.right = right # 右子节点5.1 深度优先DFS
classBinaryTree:"""二叉树操作类"""def__init__(self, root=None): self.root = root 5.1.1 前序遍历
defpreorder_recursive(self, node):"""前序遍历：根 -> 左 -> 右"""if node isNone:return[] result =[node.val] result.extend(self.preorder_recursive(node.left)) result.extend(self.preorder_recursive(node.right))return result 5.1.2 中序遍历
definorder_recursive(self, node):"""中序遍历：左 -> 根 -> 右"""if node isNone:return[] result = self.inorder_recursive(node.left) result.append(node.val) result.extend(self.inorder_recursive(node.right))return result 5.1.3 后序遍历
defpostorder_recursive(self, node):"""后序遍历：左 -> 右 -> 根"""if node isNone:return[] result = self.postorder_recursive(node.left) result.extend(self.postorder_recursive(node.right)) result.append(node.val)return result 5.2 广度优先BFS
deflevel_order(self):"""层序遍历，使用队列"""ifnot self.root:return[] result =[] queue =[self.root]# 用列表模拟队列while queue: level_size =len(queue) level_nodes =[]for i inrange(level_size): node = queue.pop(0)# 取出队列头部 level_nodes.append(node.val)if node.left: queue.append(node.left)if node.right: queue.append(node.right) result.append(level_nodes)# 按层存储return result 
