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