常见算法与数据结构
暴力:
二分: 前提,有序 , 时间复杂度O(lgn) ----> 转换成数据结构: 二叉树(二叉查找树,二叉搜索, 二叉有序树)
哈希: 最高效 , O(1), hash冲突 , jdk1.8 hashmap中的数据结构: 链表+红黑树(处理hash冲突的)
插值
索引: 搜索引擎 ,Lucene
bfs&dfs : 图论里面的遍历
平衡树AVL
B+树
B-Tree
二叉搜索树: 树的深度就是时间复杂度
红黑树 : 高效的查找结构, 底层也是一颗特殊的二叉查找树
性质:
1. 每个节点不是红色就是黑色
2. 不可能有连在一起的红色
3. 根节点就黑色(入度为0的节点)
4. 每个红色节点的两个子节点都是黑色. 叶子节点都是黑色(出度为0)
规则: 所有插入的节点默认就是红色
变色: 当前节点(插入节点)的叔,父节点都是红色
(1) 把叔父节点为黑色
(2) 祖变红
(3) 原当前节点的祖节点成为新的当前节点
左旋: 若当前节点父红叔黑,且当前节点是右子树时,左旋, 以父结节为支点左旋
右旋: 若当前节点父红叔黑,且当前节点是左子树时,右旋
(1) 把父节点变为黑色
(2) 把祖父节点变为红色
(3) 以祖父节点旋转
左旋右旋规律总结(以当前节点为基准): 父干爷死,兄弟靠爷,左旋右靠,右旋左靠
请看示例
10 20 30 5 15 3 8 再插入6
图2中, 0006与0008都是红色与性质2矛盾,所以必然会变色
图3中0005与0010都是红色,与性质2矛盾,且0005节点父红叔黑,且处于0010的左子树上,所以右旋
以上就是红黑树一个右旋示例
分析工具: https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
补充:
修订版1:
还是举例子说明, 依次添加数据,然后分析每一次旋转变色后的逻辑
插入50,60,70
