AVL树、红黑树和哈希表
AVL 树、红黑树和哈希表
AVL 树
- AVL 树对于任意一个节点，左子树和右子树的高度差不能为超过 1。红黑树是一种自平衡二叉查找树。哈希表也称散列表。
- 平衡二叉树的高度和节点数量之间的关系也是
O(log n)的。 - AVL 树节点的
平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子 1、0 或 -1 的节点被认为是平衡的。带有平衡因子 -2 或 2 的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。 - AVL 树的
基本操作一般涉及运作同在不平衡的二叉查找树所运作的同样的算法。但是要进行预先或随后做一次或多次所谓的AVL旋转。 - 失去平衡后进行的规律可归纳为下列四种情况：
- 右旋转(RR)
对节点y进行向右旋转操作，返回旋转后新的根节点x T1< z < T2 < x < T3 < y < T4
y x x.right = y
/ \ / \ y.left = T3
x T4 向右旋转 (y) z y
/ \ - - - - - - - -> / \ / \
z T3 T1 T2 T3 T4
/ \
T1 T2
- 左旋转(LL)
对节点y进行向左旋转操作，返回旋转后新的根节点x T4 < y < T3 < x < T1 < z < T2
y x x.left = y
/ \ / \ y.right = T3
T1 x 向左旋转 (y) y z
/ \ - - - - - - - -> / \ / \
T2 z T1 T2 T3 T4
/ \
T3 T4
- LR
首先对x进行左旋转，转化为了LL的情况
y y
/ \ / \
x T4 向左旋转 (x) z T4
/ \ - - - - - - - -> / \
T1 z x T3
/ \ / \
T2 T3 T1 T2
- RL
首先对x进行右旋转，转化为了RR的情况
y y
/ \ / \
T1 x 向右旋转 (x) T1 z
/ \ - - - - - - - -> / \
z T4 T2 x
/ \ / \
T2 T3 T3 T4
Red black tree 红黑树
红黑树等价于2-3树，红黑树是每个节点都带有颜色属性的二叉查找树
红黑树性质 :
- 每个节点是红色或者黑色。
根节点是黑色。- 所有
叶子都是黑色。 - 如果一个节点是红色的，那么它的孩子节点
都是黑色的 - 从任意一个节点到叶子节点，经过的黑色节点是
一样的。
性能总结
- 对于
完全随机的数据，普通的二分搜索树很好用。缺点：极端情况退化成链表（或者高度不平衡） - 对于
查询较多的使用情况，AVL树很好用 - 红黑树牺牲了
平衡性（2logn 的高度），但它的统计性能更优（综合增删改查所有操作）
- 红黑树是保持
黑平衡的二叉树。严格意义上不是平衡二叉树，最大高度:2log n，时间复杂度:O(log n)。 - 红黑树和
AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。 - 红黑树相对于 AVL 树来说，牺牲了部分平衡性以换取
插入/删除操作时少量的旋转操作，整体来说性能要优于AVL 树。
扩展
- java.util 中的
TreeMap和TreeSet基于红黑树实现的 - 红黑树是一种
统计性能优秀的树结构，另一种是 Splay Tree(伸展树)。它的局部性原理：刚被访问的内容下次高概率被再次访问。
Hash Table 哈希表
哈希表概念
哈希表（Hash table，也叫散列表），是根据键（Key）而直接访问在内存存储位置的数据结构。它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做哈希函数，存放记录的数组称做哈希表。
哈希函数设计
哈希表充分表现了算法设计领域的经典思想：空间换时间键通过函数函数得到的索引分布越均匀越好
处理冲突
链地址法：将散列到同一个存储位置的所有元素保存在一个链表中。实现时，一种策略是散列表同一位置的所有冲突结果都是用栈存放的，新元素被插入到表的前端还是后端完全取决于怎样方便。开放定址法:
- 线性探测: 逐个探测存放地址的表，直到查找到一个空单元，把散列地址存放在该空单元。
- 平方探测: 线性探测，相当于发生冲突时探测间隔 d =i^2 个单元的位置是否为空，如果为空，将地址存放进去。
- 二次探查: 一次散列产生哈希地址冲突，为了解决冲突，采用另外的散列函数或者对冲突结果进行处理的方法。