11.数据结构知识框架1
需积分: 0 64 浏览量
2022-08-03
16:19:15
上传
评论
收藏 464KB PDF 举报
数据
结
构
知
识
框架
B
树
平
衡
的
多
叉
树
性
质
根
结
点
至
少
有
两个
孩子
每
个
非
根
结
点
至
少
有
M/2
（上
取
整
）个
孩子
，
至
多
有
M
个
孩子
每
个
非
根
结
点
至
少
有
M/2-1
（上
取
整
）个
关
键
字
，
并
且
以
升
序
排
列
key[i]
和
key[i+1]
之
间
的
孩子
结
点
的
值
介于
key[i]
、
key[i+1]
之
间
所
有
的
叶
子
结
点
都
在
同
一
层
B+
树
性
质
其
定
义
基
本
与
B
树
相
同
非
叶
子
节
点
的
子
树
指
针
与
关
键
字
个
数
相
同
非
叶
子
结
点
的
子
树
指
针
P[i]
，
指
向
关
键
字
值
属
于
[k[i],k[i+
1])
的
子
树
为
所
有
叶
子
节
点
增
加
一个
链
指
针
所
有
关
键
字
都
在
叶
子
节
点
出
现
搜
索
和
B
树
基
本
相
同
特
性
所
有
关
键
字
都
出
现
在
叶
子
节
点
的
链
表
中
（
稠
密
索
引
），且
链
表
中
的
关
键
字
恰
好
是有
序
的
不
可
能
在
叶
子
结
点
命
中
非
叶
子
节
点
相
当
于
是
叶
子
结
点
的
索
引
（
稀
疏
索
引
），
叶
子
结
点
相
当
于
是
存
储
（
关
键
字
）
数据
的
数据
层
更
适
合
文
件
索
引
系统
B*
树
在
B+
树
的
非
根
和
非
叶
子
结
点
之
间
再
增
加
指
向
兄
弟
的
指
针
子
主
题
2
哈
希
搜
索
（
检
索
）
在
数据
元
素
集
合
中
查
找
是
否
存
在
关
键
字
等
于
某
个
给
定
关
键
字
数据
元
素
的
过
程
结
果
成
功
失
败
搜
索结
构
用
于
搜
索
的
数据
集
合
搜
索
的
环
境
静
态
环
境
在
执
行
插
入
和
删
除
等
操
作
的
前
后
搜
索结
构
不
会
发
生
改
变
动
态
环
境
为保
持
较
高
的
搜
索
效
率
，
搜
索结
构
在
执
行
插
入
和
删
除
等
操
作
的
前
后
将
自
动
调
整
，
结
构
可
能
会
发
生
改
变
查
找
静
态
查
找
顺
序
表
从
前
往
后
依
次
遍
历
O
（
n
）
有
序
顺
序
表
二
分
查
找
O
（
log(n)
）
索
引
顺
序
表
动
态
查
找
二
叉
树
结
构
二
叉
排
序
树
平
衡
二
叉
树
树
结
构
B
树
B+
树
哈
希
查
找
每
个
元
素
的
关
键
码
和
结
构
中
一个
唯
一
的
结
存
储
位
置
相
对
应
散
列
方
法
插
入
和
查
找
数据
利
用
哈
希
函
数
求
出
存
储
位
置
再
存
放
或
者
查
找
哈
希
冲
突
对
于
两个
数据
Ki
和
Kj
（
i!=j
）
,Ki!=Kj,
但
是有
Hash(Ki)==
Hash(Kj)
散
列函
数
哈
希
函
数
的
定
义
域
必
须
包
括
需
要
存
储
的
全
部
关
键
码
，
而
如
果
散
列
表
允
许
有
m
个
地址
时
，
其
值
域
必
须
在
0-m-1
之
间
哈
希
函
数
计
算
出
来
的
地址
能
均
匀
的
分
布
在
整
个
空
间
中
哈
希
函
数
应
该
比
较
简
单
常
见
哈
希
函
数
直
接
定
址
法
取
关
键
字
的
某
个
线
性
函
数
为
散
列
地址
优
点
：
简
单
均
匀
缺
点
：
需
要
事
先
直
到关
键
字
的
分
布
情
况
使
用
场
景
：
适
合
查
找
比
较
小
且
连
续
的
情
况
除
留
余
数
法
设
散
列
中
允
许
的
地址
数
为
m
，
取
一个不
大
于
m
，
但
最
接
近
或
者
等
于
m
的
质
数
p
作为
除
数
，
按
照
哈
希
函
数
：
Hash(
key)=key%p,p<=m;
将
关
键
码
转
换
成
哈
希
地址
平
方
取
中
法
假
设
关
键
字
是
1234
，
平
方
就
是
1522756
，
再
抽
取
中
间
的
三
位
数
227
作为
散
列
地址
折
叠
法
将
关
键
字
从
左
到
右
分
成
位
数
相
等
的
几
部
分
，
然
后
将
这
几
部
分
叠
加
求
和
，
并
按
散
列
表
长
，
取后
几
位作为
散
列
地址
随
机
数
法
选
择
一个
随
机
函
数
，
取
关
键
字
的
随
机
函
数
值
为
它
的
哈
希
地
址
数
学
分
析
法
设
有
n
个
d
位
数
，
每
一
位
肯能
有
r
种
不
同
的
符
号
，
这
r
种
不
同
的
符
号
在
各
位
上
出
现
的
频
率
不一
定
相
同
，
可
能
在
某
些位
上
分
布
比
较
均
匀
，
可
将
分
布
均
匀
的
几
位
根
据
开
散
列
的
方
式
作
为
散
列
地址
散
列冲
突
处
理
方
法
闭
散
列
法
一
旦
发
生
冲
突
，
就
去
寻
找
下一个
空
的
散
列
表
地址
，
只
要
散
列
表
足
够大
，
空
的
散
列
地址
总
能
知
道
线
性
探
查
插
入
时
发
现
该
位
置
的
数据
和
要
插
入
数据
相
等
，不
插
入
产
生
冲
突
，
依
次
查
看
其
后
的
下一个
桶
，
如
果有
空
位
置
插
入
数据
二
次
探
查
使
用
二
次
探
查
法
，
在
表
中
寻
找
下一个
空
位
置
的
公
式
是
H(
i)=(H0+i^2)%m,H(i)=(H0-i^2)%m
当
表
的
长
度
为
质
数
且
转载
因
子
不
超
过
0.5
时
，
新
的
表
项
一
定
能
插
入
双
散
列
法
需
要
两个
散
列函
数
，
当
一个
发
生
冲
突
时
，
利
用
下一个
散
列
函
数
计
算
偏
移
量
载
荷
因
子
a=
填
入
表
中
的
元
素
个
数
/
散
列
表
的
长
度
控
制
在
0.7-0.8
以
下，
超
过
0.8
，
查
表
时
CPU
缓
存
指
数
上
升
开
散
列
法
首
先
对
关
键
码
集
合
用
散
列函
数
计
算
散
列
地址
，
具
有
相
同
地
址
的
关
键
码
归
于
同
一
子
集
合
，
每
个
子
集
合
称
为
一个
桶
，
各
个
桶
中
的
元
素
通过
一个
单
链
表
链
接
起
来
，
各
链
表
的
头
结
点
组
成
一个
向
量
，
向
量
的
元
素
个
数
与
可
能
的
桶
数
相
同
布
隆
过
滤
器
当
一个
元
素
被
加入
集
合
时
，
通过
k
个
散
列函
数
将
这
个
元
素
映
射
成
一个
位
数
组
中
的
k
个
点
，
将它
们
置
为
1
，
检
索
时
只
要
看
是
不
是
都
是
1
，
就
可
以
，
只
要
有
一个
零
就
不
是
，
全
是
1
，
可
能
是
排
序
概
念
就
是
将
一
组
杂
乱
无
章
的
数据
按
照
一
定
的
规
律
（
升
序
或
降
序
）
组织
起
来
数据
表
待
排
序
数据
元
素
的
有
限集
合
排
序
码
通
常
数据
元
素
有
多
个
属
性
域
，
其
中
有
一个
数据
域
可
用
来
区
分元
素
，
作为
排
序
依
据
，
该
域
即
为
排
序
码
如
果
在
数据
表
中
各
个
元
素
的
排
序
码
互
不
相
同
，
这
种
排
序
码
称
为主
排
序
码
排
序
算
法
的
稳
定
性
两个
元
素
R[i]R[j],
它
们
排
序
码
K[i]==K[j]
，且
在
排
序
之
前
，
元
素
R[i]
在
R[j]
之
前
，
元
素
在
R[i]
和
R[j]
的
顺
序
不
变
常
见
排
序
算
法
插
入
排
序
直
接插
入
排
序
插
入到
已
排
序序
列
中
，
先
找
位
置
，
然
后
将
位
置
之
后
得
元
素
后
移
稳
定
希
尔
排
序
缩
小
增
量
排
序
选
择
排
序
选
择
排
序
每次
把
最
小
的
元
素
换
在
最
前
面
锦
标
赛
排
序
一
直
两两
比
较
找
出
获
胜者
，
将
这
个不
再
比
较
，
其
他
继续
两
两
比
较
，
取
得
获
胜者
，一
直
循
环
不
稳
定
堆
排
序
升
序
创
建
大堆
，
否
则创
建
小
堆
不
稳
定
交
换排
序
冒
泡
排
序
稳
定
依
次比
较
相
邻
两个
元
素
，不
满
足
条
件交
换
快
速
排
序
取
一个
基
准
值
将
比
它小
得
放
在
左
侧
，
大
的
放
在
右
侧
。
左
右
两
部
分
递
归
取
基
准
值
继续
分
归并
排
序
归并
排
序
将
待
排
序
的
序
列分
成
两个
等
长
的
子
序
列
，
然
后
将它
们
合
并
成
一个
序
列
非
比
较
排
序
计
数排
序
基
数排
序
图
由
顶
点
集
合及
顶
点
间
关
系组
成
的
一
种
数据
结
构
顶
点
和
边
顶
点
图
中
结
点
称
为
结
点
边
顶
点
与
顶
点
之
间
有
一
条
边
图
的
分
类
有
向
图
在
有
向
图
中
，
顶
点
对
<x,y>
是有
序
的
<x,y><y,x>
是
不
同
的
两
条
边
无
向
图
(x,y)(y,x)
是
一
条
边
完
全
图
在
有
n
个
顶
点
的
无
向
图
中
，
若
有
n*(n-1)/2
条
边
，
即
任
意
两
个两个
顶
点
之
间
有
且
只
有
一
条
边
在
n
个
顶
点
的
有
向
图
中
，
若
有
n*(n-1)
条
边
，
即
任
意
两个
顶
点
之
间
有
且
仅
有
方
向
相
反
的
边
邻
接
结
点
在
无
向
图
中
G
中
，
若
（
u,v
）
是
E
（
G
）
中
的
一
条
边
，
则
称
u
和
v
互为
邻
接
顶
点
，
并
称
（
u
，
v
）
依
附
于
顶
点
u
和
v
在
有
向
图
G
中
，
若
<u,v>
是
E
（
G
）
中
的
一
条
边
，
则
称
顶
点
u
邻
接
到
v
，
顶
点
v
邻
接
自
顶
点
u
，
并
称
边
<u,v>
与
顶
点
u
和
v
相
关
联
顶
点
的
度
与
它
相
关
联
的
边
的
条
数
在
有
向
图
中
，
顶
点
的
度
等
于
该
顶
点
的
入
度
与
出
度
之
和
，
其
中
顶
点
v
的
入
度
是
以
v
为
终
点
的
有
向
边
的
条
数
，
记
做
indev(
v)
顶
点
v
的
出
度
是
以
v
为
起
始
点
的
有
向
边
的
条
数
记
做
outdev
（
v
）
无
向
图
的
度
等
于
入
度
和
出
度
dev(v)=indev(v)=outdev(
v)
路
径
在图
G=(V,E)
中
，
若
从
顶
点
vi
出
发
有
一
组
边
使
其
可
到
达
顶
点
vj
，
则
称
顶
点
vi
到
vj
的
顶
点
序
列
为从
顶
点
vi
到
顶
点
vj
的
路
径
权
边
附
带
的
数据
信
息
路
径
长
度
对
于
不
带
权
的
图
，一
条
边
的
路
径
长
度
是
指
该
路
径
上
的
边
的
条
数
对
于
带
权
的
图
，一
条
路
径
的
长
度
是
指
一
条
路
径
的
路
径
长
度
是
指
该
路
径
上
各
个
边
权
值
的
总
和
简
单
路
径
与
回
路
如
路
径
上
各
个
顶
点
均
不
重
复
，
则
称
这
样
的
路
径
是
简
单
路
径
，
若
路
径
上
第
一个
顶
点
v1
和
最
后
一个
顶
点
vm
重
合
，
则
称
这
样
的
路
径
为
回
路
或
环
子
图
设
图
G={V,E}
和
图
G1={V1.E1},
若
V1
属
于
V
且
E1
属
于
E
，
则
称
G1
是
G
的
子
图
连通
图
无
向
图
中
，两个
顶
点
之
间
有
路
径
就
是
连通
的
，
任
一
对
顶
点
之
间
都
是
连通
的
则
称
这
个
图
是
连通
图
强
连通
图
在
有
向
图
中
，
任
意
一
对
顶
点
vi
和
vj
之
间
都
存
在
一
条
从
vi
到
vj
的
路
径
，
也
存
在
一
条
从
vj
到
vi
的
一
条
路
径
生
成
树
一个
连通
图
的
最
小
连通
子
图
称
作
该
图
的
生
成
树
，
有
n
个
顶
点
的
连通
图
的
生
成
树有
n
个
顶
点
和
n-1
条
边
图
的
存
储
结
构
邻
接
矩
阵
邻
接
表
无
向
图
有
向
图
图
的
遍
历
深
度
优
先
广度
优
先
连通
分
量
当
无
向
图
为
非
连通
图
时
，
从
图
中
某
一
顶
点
出
发
，
利
用
深
度
优
先
搜
索
或
广度
优
先
搜
索
算
法
无
法
遍
历
图
的
所
有
顶
点
，
而
只
能
访
问
到
该
节
点
所
在
的
最
大
连通
子
图
的
所
有
顶
点
，
这
些
顶
点
构
成
一个
连通
分
量
最
小
生
成
树
准则
只
能
使
用
图
中
的
边
来构
造
最
小
生
成
树
只
能
使
用
恰
好
n-1
条
边
来
连
接
图
中
的
n
个
顶
点
选
用
的
n-1
条
边
不
能
构
成
回
路
贪
心
算
法
在
问题
求
解
时
，
总
是
做出
当
前
看
起
来最
好
的
选
择
，
也
就
是
局
部
最
优
解
Kruskal
算
法
每次
找
一
条
具
有最
短
权
值
且不
再
同
一
连通
分
量
上
的
边
加入
生
成
树
prime
算
法
挨
着
找
单
元
最
短
路
径
从
在
带
权
图
的
某
一
顶
点
出
发
，
找
出
一
条
通
往
另
一个
顶
点
的
最
短
路
径
，
最
短
也
即
是
沿
路
径
各
边
的
权
值
和
最
小
初
识
数据
结
构
概
念
数据
描
述
客
观
事
物
的
符
号
，
是
计
算
机
中
可
以
操
作
的
对
象
，
能
被
计
算
机
识
别
，
并
输
入
给
计
算
机
处
理
的
符
号
集
合
数据
元
素
是
组
成
数据
的
、
有
一
定
意
义
的
基
本
单
位
，
在
计
算
机
通
常
作
为
整
体
处
理
，
也
被
称
为
记
录
数据
项
一个
数据
元
素
可
以
由
若
干
个
数据
项
组
成
。
数据
项
是
数据
不
可
分
隔
的
最
小
单
位
数据
结
构
形式
数据
结
构
是
相
互之
间
存
在
一
种
或
多
种
特
定
关
系
的
数据
元
素
的
集
合
分
类
逻辑
结
构
集
合
结
构
线
性
结
构
树
形
结
构
图
形
结
构
物
理
结
构
顺
序
存
储
结
构
链
式
存
储
结
构
具
体
概
念
逻辑
结
构
数据
对
象
中
数据
元
素
之
间
的相
互
关
系
集
合
结
构
集
合
中
的
数据
元
素
除
了
同
属
一个
集
合
外
，
它
们之
间
没
有
其
他
关
系
线
性
结
构
数据
元
素
之
间
是
一
对
一
的
关
系
树
形
结
构
数据
元
素
之
间
存
在
的
一
种
一
对
多
的
层
次
关
系
图
形
结
构
数据
元
素
是
多
对
多
的
关
系
物
理
结
构
数据
的
逻辑
结
构
在
计
算
机
中
的
存
储
形式
顺
序
存
储
结
构
数据
元
素
存
放
在地址
连
续
的
存
储
单
元
里
，
其
数据
间
的
逻辑
关
系
和
物
理
关
系
是
一
致
的
链
式
存
储
结
构
数据
元
素
存
放
在
任
意
的
存
储
单
元
里
，
存
储
单
元
可
以
是
连
续
的
，
也
可
以
是
不
连
续
的
逻辑
结
构是
面
向
问题
的
，
物
理
结
构是
面
向
计
算
机
的
，
其
基
本
的目
标
就
是
将
数据
及
其
逻辑
关
系
存
储到
计
算
机
的
内
存
中
程
序
算
法
数据
结
构
算
法
解
决
特
定
问题
求
解
步
骤
的
描
述
，
在
计
算
机
中
表
现
为
指
令
的
有
限
序
列
，
并
且
每
条
指
令
表
示
一个
或
多
个
操
作
算
法
特
性
输
入
算
法
有
零
个
或
多
个
输
入
输
出
至
少
有
一个
或
多
个
输
出
有
穷
性
算
法
在
执
行
有
限
的
步
骤
之
后
，
自
动
结
束
而
不
会
出
现
无
限
循
环
，
并
且一个
步
骤
在
可
接
受
的
时
间
内
完
成
确
定
性
算
法
的
每
一个
步
骤
都
有
确
定
含
义
，不
会
出
现
二义
性
可
行
性
算
法
的
每
一
步
都
必
须
是
可
行
的
，
也
就
是
说
，
每
一
步
都
能
够
通过
执
行
有
限
次
数
完
成
设计
算
法
要
求
正
确
性
可
读
性
健
壮
性
时
间
效
率
高
且
空
间
使
用率
低
简
单
性
算
法
的
复
杂
度
时
间
复
杂
度
空
间
复
杂
度
算
法
分
析
的
分
类
平
均
情
况
任
意
输
入
规
模
的
期望
运
行
次
数
最
坏
情
况
任
意
输
入
规
模
的
最
大
运
行
次
数
最
好
情
况
任
意
输
入
规
模
的
最
小
运
行
次
数
，
通
常
最
好
情
况
不
会
出
现
时
间
复
杂
度
--O
渐
进
表
示
法
一
般
算
法
O(n)
计
算
法
用
常
数
1
取
代
运
行
时
间
中
的
所
有
加
法
常
数
在
修
改
后
的
运
行
次
数
函
数
中
，
只
保
留
最
高
阶项
如
果最
高
阶项
系
数
存
在
且不
是
1
，
则
去
除
与
这
个
项
相
乘
的
常
数
分
治
算
法
的
时
间
复
杂
度
计
算
二
分
搜
索
算
法
的
时
间
复
杂
度
是
lgN
M
分
搜
索
算
法
的
时
间
复
杂
度
为
logM^N
递
归
算
法
的
时
间
复
杂
度
计
算
递
归总
次
数
*
每次
递
归
次
数
递
归
算
法
空
间
复
杂
度
算
法
N*
每次
递
归
空
间
大
小
递
归
递
归
定
义
若
一个
对
象
部
分
的
包
含
它
自
己
或
者
用
它
自
己
给
自
己定
义
，
则
称
这
个
对
象
是
递
归
的
递
归
的
过
程
一个
过
程
直
接
或
间
接
的
调
用
自
己
递
归
的
思
想
把
问题
分
解
成
规
模
更
小
的
具
有
与
原
来
问题
具
有
相
同
解
法
的
小
问题
递
归
条
件
缩
小
问题
规
模
，
使
新
问题
与
原
问题
具
有
相
同
的
解
决
方
式
设
置
递
归
的
出
口
递
归
分
类
数据
结
构
递
归
问题
解
法
递
归
递
归
调
用
栈
尾
递
归
递
归
调
用
返
回
的
结
果
总
被
直
接
返
回
尾
递
归
的
本
质
将
单
次
计
算
的
结
果
缓
存
起
来
，
传
递
给
下一
次
调
用
，
相
当
于
自
动
累
积
时
间
复
杂
度
递
归总
次
数
*
每次
递
归
次
数
回
溯法
基
本
思
想
迷
宫
算
法
递
归
的
优
缺
点
优
点
递
归
在
解
决
某
些
问题
的
时
候使
得
我
们
思
考
的
方
式
的
以
简
化
，
代
码
也
更
加
简
练
，
容
易
阅
读
缺
点
递
归
的
实
质
就
是
自
己
调
用
自
己
，
而
函
数
的
调
用
开
销
是
很
大
的
，
系统
要
为
每次
函
数
调
用
分
配
空
间
存
储
空
间
，
并
将
调
用
点
信
息
压
栈
，
而
在
函
数
的
调
用
结
束
后
，
还
要
释
放
空
间
，
弹
栈
恢
复
断
点
，
如
果
递
归
方
案
的
复
杂
度
栈
栈
的
概
念
一
种
特
殊
的
线
性
表
，
只
允
许
从
一
端
插
入
和
删
除
数据
特点
：
后
进
先出
顺
序
栈
顺
序
堆
栈
和
书
序
表
数据
成
员
相
同
，不
同
之
处
，
顺
序
堆
栈
的
入
栈
和
出
栈
操
作
只
允
许
对
当
前
栈
顶
进
行
共
享
栈
一个
数
组
实
现
两个
栈
原
理
既
然
是
两个
栈
共
享
一
段
空
间
，
向
中
间靠
拢
，
数
组
两
端
表
示
两个
栈
的
栈
底
，
栈
顶
一
直
向
中
间靠
近
应
用
场
景
两个
栈
空
间需
求
有
相
反
的
关
系
，
也
就
是
一个
增
长
一个
缩
短
的
场
景
链
式
栈
头
插
头
删
栈
的
应
用
括
号匹
配
逆
波
兰
表
达
式
迷
宫
算
法
队
列
只
允
许
在
一
端
插
入
数据
，
在
另
一
端
删
除
数据
的
特
殊
线
性
表
顺
序
队
列
实
现
方
式
一
队
头
不
动出
队
列
时
所
有
元
素
向
前
移
动
实
现
方
式
二
出
队
列
时
，
队
头
向后
移
动
一个
位
置
假
溢
出
现
象
多
次
入
队
列
、
出
队
列
操
作
后
出
现
的
尚
有
存
储
空
间
但
不
能
进
行
入
队
列
操
作
的
溢
出
真
溢
出
现
象
最
大
存
储
空
间
已
经
存
储
满
，
继续
进
行
入
队
列
操
作
循
环
队
列
头
尾
相
接
的
顺
序
存
储
队
列
就
是
循
环
队
列
队
列
满
队
列
空
的
判
断
少
用
一个
存
储
空
间
队
尾
指
针
加
一
等
于
队
头
指
针
就
是
队
列
满
的
判
断
条
件
判
空
条
件
是
尾
和
头
相
等
设计
一个
标
记
flag
初
始
flag
置
为
0
，
入
队
列
成
功
flag=1
，
出
队
列
成
功
flag
置
为
0
队
空
条
件
rear==front&&flag==0,
堆
满
条
件
rear==front&&flag=1
设
置
一个
计
数
器
初
始
时
count=0,
入
队
列
成
功
，
count+1,
出
队
列
成
功
count-
1
队
列
空
的
条
件
count==0
队
列
满
的
条
件
count>0&&rear==front
或
者
count==
MaxSize
链
式
队
列
队
列
的
链
式
存
储
结
构
，
其
实就
是
线
性
表
的
单
链
表
，
只
不
过
它
只
能
尾
进
，
头
出
而
已
优
先
级
队
列
带
有
优
先
级
的
队
列
优
先
级
高
的
先出
队
列
，
优
先
级
相
同
的
遵
守
先
进
先出
规
则
队
列
的
应
用
生
产
者
消
费
者
模
型
消
息
队
列
排
队
现
象
网络
数据
传
输
矩
阵
特
殊
矩
阵
有
很
多
值
相
同
的
元
素
或
有
许
多
零
元
素
，且
值
相
同
的
元
素
或
零
元
素
的
分
布
有
一
定
规
律
的矩
阵
对
称
矩
阵
一个
N*N
矩
阵
，
任
意
Aij=Aji
对
称
矩
阵
压
缩
存
储
由
于
对
称
矩
阵
上三
角
和
下三
角
是
相
同
的
所
以
只
需
存
一
半即
可
对
称
矩
阵
和
对
称
压
缩
存
储
的
关
系
下三
角
i>jSymmetricMatrix[i][j]==Array[i*(i+1)/2+j]
稀
疏
矩
阵
M*N
矩
阵
，
矩
阵
有
效
值
的
个
数
远
小
于
无效
值
的
个
数
，
分
布
没
有
规
律
稀
疏
矩
阵
压
缩
存
储
只
存
储
少
量
的
有
效
值
使
用
{row,col,value}
三
元
组
按
照
数
组
中
的
位
置
，
以
行
优
先
级
先
后
顺
序
一
次
存
放
矩
阵
逆
置
行
列
互
换
快
速逆
置
初
识
树
树
的
基
本
概
念
由
N
个
节
点
（
N>=0
）
构
成
的
集
合
有
一个
特
殊
的
节
点
，
称
为
根
节
点
，
根
节
点
没
有
前
驱
节
点
除
过
根
节
点
外
，
其
余
节
点
别分
成
M
个（
M>0
）个
互
不
相
交
的
集
合
T1
、
T2...Tn,
其
中
每
一个
集
合又
是
一
棵
与
树
结
构
类
似
的
子
树
树是
递
归
定
义
的
名
词解
释
结
点
结
点
包
括
一个
数据
元
素
及
若
干
指
向
其
他
子
树
的
分
支
（
指
针
（
索
引
））
结
点
的
度
结
点
所拥
有
的的
子
树
的
个
数
度
为
0
的
结
点
又
称
终
端
节
点
分
支
结
点
度
不
为
零
的
结
点
非
终
端
结
点
祖
先
结
点
从
根
结
点
到
该
结
点
所
经
分
支
上
的
所
有
结
点
子孙
结
点
以
某
结
点
为
根
结
点
的
子
树
中
的
所
有
结
点
双
亲
结
点
树
中
某
结
点
有
孩子
节
点
，
该
结
点
称
为
它孩子
节
点
的
双
亲
结
点
孩子
结
点
树
中
一个
结
点
的
子
树
的
根
结
点
称
为
该
结
点
的
孩子
结
点
兄
弟
结
点
具
有
相
同双
亲
结
点
的
结
点
树
的
度
树
中
所
有
结
点
的
度
的
最
大
值
结
点
的
层
次
从
根
结
点
到
树
中
某
结
点
所
经
路
径
上
的
分
支数
树
的
深
度
树
中
所
有
结
点
的
层
次
的
最
大
值
有
序
树
树
中
结
点
的
各
棵
子
树
T0,T1...
是有
序
的
无
序
树
树
中
结
点
的
各
棵
子
树
之
间
的
次
序
不
重
要
，
可
以
相
互交
换
位
置
森
林
树
m
棵
树
的
集
合
树
的
表
示
方
法
目
录
结
构
集
合
文
氏
图
树
的
存
储
结
构
双
亲
表
示
法
用
指
针
表
示
出
每
个
结
点
的
双
亲
结
点
优
点
寻
找
一个
结
点
的
双
亲
结
点
操
作
实
现
很
方
便
缺
点
寻
找
一个
结
点
的
孩子
结
点
很
不
方
便
孩子
表
示
法
用
指
针
指
出
每
个
结
点
的
孩子
结
点
优
点
寻
找
一个
结
点
的
孩子
结
点
比
较
方
便
缺
点
寻
找
一个
结
点
的
双
亲
结
点
很
不
方
便
双
亲
孩子
表
示
法
用
指
针
既
表
示
出
每
个
结
点
的
双
亲
结
点
，
也
表
示
出
每
个
结
点
的
孩子
结
点
孩子
兄
弟
表
示
法
表
示
出
第
一个
结
点
的
第
一个
孩子
结
点
，
也
表
示
出
每
个
结
点
的
下一个
兄
弟
结
点
树
的
应
用
电
脑
的目
录
树
之二
叉
树
概
念
一
棵
二
叉
树是
结
点
的
一个
有
限集
合
，
该
集
合
或
者
为
空
，
或
者
是
由
一个
根
节
点
加
上两
棵
分别
称
为
左子
树
和右
子
树
的
二
叉
树
组
成
特点
每
个
结
点
最
多
有
两
棵
子
树
二
叉
树
的
子
树有
左
右
之
分
，
其
次
序
不
能
颠
倒
满
二
叉
树
所
有
分
支
结
点
都
存
在
左子
树
和右
子
树
，
并
且
所
有
叶
子
结
点
都
在
同
一
层
上
完
全
二
叉
树
如
果
一
棵
具
有
N
个
结
点
的
二
叉
树
的
结
构
与
满
二
叉
树
的
前
N
个
节
点
的
结
构
相
同
，
称
为
完
全
二
叉
树
二
叉
树
的
性
质
、
若
规
定
根
节
点
的
层
次
为
1
，
则
一
棵
非
空
二
叉
树
第
i
层
上
最
多
有
2^
（
i-1
）（
i>=1
）个
结
点
若
规
定
只
有根
节
点
的
二
叉
树
的
深
度
为
1
，
则
深
度
为
K
的
二
叉
树
的
最
大
结
点
数
是
2^k-1(k>=0)
对
任何
一
棵
二
叉
树
，
如
果
其
叶
结
点
个
数
为
n0
，
度
为
2
的
非
叶
结
点
个
数
为
n2,
则
有
n0=n2+1
具
有
n
个
结
点
的
完
全
二
叉
树
，
如
果
按
照
从
上
至
下
从
左
到
右
的
顺
序
对
所
有
结
点
从
0
开
始
编
号
，
则
对
于
序
号
为
i
的
结
点
有
：
如
果
i>0,
则
序
号
为
i
的
结
点
的
双
亲
结
点
的
序
号
为
（
i-1
）
/2,
如
果
i==0
，
则
序
号
为
i
的
结
点
为
根
节
点
，
无
双
亲
结
点
如
果
2i+1<n,
则
序
号
为
i
的
双
亲
结
点
的
左孩子
序
号
是
（
i-1
）
/
2
，
如
果
(2i+1)>=n,
则
序
号
为
i
结
点
无
右
孩子
结
点
如
果
2i+2<n,
则
序
号
为
i
结
点
的
右
孩子
结
点
的
序
号
为
2i+2,
如
果
2i+2>=n,
则
序
号
为
i
结
点
无
右
孩子
结
点
二
叉
树
的
存
储
结
构
顺
序
存
储
优
点
、
存
储
完
全
二
叉
树
，
简
单
省
空
间
缺
点
对
一
般
二
叉
树
尤
其
单
支
树
，
存
储
空
间
利
用
不
理
想
链
式
存
储
子
主
题
1
仿
真
指
针
（
静
态
链
表
）
二
叉
树
的
基
本
操
作
二
叉
树
的
创
建
二
叉
树
的
遍
历
前
序
中
序
后
序
层
序
初
始
化
一个
队
列
把
根
节
点
的
指
针
入
队
列
当
队
列
非
空
时
循
环
执
行
出
队
列
取
一个
节
点
若
该
结
点
的
左子
树
非
空
，
将
该
节
点
的
左子
树
指
针
入
队
列
若
该
节
点
的
右
子
树
非
空
将
该
节
点
的
右
子
树
入
队
列
结
束
线索
化
二
叉
树
线索
化
概
念
按
照
二
叉
树
的
遍
历
将
二
叉
树
导
成
一个
线
性序
列
普
通
二
叉
树
可
能
存
在
的
问题
递
归
遍
历
有
可
能
导
致
栈
溢
出
非
递
归
版
本
可
能
会
降
低
程
序
的
效
率
想
要
找
到
某
种
遍
历
形式
下
某
个
节
点
的
前
驱
还
是
后
继
比
较
难
树
中
有
大
量
的
空
指
针
域
造
成
浪
费
，
线索
化
过
程
当
某
结
点
的
左
指
为
空
时
，
令
该
指
针
指
向
按
照
某
种
方
式
遍
历
二
叉
树时
得
到
该
结
点
的
前
驱
节
点
当
某
结
点
的
右
指
针
为
空
时
，
令
该
指
针
指
向
按
照
某
种
遍
历
方
式
遍
历
二
叉
树时
得
到
该
结
点
的
后
继结
点
线索
标
志
位
作
用
区
分
是
孩子
结
点
还
是
前
驱
或
者
后
继
leftThread
0leftChild
1leftThread
rightThread
0rightChild
1rightThread
线索
结
点
中
指
向
前
驱
或
者
后
继结
点
的
指
针
线索
二
叉
树
二
叉
树
的
结
点
加
上
线索
的
二
叉
树
对
二
叉
树
按
照
某
种
方
式
（
前
序
、
中
序
、
后
序
）
遍
历
使
其
称
为
线索
二
叉
树
的
过
程称
为
按
照
什么
方
法
对
二
叉
树
进
行
线索
化
堆
堆
的
概
念
把所
有
的
元
素
按
照
完
全
二
叉
树
的
方
式
存
储
在
一个一
维
数
组
中
并
满
足
Ki<=K2*i+1
且
Ki<=K2*i+2
（
Ki>=K2*i+1
且
Ki>=
K2*i+2
）
,
这
个
堆
称
为
最
小
堆
（
最
大堆
）
堆
的
分
类
小
堆
任
一
节
点
的
关
键
码
均
小
于
它左
右
孩子
的
关
键
码
，
位于
堆
顶
结
点
的
关
键
码
最
小
大堆
任
一
结
点
的
关
键
码
均
大
于
它左
右
孩子
的
关
键
码
，
位于
堆
顶
结
点
的
关
键
码
最
大
堆
的
性
质
如
果
i=0
，
结
点
i
是根
结
点
，
没
有
双
亲
结
点
，
否
则
结
点
i
的
双
亲
结
点
为
（
i-1
）
/2
如
果
2*i+1>n-1,
则
结
点
i
无
左孩子
，
否
则
结
点
i
的
左孩子
为
节
点
2*i+1
如
果
2*i+1>n-1,
则
结
点
i
无
左孩子
，
否
则
结
点
i
的
左孩子
为
节
点
2*i+2
堆
的
创
建
从
上
向
下
调
整
堆
的
插
入
堆
的
删
除
堆
的
应
用
优
先
级
队
列
Huffman
树
概
念
路
径
路
径
长
度
把
带
权
路
径
长
度
最
小
的
树
叫
做
Huffman
树
构
造
huffman
树
构
造
n
棵
只
有根
结
点
的
二
叉
树
森
林
，
每棵
二
叉
树
都
只
有
一
个
带
有权
值
的
根
结
点
重
复
以
下
步
骤
，
直
到
F
中
只
剩
下一
棵
树
在
二
叉
树
森
林
中
选
最
小
的
两个，
作为
左
右
子
树构
建
一
棵
新
的
二
叉
树
，
新
二
叉
树
的
根
结
点
的
权
值
为
左
右
子
树根
结
点
的
权
值
之
和
在
原
来
二
叉
树
森
林
里
删
除
这
两
棵
二
叉
树
把
新
的
二
叉
树
加入
二
叉
树
森
林
huffman
编
码
编
码
在
数据
通
信中
经
常
把
传
输
的
文
字
转
换
成
二
进
制
字
符
0
和
1
组
成
的
二
进
制
串
，
这
叫
做
编
码
等
长
编
码
不
等
长
编
码
文
件
压
缩
二
叉
搜
索
树
性
质
如
果
左子
树
不
为
空
，
则
左子
树
上
所
有
节
点
的
值
都
小
于
根
结
点
的
值
它
的
右
子
树
不
为
空
，
则
右
子
树
上
所
有
节
点
的
值
都
大
于
根
结
点
的
值
它
的
左
右
子
树
也
分别
为二
叉
搜
索
树
操
作
搜
索
若
根
结
点
不
为
空
根
结
点
key==
要
查
找
的
key
，
返
回
true
根
结
点
key>
查
找
key
，
在
其
左子
树查
找
根
结
点
key<
查
找
key
，
在
其
右
子
树查
找
否
则
返
回
false
插
入
首
先
检
测
这
个
节
点
是
不
是
已
经
存
在
，
要
是
存
在
不
插
入
否
则
将
元
素
插
入到
找
到
的
位
置
删
除
首
先判
断
是
否
在
树
中
，
没
有
直
接
返
回
有
的
情
况
要
删
除
的
节
点
没
有
孩子
节
点
直
接
删
除
该
结
点
要
删
除
的
节
点
只
有
左孩子
删
除
该
结
点
并
使
被
删
除
结
点
的
双
亲
结
点
指
向
被
删
除
结
点
的
左孩子
结
点
要
删
除
的
节
点
只
有
右
孩子
删
除
该
结
点
并
使
被
删
除
结
点
的
双
亲
结
点
指
向
被
删
除
结
点
的
右
孩子
结
点
要
删
除
的
节
点
有
左
、
右
孩子
结
点
在
它
的
右
子
树
中
寻
找
中
序
下
的
第
一个
结
点
（
关
键
码
最
小
），
用
它
的
值
填
补
到
被
删
除
节
点
中
，
再
来
处
理
该
结
点
的
删
除问题
二
叉
搜
索
树
性
能
分
析
最
坏
情
况
下，
平
均
查
找
长
度
为
O(n)
一
般
情
况
下
平
均
长
度
为
O(lgn)
AVL
树
AVL
树
性
质
它
的
左
右
子
树
都
是
AVL
树
左子
树
和右
子
树
高
度
之
差
（
简称
平
衡
因
子
）
的
绝
对
值
不
超
过
1
（
-1
、
0
、
1
）
如
果
一
棵
树是
高
度平
衡
的
，
它就
是
AVL
树
。
如
果
它
有
n
个
节
点
，
其
高
度
可
保
持
在
0(lgn)
，
平
均
搜
索
复
杂
度
O(lgn)
平
衡
化
旋
转
左
单
旋
右单
旋
左
右双
旋
右
左
双
旋
AVL
树
的
插
入
如
果是
空
树
，
插
入
后即
为
根
结
点
，
插
入
后
直
接
返
回
true
如
果树
不
空
，
寻
找
插
入
位
置
，
若
在
查
找
过
程
中
找
到
key
，
则
插
入
失
败
直
接
返
回
false
插
入
节
点
更
新
平
衡
因
子
，
对
树
进
行调
整
AVL
树
的
删
除
被
删
除
结
点
只
有
左孩子
parent
的
平
衡
因
子
为
1
或
者
-1
，
parent
高
度
不
变
，
则
从
parent
到
根
所
有
结
点
高
度
均
不
变
，不
用
调
整
被
删
除
结
点
只
有
右
孩子
parent
的
平
衡
因
子
变
成
0
，
虽
然
以
parent
为
根
的
子
树
平
衡
，
其
高
度
减
1
，
但
需
要
检
查
parent
的
双
亲
结
点
的
平
衡
性
被
删
除
结
点
左
右
孩子
都
有
变
为
删
除
中
序
遍
历
下
的
第
一个
结
点
q
结
点
parent
的
平
衡
因
子
为
2
或
者
-2
，
则
较
矮
子
数
缩
短
，
parent
发
生
不
平
衡
，
需
要
进
行
平
衡
化
旋
转
parent
较
高
子
树
的
根
为
q
如
果
q
的
平
衡
因
子
为
0
，
执
行
单
循
环
恢
复
parent
如
果
q
的
平
衡
因
子
与
parent
平
衡
因
子
（
正
负
）
号
相
同
，
则
执
行
一个
单
循
环
恢
复
parent
如
果
q
的
平
衡
因
子
与
parent
平
衡
因
子
（
正
负
）
号
相
反
，
则
执
行
一个
双
旋
转
恢
复
parent
红
黑
树
概
念
红
黑
树是
一
棵
二
叉
搜
索
树
，
它
在
每
个
节
点
上
增
加
了
一个
存
储
位
来
表
示
结
点
的
颜
色
，
保
证
最
长
路
径
不
超
过
最
短
路
径
的
两
倍
，
近
似
平
衡
性
质
每
个
结
点
不
是
红
色
就
是
黑
色
树
的
根
结
点
是
黑
色
如
果
一个
结
点
是
红
色
的
，
则
它
的
两个
孩子
结
点
是
黑
色
的
（
没
有
连
续
的
两个
红
色
结
点
）
对
于
每
个
节
点
，
从
该
结
点
到其
所
有
后
代
叶
节
点
的
简
单
路
径
上，
均
包
含
相
同
数
目的
黑
色
结
点
（
每
条
路
径
上
黑
色
结
点
的
数
量
相
等
）
每
个
叶
子
节
点
都
是
黑
色
的
（
此
处
的
叶
子
结
点
指
的
是
空
节
点
）
插
入
实
现
若
树
为
空
，
插
入
后
需
将
新
节
点
改
成
黑
色
插
入
结
点
的
父
节
点
为
黑
色
，不
违
反
任何
性
质
，
直
接插
入
情
况
三
情
况
四
情
况
五
删
除
运
用
C++STL
库
--map/setmultimapmultiset
Java
库
linux
内
核
其
他
一
些
库
红
黑
树
和
AVL
树
的
比
较
扫
码
回
复
【
脑
图
】
下
载
120
张
超
清
晰
脑
图
源
文
件
评论0