AVL樹節(jié)點(diǎn)的刪除規(guī)則

三種現(xiàn)象

現(xiàn)象1

注意:q是30，而不是20，因?yàn)閯h除了25，節(jié)點(diǎn)會移動,以下現(xiàn)象均遵循此規(guī)律

現(xiàn)象2

現(xiàn)象3

現(xiàn)象1和現(xiàn)象2比較簡單,不需要平衡化處理,現(xiàn)象3則比較復(fù)雜.先討論現(xiàn)象1和2

現(xiàn)象1刪除步驟

先找到節(jié)點(diǎn),然后刪除節(jié)點(diǎn)

private Node FindNode(int value){currentIndex = -1;Node node = _head;while (node != null){path[++currentIndex] = node;if (value == node.Data){return node;}if (value < node.Data){ node = node.Left;}else{ node = node.Right;}}return null;}public bool Remove(int value){var node = FindNode(value);if (node != null){RemoveNode(node);return true;}return false;}

其刪除節(jié)點(diǎn)的子節(jié)點(diǎn)<2個,即只有左節(jié)點(diǎn)或者右節(jié)點(diǎn)或者沒節(jié)點(diǎn)三種可能

如果刪除的是右節(jié)點(diǎn),那么該刪除節(jié)點(diǎn)的子節(jié)點(diǎn)(如果有的話)將會代替該節(jié)點(diǎn),反之也則替換左節(jié)點(diǎn)

代替的節(jié)點(diǎn)不是左節(jié)點(diǎn)就是右節(jié)點(diǎn)(只會是其中一個,若是兩個子節(jié)點(diǎn)的情況則另外考慮)

var tmp = node.Left; if (tmp == null) {tmp = node.Right; } if (currentIndex > 0) {if (path[currentIndex - 1].Left == node){ path[currentIndex - 1].Left = tmp;}else{ path[currentIndex - 1].Right = tmp;} } else {_head = tmp; }

現(xiàn)象2刪除步驟

即該節(jié)點(diǎn)的平衡因子為0，說明其左子樹和右子樹的高度是相同的

刪除該節(jié)點(diǎn)后,其左節(jié)點(diǎn)代替父節(jié)點(diǎn)

但程序的做法沒有我們看到這么簡單

將左節(jié)點(diǎn)的值賦給父節(jié)點(diǎn),然后將父節(jié)點(diǎn)的左節(jié)點(diǎn)以其原有左節(jié)點(diǎn)的左節(jié)點(diǎn)進(jìn)行替換(即將15的值換成12,將15的左子節(jié)點(diǎn)換成12的左子節(jié)點(diǎn)，由于12沒有左子節(jié)點(diǎn),所以12的左子節(jié)點(diǎn)為空),程序如下

private void RemoveNode(Node node) {Node tmp = null;if (node.Left != null && node.Right != null){tmp = node.Left;
node.Data = tmp.Data;node.Left = tmp.Left;} }

現(xiàn)象3刪除步驟

現(xiàn)象3和現(xiàn)象2方式前期處理方式相同,但是由于其左子樹和右子樹的高度不同導(dǎo)致了平衡因子出現(xiàn)2或-2的情況,后期還要進(jìn)行處理,即是對于平衡因子的處理

平衡因子的處理

還是一樣,當(dāng)刪除左節(jié)點(diǎn)時(父節(jié)點(diǎn)和某些祖父節(jié)點(diǎn)的)平衡因子-1，反之則+1

現(xiàn)象1則+1

現(xiàn)象2則-1

現(xiàn)象3則是父和祖父均-1

當(dāng)平衡因子絕對值變成2了，則進(jìn)行旋轉(zhuǎn)

轉(zhuǎn)載于:https://www.cnblogs.com/Clingingboy/archive/2010/10/09/1846865.html

總結(jié)

以上是生活随笔為你收集整理的平衡二叉树(AVL)实现(3)-删除的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。