插入一個(gè)元素--上浮
52與父親節(jié)點(diǎn)比較,并交換
繼續(xù)比較交換
最后52與父親節(jié)點(diǎn)62比較, 比其小則不再交換,此次插入完成
取出一個(gè)元素--下沉
62被取走,最末尾的16放到堆頂,并且刪除最后一個(gè)元素16 ,size-1
下沉開始:
16每次都與左右孩子比較,然后與較大的那個(gè)交換
繼續(xù)比較,交換
最后16與只有左孩子的15比較, 發(fā)現(xiàn)滿足堆的性質(zhì),此次下沉完成!
前k個(gè)大 那么就最小堆
???不確定 前k個(gè)小 那么就最大堆 兩兩相反
紅黑樹
絕對(duì)平衡: 根節(jié)點(diǎn)到任意子樹的距離都一樣
2-3添加一個(gè)節(jié)點(diǎn)
對(duì)于2-3樹來說,節(jié)點(diǎn)永遠(yuǎn)都不會(huì)添加到空的位置!
37<42 添加到樹的左邊, 左邊是空, 則融合成3節(jié)點(diǎn)(可容納3孩子)
12添加進(jìn)來,暫時(shí)進(jìn)行融合形成4節(jié)點(diǎn)(可容納4孩子)
2-3樹最多為3節(jié)點(diǎn)所以將4節(jié)點(diǎn)樹分裂由3個(gè)二節(jié)點(diǎn)組成的絕對(duì)平衡樹
再添加一個(gè)節(jié)點(diǎn)18, 18先與37比較,比37小, 往左邊查找, 比12大,而節(jié)點(diǎn)不能存在空位置,所以與12融合成3節(jié)點(diǎn)
6添加進(jìn)來,按照上面的規(guī)律,先暫時(shí)性與12融合成4節(jié)點(diǎn)
拆分
因?yàn)橐獫M足絕對(duì)平衡,而此時(shí)37節(jié)點(diǎn)人可以存放一個(gè)節(jié)點(diǎn),編程3節(jié)點(diǎn),所以融合
插入11
插入5 暫時(shí)融合
分裂
再融合
4節(jié)點(diǎn)--->分裂
此時(shí)滿足2-3樹的性質(zhì)
紅黑樹與2-3的等價(jià)
用紅邊表示a,b節(jié)點(diǎn)是在一起的(同級(jí))
因?yàn)槊總€(gè)節(jié)點(diǎn)最多只有一個(gè)父親節(jié)點(diǎn),所以在節(jié)點(diǎn)中添加一個(gè)顏色標(biāo)明這個(gè)被標(biāo)紅的節(jié)點(diǎn)與其父親節(jié)點(diǎn)是同級(jí)的. 左傾斜 b < c
現(xiàn)在再來看下5個(gè)性質(zhì):
紅黑樹添加新節(jié)點(diǎn)
紅黑樹添加的節(jié)點(diǎn)永遠(yuǎn)都是紅色的,第一次添加是根節(jié)點(diǎn),而根節(jié)點(diǎn)要保持黑色,所以變色.
繼續(xù)添加有兩種情況:
左旋:
注意,左旋只是一個(gè)子過程, 該過程并不能一直保證一紅一黑.
該過程有顏色翻轉(zhuǎn)
