计算机考研知识数据结构思维导图
数据结构主要包括两大部分
树图思维导图提供 计算机考研知识数据结构思维导图 在线思维导图免费制作，点击“编辑”按钮，可对 计算机考研知识数据结构思维导图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：9f61297da5d47f66c351c56f99b76bfa
思维导图大纲
数据结构思维导图模板大纲
并查集
路径压缩算法
优化find()函数
基本
查：最坏时间复杂度：O（n）
并：时间复杂度：O（1）
- int find(int x) //查找结点 x的根结点
{ if(pre[x] == x) return x; //递归出口：x的上级为 x本身，即 x为根结点
- 加权标记法 - 所有结点增设一个权值表示在书中的高度
应用
判断图的连通分量数
判断图是否有环
克鲁斯卡尔算法
红黑树
性质
根节点到叶节点的最长路径不大于最短路径的2倍
h<=2log(n+1)
若根节点黑高为x，则节点数最多为2^2x -1，最少为2^x -1
红黑树的某棵子树不一定是红黑树
若所有节点都是黑色，一定是满二叉树
从根节点开始任意一条查找路径上红节点不过半，但整棵树红节点可能过半
任意一节点的左右子树高度只差不超过2倍
相比之下AVL查找效率更高，但插入删除等操作要差一些
红黑树查找、插入、删除操作的最坏时间复杂度都是O（log2(n)）
插入
非根染红
红叔
叔父爷染色，爷变为新节点
黑叔
RR
LR
儿换爷+染色（儿爷）
RL
LL
父换爷+染色（父爷）
根节点
染黑
定义
左根右，根页黑，不红红，黑路同
黑高：从这个节点到一个叶节点的任意一条简单路径上的黑色节点个数（包括叶节点不包括起始节点）
相关思维导图模板
树图思维导图提供 考研择校思维脑图 在线思维导图免费制作，点击“编辑”按钮，可对 考研择校思维脑图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：667fa7d3f4f10bb572e92e4d672823f4
树图思维导图提供 计算机系统结构思维导图 在线思维导图免费制作，点击“编辑”按钮，可对 计算机系统结构思维导图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：d55735120bfc45f09e7d4f00035ca040
沪公网安备 31011502019485号
上海工商