数据结构

概览图

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(红黑树)

补充说明

• 顺序表与(普通)链表的比较

• 栈，队列，字符串，数组都是特殊的线性表
• c++ 内在的数组是静态数组，数组大小必须是编译时的常量！因而需要更强的数组实现
  数组类型特点是没有插入删除元素操作，适合顺序储存。

///内置数组实现，静态数组
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树，实际应用中更多选择使用红黑树