algs

目录

• ☕ 线性结构
• 📂 常用排序
• 💻 树
• 💾 散列表

☕ 线性结构

数据结构	类
栈	MyStack.java
队列	MyQueue.java
单链表	Node.java
循环链表	LoopNode.java
双向链表	DoubleNode.java

📂 常用排序

排序方法	类
冒泡排序	BubbleSort.java
快速排序	QuickSort.java
插入排序	InsertSort.java
希尔排序	ShellSort.java
选择排序	SelectSort.java
归并排序	MergeSort.java
基数排序	RadixSort.java
堆排序	HeapSort.java

💻 树

链式存储的二叉树

类BinaryTree.java
结点类TreeNode.java

链式二叉树的操作	方法
前序遍历	frontShow()
中序遍历	midShow()
后序遍历	afterShow()
前序查找	frontSearch(i)
删除子树	delete(i)

顺序存储的二叉树

只适用于完全二叉树
类ArrayBinaryTree.java
应用：堆排序

顺序存储二叉树的操作	方法
前序遍历	frontShow(i)

线索二叉树

遍历高效
类ThreadedBinaryTree.java
结点类ThreadedNode.java

线索二叉树的操作	方法
中序线索化	threadNodes(node)
中序遍历	mi'dShow()

霍夫曼树

带权路径最小，可用于压缩编码。
类HuffmanTree.java

二叉排序树（BST）

有序的顺序存储查找方便，插入困难；
无序的顺序存储查找困难，插入简单；
链式存储插入和查找都困难；
二叉排序树插入和查找性能都不会太差。
类BinarySortTree.java
结点类Node.java

二叉排序树的操作	方法
插入结点	add(node)
查找结点	search(value)
删除结点	delete(value)

AVL树（平衡二叉树）

二叉排序树如果不平衡效率低下，AVL保证任何一个结点的左右子树高度差不超过1。
操作：在BST树插入结点平衡破坏时对结点进行旋转

类AVLTree.java
结点类Node.java

AVL树的操作	方法
结点的平衡因子	BF()
添加结点	add(node)
左旋转	leftRotate()
右旋转	rightRotate()

红黑树

具体见 算法第四版 的2-3树和左倾红黑树。
自己编的小口决：左黑右红即左旋，红左连续即右旋，左右全红变全黑，根节点总为黑。

💾 散列表

通过计算键值对中健的散列函数得到索引，通过索引值来进行查找和插入删除。
散列表的关键在于处理碰撞冲突，因而可以分为两种实现：基于拉链法和基于开发地址的散列表。

基于拉链法的散列表

类NodeHashST.java
链表符号表NodeST

操作	方法
计算键的散列函数	hash(key)
获取健的值	get(key)
插入新的键值对	put(key,value)

基于开放地址的散列表（线性探测）

线性探测要求探测表的利用率要小于1/2，所以需要动态调整容量。
类LinearHashST.java

操作	方法
调整容量	resize(cap)
计算键的散列函数	hash(key)
插入新的键值对	put(key,value)
获取键的值	get(key)
删除	delete(key)