dataStructure

常用数据结构实现

1.动态数组√

2.单向链表-

3.双向链表-

4.循环链表-

• 链表实现可以看标准库container/list

5.栈√

6.队列√

7.二分搜索树√

8.堆√

• 堆实现可以看标准库container/heap
• 是一种优先队列，利用数组实现的完全二叉树
• 通过添加元素元素上浮和取出元素元素下沉两个操作维护堆的性质

9.一维线段树√

• 适用场景，对静态数据中的某个区间进行统计查询
• 利用空间换时间的思想，将预处理结果组织成平衡二叉树的数据结构

10.Trie字典树√

• 以单个字符作为节点的多叉树

11.并查集√

• 由子节点指向父节点的多叉树

12.AVL树√

• 是一种平衡二叉树
• 引入平衡因子的概念：当前节点的平衡因子大小 = 当前节点左子树的高度 - 当前节点右子树的高度
• 所有节点的平衡因子大小的绝对值要小于等于1
• 四种需要维护节点平衡性的情况：LL,RR,LR,RL

13.2-3树(左倾红黑树)√

14.2-3-4树(红黑树)√

15.哈希表√

16.B树√

17.B+树

18.滑动窗口√