读书笔记：《数据结构与算法之美》学习.zip

# 树 - 节点的高度：节点到子节点的**最长路径**（边数） - 节点的深度：根节点到这个节点所经历的**边的个数** - 节点的层数：节点的深度 + 1 - 树的高度：根节点的高度 高度、层数类比楼层，从下往上数；深度类比鱼塘，从上往下数 ## 二叉树 - 满二叉树 - 完全二叉树 ## 二叉树的遍历 - 前序遍历（对于任意节点，先打印这个节点，再打印它的左子树，最后打印它的右子树） - 中序遍历（对于任意节点，先打印它的左子树、再打印它本身，最后打印它的右子树） - 后序遍历（对于任意节点，先打印它的左子，再打印它的右子树，最后打印它本身） **二叉树的前、中、后序遍历就是一个递归的过程** ## 二叉查找树 在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值 ## 对比散列表 1. 散列表的数据无序存储，二叉查找树只需要中序遍历 2. 散列表扩容耗时多，遇到散列冲突时不稳定，平衡二叉查找树性能非常稳定，时间复杂度稳定在 O(logn) 3. 散列表查找复杂度是常量级，但因为哈希冲突，这个常量不一定比 logn 小 4. 散列表的构造比二叉查找树复杂，考虑的东西多，如散列函数的设计、冲突解决办法、扩容、缩容等，平衡二叉查找树只需要考虑平衡性 ## 平衡二叉树 二叉树中任意一个节点的左右子树的高度相差不大于 1 平衡二叉查找树中“平衡”的意思，其实就是让整棵树左右看起来比较“对称”、比较“平衡”，不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些 ## 红黑树 红黑树中的节点一类被标记为黑色，一类被标记为红色 - 根节点是黑色的； - 每个叶子节点都是黑色的空节点，也就是说，叶子节点不存储数据 - 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的； - 每个节点，从该节点到达其可达叶子节点的所有路径，都包含享同数目的黑色节点； AVL 树是一种高度平衡的二叉树，查找效率非常高，但是为了维持这种平衡，要付出更多代价，每次插入、删除都要做调整，复杂且耗时 红黑树只是近似平衡，不是严格平衡，所以维护平衡的成本上比 AVL 树要低，因此对于工程应用来说为了面对各种异常情况，支撑工业级应用，倾向于性能稳定的红黑树 红黑树实现困难，对平时开发帮助不大，不需要亲手写一个红黑树，对面试帮助也不大，有的放矢