数据结构 java demo
1---Array- 数组 增删改查等 动态数组
2---Stack- 栈(FILO) push pop 等 ;实例:使用栈实现括号匹配判断;数组实现与链表实现
3---Queue- 队列(FIFO) enqueue dequeue操作等 ;数组队列和循环队列实现 链表实现队列
4---LinkedList- 链表 增删改查等 虚拟头结点
leedcode_203 删除链表中的节点(所有值等于指定数值的结点)
5---Recursion- 递归 递归实现数组相加 leedcode_203问题及调试输出
6---BST- 二分搜索树 add(); contains(); 前序 中序 后序遍历 删除等
二分查找树或者是一棵空树,或者具有下列性质:
1.若它的左子树不为空,则左子树上所有结点的值均小于根结点的值;
2.若它的右子树不为空,则右子树上所有结点的值均大于根结点的值;
3.它的左右子树均为二分查找树。
7---Set- 集合 add();remove();contains()
基于二分搜索树实现集合--> BSTSet
基于链表实现集合 --> LinkedListSet
leedcode_804:唯一摩尔斯密码词
8---Map- 映射 add,remove,set,get,contains
基于链表实现映射 ---> LinkedListMap
基于二分搜索树实现Map ---> BSTMap
9---MaxHeap- 最大堆 add,extractMax,replace,heapify &基于堆实现优先队列
堆属于完全二叉树;
堆中任意节点值>=孩子节点值(最大堆);
leedcode_347. 前K个高频元素;
10---SegmentTree- 线段树(区间树) query,set
leedcode_303 .区域和检索 - 数组不可变
leedcode_307 .区域和检索 - 数组可修改
11--- Trie - 字典树(前缀树) add,contains,isPrefix
leedcode_221 .添加与搜索单词 - 数据结构设计
leedcode_677 .键值映射
12--- UnionFind- 并查集 unionElements,isConnected
基于size的优化
基于rank的优化
路径压缩
13--- AVL_Tree- 平衡树