PTT
Submit
Submit
选择语言
正體中文
简体中文
PTT
Grad-ProbAsk
Re: [理工] [DS] 104台大电机丙 top down insertion
楼主:
easonc
(eason)
2016-02-15 10:11:25
※ 引述《easonc (eason)》之铭言:
: 我知道做top down 的insertion是由root开始往下走,
: 遇到full的node就split,然后继续往下走,重复这个过程。
: 当order是偶数(node满的时候会有奇数把key,如:2-3-4tree),
: split可以把正中间的key往上放,
: 比中间的key大的key分在右边的node,
: 比较小的key分在左边的node;
: 可是当order是奇数(node满的时候有偶数把key),就不能这样做了
:
如果有一棵2-3 tree:
7,9
/ | \
5,6 8 10
需要insert 4
如果做的是bottom up的insertion,
应该是把 4 insert到5,6的那个node,再split,再往上检查看有没有人需要再split;
但是,
如果是top-down 的 insertion,
应该是
从根开始往下看,发现7,9的node已经满了,就split 7,9的node
可是只有2个key的node怎么split,好像都很奇怪
我是不是误会了什么qq
作者:
pups003
(冈本)
2016-02-15 10:27:00
可以split吧,2-3 tree是link数为2 or 3
" target="_blank" rel="nofollow">
楼主: easonc (eason)
2016-02-15 10:53:00
多谢~你中间split的过程是怎样呢?是把4insert到56的node再split,然后5跑进79的node再split一次吗?
作者:
pups003
(冈本)
2016-02-15 11:33:00
4,7,9 split,然后4到5,6 发现也要 split我是这样想的喇
楼主: easonc (eason)
2016-02-15 11:55:00
可以一步一步画图吗?3Q~感觉好像会有别的case怪怪的
作者:
janus7799
(Janus逍遥)
2016-02-15 11:56:00
2-3 top down应该不用split路径上的3-node,因为3-node不保证可以分成三个结点。借用楼上的图,如果delete 6再insert 4,沿途split所有3-node会造成高度不平衡
楼主: easonc (eason)
2016-02-15 12:33:00
我也是想到这个情况可是不沿途split 3-node该怎么insert呢
作者:
dddm49
(芭蕉)
2016-02-15 16:28:00
不是找到正确位置插入后 再看有无overflow 决定是否split吗
继续阅读
[理工] 105交大计系
leo258x
[理工] 105 交大 DS 红黑树
yaxauw
[理工] [DS] 104台大电机丙 top down insertion
easonc
Re: [理工] 103台联大线性代数问题
sky2201
Re: [理工] 103台联大线性代数问题
sky2201
[理工] 驱动点阻抗法
superdevil
[理工] 103台联大线性代数问题
sky2201
[生医] 台大 103生化
howard852963
[理工] [DS]100台大电机丙 多选第十题
Billgaspeed
[理工] [DS] 100台大电机 单选第六题 Trie
Billgaspeed
Links
booklink
Contact Us: admin [ a t ] ucptt.com