# 树
- 节点的高度:节点到子节点的**最长路径**(边数)
- 节点的深度:根节点到这个节点所经历的**边的个数**
- 节点的层数:节点的深度 + 1
- 树的高度:根节点的高度
高度、层数类比楼层,从下往上数;深度类比鱼塘,从上往下数
## 二叉树
- 满二叉树
- 完全二叉树
## 二叉树的遍历
- 前序遍历(对于任意节点,先打印这个节点,再打印它的左子树,最后打印它的右子树)
- 中序遍历(对于任意节点,先打印它的左子树、再打印它本身,最后打印它的右子树)
- 后序遍历(对于任意节点,先打印它的左子,再打印它的右子树,最后打印它本身)
**二叉树的前、中、后序遍历就是一个递归的过程**
## 二叉查找树
在树中的任意一个节点,其左子树中的每个节点的值,都要小于这个节点的值,而右子树节点的值都大于这个节点的值
## 对比散列表
1. 散列表的数据无序存储,二叉查找树只需要中序遍历
2. 散列表扩容耗时多,遇到散列冲突时不稳定,平衡二叉查找树性能非常稳定,时间复杂度稳定在 O(logn)
3. 散列表查找复杂度是常量级,但因为哈希冲突,这个常量不一定比 logn 小
4. 散列表的构造比二叉查找树复杂,考虑的东西多,如散列函数的设计、冲突解决办法、扩容、缩容等,平衡二叉查找树只需要考虑平衡性
## 平衡二叉树
二叉树中任意一个节点的左右子树的高度相差不大于 1
平衡二叉查找树中“平衡”的意思,其实就是让整棵树左右看起来比较“对称”、比较“平衡”,不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些,相应的插入、删除、查找等操作的效率高一些
## 红黑树
红黑树中的节点一类被标记为黑色,一类被标记为红色
- 根节点是黑色的;
- 每个叶子节点都是黑色的空节点,也就是说,叶子节点不存储数据
- 任何相邻的节点都不能同时为红色,也就是说,红色节点是被黑色节点隔开的;
- 每个节点,从该节点到达其可达叶子节点的所有路径,都包含享同数目的黑色节点;
AVL 树是一种高度平衡的二叉树,查找效率非常高,但是为了维持这种平衡,要付出更多代价,每次插入、删除都要做调整,复杂且耗时
红黑树只是近似平衡,不是严格平衡,所以维护平衡的成本上比 AVL 树要低,因此对于工程应用来说为了面对各种异常情况,支撑工业级应用,倾向于性能稳定的红黑树
红黑树实现困难,对平时开发帮助不大,不需要亲手写一个红黑树,对面试帮助也不大,有的放矢
没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
收起资源包目录
读书笔记:《数据结构与算法之美》学习.zip (59个子文件)
读书笔记:《数据结构与算法之美》学习
algorithm
.vscode
settings.json 449B
.prettierrc 75B
jest.config.js 431B
src
data-structures
doubly-linked-list
DoublyLinkedListNode.ts 495B
DoublyLinkedList.ts 4KB
hash-table
HashTable.ts 3KB
tree
binary-search-tree
BinarySearchTreeNode.ts 3KB
BinarySearchTree.ts 506B
BinaryTreeNode.ts 3KB
README.md 3KB
linked-list
LinkedListNode.ts 332B
LinkedList.ts 4KB
README.md 219B
heap
MinHeap.ts 195B
MaxHeap.ts 195B
Heap.ts 5KB
application.md 3KB
stack
Stack.ts 738B
.gitkeep 0B
queue
Queue.ts 825B
graph
GraphVertex.ts 2KB
README.md 615B
Graph.ts 3KB
GraphEdge.ts 728B
trie
Trie.ts 2KB
TrieNode.ts 1KB
algorithms
sorting
insertion-sort
InsertionSort.ts 649B
merge-sort
MergeSort.ts 1KB
radix-sort
RadixSort.ts 3KB
selection-sort
SelectionSort.ts 594B
bubble-sort
BubbleSort.ts 595B
quick-sort
QuickSort.ts 1KB
counting-sort
CountingSort.ts 2KB
math
fibonacci
fibonacci.ts 1KB
string
knuth-morris-pratt
knuthMorrisPratt.ts 1KB
rabin-karp
rabinKarp.ts 1KB
cryptography
polynomial-hash
PolynomialHash.ts 1KB
.gitkeep 0B
search
binary-search
binarySearch.ts 657B
graph
breadth-first-search
breadthFirstSearch.ts 2KB
depth-first-search
depthFirstSearch.ts 2KB
practice
__tests__
practice.spec.ts 0B
practice.ts 2KB
utils
comparator
Comparator.ts 948B
.git
index 5KB
HEAD 21B
refs
heads
main 41B
tags
remotes
origin
main 41B
objects
pack
pack-f5e67dfe918d7a0816f55dedc3480d1bbbfa076a.pack 47KB
pack-f5e67dfe918d7a0816f55dedc3480d1bbbfa076a.idx 10KB
info
FETCH_HEAD 117B
logs
HEAD 130B
refs
heads
main 130B
remotes
origin
main 144B
hooks
config 252B
branches
.babelrc 38B
package.json 685B
.gitignore 138B
tsconfig.json 599B
共 59 条
- 1
资源评论
九转成圣
- 粉丝: 5561
- 资源: 2962
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功