简单介绍数据结构内容
树图思维导图提供 计算机知识数据结构思维导图 在线思维导图免费制作,点击“编辑”按钮,可对 计算机知识数据结构思维导图 进行在线思维导图编辑,本思维导图属于思维导图模板主题,文件编号是:2e0c8dca1d783525dba151f72abfa26f
数据结构思维导图模板大纲
路径压缩算法
优化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
父换爷+染色(父爷)
根节点
染黑
定义
左根右,根页黑,不红红,黑路同
黑高:从这个节点到一个叶节点的任意一条简单路径上的黑色节点个数(包括叶节点不包括起始节点)
树图思维导图提供 计算机辅助电子线路设计 在线思维导图免费制作,点击“编辑”按钮,可对 计算机辅助电子线路设计 进行在线思维导图编辑,本思维导图属于思维导图模板主题,文件编号是:6ca7534122e478b7cd1b28b3c72601e8
树图思维导图提供 计算机网络应用层 在线思维导图免费制作,点击“编辑”按钮,可对 计算机网络应用层 进行在线思维导图编辑,本思维导图属于思维导图模板主题,文件编号是:1d7a27cc460774320c29f068a3a669b8