Loading... ## 概览图 ```mermaid graph LR A(数据结构) --> B(线性表) B --> C(顺序表) C -->c(向量) B --> D(链表) D(链表)-->D2(列表) A --> E(栈) E --> w(顺序栈) E --> W2(链式栈) A --> F(队列) F --> P(链式队列) F --> U(顺序队列) U--> U3(循环队列) A --> G(字符串) G(字符串)--> G2(c风格-const char*) G(字符串)--> G3(结构表示法-c++中内置) G(字符串)--> G4(块链储存) A --> Z(数组) Z -->Z2(一维数组-就是线性表) Z --> Z3(多维数组-看做线性表) Z3 -->Z4(矩阵) A --> H(树) H --> I(二叉树) I --> I2(顺序实现) I2 --> I3(堆) I--> p(链式节点实现) p-->p2(二叉链表) p2-->p38(二叉搜索树) p-->p3(三叉链表) A -->uu(词典) uu -->u2(散列表) A -->R(优先级队列) R -->R2(堆) A --> J(图) o9(二叉搜索树)--> o4(平衡二叉搜索树) o4 --> u8(AVL树) o4 --> u9(伸展树) u9 --> u99(逐层伸展树 有缺陷) u9 --> u97(双层伸展树 常使用这种) o4 --> u999(B-树) o4 -->u788(红黑树) ``` --- ## 补充说明 * 顺序表与(普通)链表的比较 | | 顺序表 | 链表 | | -------------------------- | ------------------------------------- | ------------------------------ | | 序号读取元素 | O(1) | O(n) | | 序号插入元素 insert(pos,e) | O(n) 后移元素花费时间多 | O(n)查找花费时间多 | | insert_front(e) | O(n) | O(1) | | push_back(e) | O(1) 如果重新分配内存，也是O(n) | O(n) | | 内存使用 | 分配预留空间;可能没有足够大的连续空间 | 按需分配；可利用很小的碎片空间 | * 栈，队列，字符串，数组都是特殊的线性表 * c++ 内在的数组是静态数组，数组大小必须是编译时的常量！因而需要更强的数组实现 数组类型特点是没有插入删除元素操作，适合顺序储存。 ```cpp ///内置数组实现，静态数组 int m = 3; int n = 4; double A[m][4];// 在编译时就确定了大小 // 自定义数组实现,动态数组 int a,b; std::cin>>a>>b; Array B(a,b);//在编译时不确定数组大小 ``` * 二叉搜索树的中序遍历的元素排列满足一定顺序 ## AVL树和红黑树的比较和原理说明 ### AVL树 平衡标准比较严格：每个左右子树的高度差不超过1 最大高度是 1.44 ∗ log2 n + 2 − 1.328（100W个节点，AVL树最大树高28） 搜索、添加、删除都是 O(logn) 复杂度，其中添加仅需 O(1) 次旋转调整、删除最多需要 O(logn) 次旋转调整 ### 红黑树 平衡标准比较宽松：没有一条路径会大于其他路径的2倍 最大高度是 2 ∗ log2(n + 1)（ 100W个节点，红黑树最大树高40） 搜索、添加、删除都是 O(logn) 复杂度，其中添加、删除都仅需 O(1) 次旋转调整 ### 如何选择 搜索的次数远远大于插入和删除，选择AVL树；搜索、插入、删除次数几乎差不多，选择红黑树 相对于AVL树来说，红黑树牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树 红黑树的平均统计性能优于AVL树，实际应用中更多选择使用红黑树 最后修改：2025 年 01 月 04 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏
