Skip to content

skeletongo/datastructure

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

88 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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.滑动窗口√