TreeMind树图在线AI思维导图
当前位置:树图思维导图模板资格考试计算机计算机知识数据结构思维导图

计算机知识数据结构思维导图

  收藏
  分享
免费下载
免费使用文件
U517027942 浏览量:32022-11-04 13:19:52
已被使用0次
查看详情计算机知识数据结构思维导图

简单介绍数据结构内容

树图思维导图提供 计算机知识数据结构思维导图 在线思维导图免费制作,点击“编辑”按钮,可对 计算机知识数据结构思维导图  进行在线思维导图编辑,本思维导图属于思维导图模板主题,文件编号是: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