type
Post
status
Published
date
Apr 7, 2025
slug
summary
tags
面试
硕士
category
技术
icon
password
B+树、基数树、红黑树、还有哪些树结构、比较
口述一下用两个栈模拟队列
用两个栈模拟队列就是需要两次翻转。两个栈分别是入队栈和出队栈。比如将12345加入入队栈，在出栈的时候先将其压入出队栈变成54321，最后弹出出队栈就变成了12345.
八个常见排序算法
排序算法分为基于比较的和非比较的。非比较的排序算法中一个数的值就决定了应该放在哪个位置 基于比较的排序算法有 选择排序、冒泡排序、插入排序、希尔排序、归并排序、快速排序、堆排序 非比较的排序算法有计数排序、基数排序、桶排序。 非比较的排序算法很有局限性，对数据有很多限定。例如计数排序需要小范围整数、基数排序需要数据是相同位数、桶排序需要数据均匀分布。并且非比较算法通常需要较多辅助空间。
选择排序：每次扫描数组可以选出本轮最小的元素，交换到数组的开头。因此需要On2。选择排序的执行时间与数据无关。 冒泡排序：每一轮扫描将较大的数据和后面相邻元素交换。On2如果某一轮没有数据交换，则说明已经有序可以退出。因此顺序数组可以实现On的复杂度 插入排序：类似扑克牌方式，数组的前端是有序数组，每次将当前的元素插入有序部分，也就是逐个交换，直到前面的元素比该元素小。如果本身有序则On。插入排序比选择排序好，因为对于有序数组可以降为On，而且内层循环很有可能提前终止，而冒泡排序提前终止比较少见。插入排序很适合接近有序或规模较小的数组，因为这些数组很容易提前终止内层循环。归并排序和快速排序拆分到较小子区间的时候可以转为使用插入排序，更快。 希尔排序：比快排差但是不需要递归，可以用在不支持递归的环境。希尔排序是分组插入排序，将数组按间隔分为多个组（比如0，4，8为1组，1，5，9为一组等），对每组执行插入排序。接下来将间隔缩减为一半，再执行插入。因此数据会越来越有序，适合插入排序。最后间隔为1.
快速排序：随机选择区间内某一个元素作为基准，将区间内所有小于基准的交换到基准之前，将所有大于基准的交换到基准之后。因此基准就在应该在的地方。分别再排序pivot左边和pivot右边区间 之所以随机选择是因为对于有序数组来说会使得左边的子区间特别小、右边子区间特别大，使得递归树倾斜 双路快排是pivot相等元素过多时，避免重复元素堆积到单侧，导致容易出现有序情况，从而递归树倾斜。每次将等于pivot的元素平均分到pivot两侧：
- 选择基准值（通常为左端元素，但推荐随机化选择
- i指针向右移动，直到遇到大于基准值的元素；j指针向左移动，直到遇到小于基准值的元素。
- 交换i和j的元素，继续扫描直至两指针相遇。
- 将基准值与j指针位置交换，完成分区。 优势：通过双向扫描，减少单侧元素堆积，使分区更均衡，降低递归深度 三路快排是每次将等于pivot的元素都排到一起，可以避免接下来的区间中再出现pivot，从而减少了左右递归区间的长度 • 指针定义与初始化 ◦ lt（左边界）：初始指向l，左侧区域的上界。 ◦ gt（右边界）：初始指向r+1，右侧区域的下界。 ◦ i（遍历指针）：初始指向l+1，从左向右扫描元素。 • 遍历与交换逻辑 ◦ 当前元素 < 基准值：与lt+1位置的元素交换，lt和i均右移。 ◦ 当前元素 > 基准值：与gt-1位置的元素交换，gt左移（i不动，需重新检查交换后的元素）。 ◦ 当前元素 = 基准值：仅i右移。 • 终止条件：当i与gt相遇时，遍历结束。 • 基准值归位 ◦ 将基准值（原左端元素）与lt位置的元素交换，此时基准值位于中间区域的左边界。 ◦ 递归处理左区域（l至lt-1）和右区域（gt至r），中间区域无需处理
B+树 增、删、查Olog_m^n n为总数据量，m为每个节点的最大子节点树
B+树是一种多路平衡查找树，所有数据记录在叶子节点，非叶子节点只存键和子结点指针。叶子节点形成一个链表，便于范围查找和遍历。由于多路，节点存储密度高，适合磁盘，能够减少磁盘IO次数，例如EXT4中的extent。传统inode使用多级间接索引，而B+树可以减少查询次数，提高效率
B树 增、删、查Olog_m^n n为总数据量，m为每个节点的最大子节点树
B树也是一种多路平衡查找树，数据放在叶子节点和内部节点上，叶子节点既存储键值又存储数据本身或者数据的指针。并且叶子节点没有链式连接，遍历不方便（这是因为数据在非叶子节点上，有链表也没用）
与B+树相比，B树不适合范围查询，因为需要回溯遍历。B树不如B+树扁平，因为B+树的非叶子节点不存储数据，可以放更多子节点指针。B树的删除插入节点可能在任意层分裂和调整。而B+树只影响叶子节点，复杂度较小。
B树的优点在于键值唯一，因为B+树只有叶子节点才放值，可能存储重复的键
红黑树
红黑树是一种自平衡的二叉查找树，最长路径不超过最短路径的两倍，特点是插入删除的时候，旋转次数少，保证增删改查的时间复杂度是Ologn，适合内存中的数据结构，比如虚拟内存管理中的VMA 通过颜色翻转和很少的旋转可以保持平衡，常数时间
B+树如果插入导致叶子节点分裂需要递归调整父节点的索引键
B+树插入流程
插入步骤
- 定位叶子节点
从根节点开始，根据关键字大小向下查找，直到找到对应的叶子节点（插入操作仅在叶子层进行）
- 直接插入（未溢出）
若叶子节点当前关键字数 k<m−1，直接按序插入新关键字并更新指针，操作结束
- 分裂叶子节点（溢出处理）
若插入后关键字数 k=m，则分裂为两个节点：
- 左节点：保留前 ⌈m/2⌉ 个关键字。
- 右节点：包含剩余 ⌊m/2⌋ 个关键字。
- 中间关键字上浮：将第 ⌈m/2⌉ 个关键字（即左节点的最大值）复制到父节点作为索引
- 递归调整父节点 ◦ 若父节点因接收上浮关键字导致 k=m，则继续分裂父节点，直至根节点。 ◦ 若根节点分裂，则生成新根（树高增加1），新根包含1个关键字和2个子指针
示例（4阶B+树）
- 插入43：根节点（也是叶子节点）变为 [43]。
- 插入48, 36：叶子节点变为 [36, 43, 48]。
- 插入32：节点分裂为 [32, 36] 和 [43, 48]，关键字36上浮到父节点
关键点
- 分裂策略：偶数阶（如4阶）取 ⌈m/2⌉（即第2个关键字）上浮；奇数阶（如3阶）取中间关键字
- 索引更新：内部节点仅存储关键字副本（或最大值）和子指针，不存储实际数据
AVL树
AVL树也是一种自平衡二叉查找树，可以保证时间复杂度为logn。AVL树要求每个节点的左右子树高度差不超过1，否则需要旋转调整。树的高度比红黑树小，因为红黑树只是保证最长路径不超过最短路径的两倍。但是旋转调整的开销大。红黑树由于放宽了平衡限制，可以保证旋转操作不超过3次，所以适合频繁修改的场景。
基数树 Ok
基数树是一种前缀树，结点存储字符或部分字符串，路径从根到叶子标识完整键，适合需要按前缀快速检索字符串的场景，通过合并公共前缀减少存储冗余，例如page cache就是基数树
三种树比较
B+树和红黑树查询都是Ologn，但是红黑树插入删除的开销小。
B+树是为磁盘优化的，一是树的高度小，便于减少访存，适合大数据量场景，二是结点与磁盘页面对齐，可以预读其他结点，三是双向链表便于范围查找和遍历。
红黑树的高度高于B+树，但是插入删除结点的旋转的次数少，开销小。而B+树需要合并和分裂结点，操作复杂度为Ologn
B+树用于文件系统和数据库索引，大规模数据树高可控。
红黑树适合内存中经常修改删除的场景，能够减少更新开销。比如stl中的map和set。
基数树能够通过共享前缀减少存储量。例如两个字符串共享前缀，则前缀放在父节点中，后面不同的部分放在两个子节点。通过前缀的匹配能够快速查询字符串，Ok，k是最长字符串长度。比如在page cache中将文件偏移量映射到物理页，偏移量作为键，4K页的地址作为值。
完全二叉树
只允许最后一排不满， 中间不可以有空缺，最后一排必须从左往右排序。
堆
堆是一种完全二叉树。
大根堆是指堆中每个节点都要大于等于子节点，小根堆是堆中每个节点都要小于等于子节点。
堆通常用数组的形式实现，按照层序遍历存放在数组中
建堆：1. 自下而上：将新元素插入叶子节点并且向上过滤；2.自上而下： 将新元素插入根节点并向下过滤
向上过滤：将某个叶子节点与父节点比较，如果大于/小于父节点就交换，直到根节点。
向下过滤：将父节点与子节点比较，若小于子节点就和最大/最小的子节点交换，直到叶子节点。
堆排序
从小到大排序就是小顶堆（每次弹出最小的根节点），从大到小排序就是大顶堆。
小顶堆/大顶堆建堆：第一步将数组调整为堆，On
- 从最后一个非叶子节点开始逆序下沉/上浮
排序：每次将堆顶元素交换到末尾，并缩小堆范围重新建堆，Onlogn