您好,登錄后才能下訂單哦!
這篇文章將為大家詳細(xì)講解有關(guān)JDK中如何刪除元素,小編覺(jué)得挺實(shí)用的,因此分享給大家做個(gè)參考,希望大家閱讀完這篇文章后可以有所收獲。
刪除元素本身比較簡(jiǎn)單,就是采用二叉樹(shù)的刪除規(guī)則。
如果刪除的位置有兩個(gè)葉子節(jié)點(diǎn),則從其右子樹(shù)中取最小的元素放到刪除的位置,然后把刪除位置移到替代元素的位置,進(jìn)入下一步。
如果刪除的位置只有一個(gè)葉子節(jié)點(diǎn)(有可能是經(jīng)過(guò)第一步轉(zhuǎn)換后的刪除位置),則把那個(gè)葉子節(jié)點(diǎn)作為替代元素,放到刪除的位置,然后把這個(gè)葉子節(jié)點(diǎn)刪除。
如果刪除的位置沒(méi)有葉子節(jié)點(diǎn),則直接把這個(gè)刪除位置的元素刪除即可。
針對(duì)紅黑樹(shù),如果刪除位置是黑色節(jié)點(diǎn),還需要做再平衡。
如果有替代元素,則以替代元素作為當(dāng)前節(jié)點(diǎn)進(jìn)入再平衡。
如果沒(méi)有替代元素,則以刪除的位置的元素作為當(dāng)前節(jié)點(diǎn)進(jìn)入再平衡,平衡之后再刪除這個(gè)節(jié)點(diǎn)。
public V remove(Object key) { // 獲取節(jié)點(diǎn) Entry<K,V> p = getEntry(key); if (p == null) return null; V oldValue = p.value; // 刪除節(jié)點(diǎn) deleteEntry(p); // 返回刪除的value return oldValue; } private void deleteEntry(Entry<K,V> p) { // 修改次數(shù)加1 modCount++; // 元素個(gè)數(shù)減1 size--; if (p.left != null && p.right != null) { // 如果當(dāng)前節(jié)點(diǎn)既有左子節(jié)點(diǎn),又有右子節(jié)點(diǎn) // 取其右子樹(shù)中最小的節(jié)點(diǎn) Entry<K,V> s = successor(p); // 用右子樹(shù)中最小節(jié)點(diǎn)的值替換當(dāng)前節(jié)點(diǎn)的值 p.key = s.key; p.value = s.value; // 把右子樹(shù)中最小節(jié)點(diǎn)設(shè)為當(dāng)前節(jié)點(diǎn) p = s; // 這種情況實(shí)際上并沒(méi)有刪除p節(jié)點(diǎn),而是把p節(jié)點(diǎn)的值改了,實(shí)際刪除的是p的后繼節(jié)點(diǎn) } // 如果原來(lái)的當(dāng)前節(jié)點(diǎn)(p)有2個(gè)子節(jié)點(diǎn),則當(dāng)前節(jié)點(diǎn)已經(jīng)變成原來(lái)p的右子樹(shù)中的最小節(jié)點(diǎn)了,也就是說(shuō)其沒(méi)有左子節(jié)點(diǎn)了 // 到這一步,p肯定只有一個(gè)子節(jié)點(diǎn)了 // 如果當(dāng)前節(jié)點(diǎn)有子節(jié)點(diǎn),則用子節(jié)點(diǎn)替換當(dāng)前節(jié)點(diǎn) Entry<K,V> replacement = (p.left != null ? p.left : p.right); if (replacement != null) { // 把替換節(jié)點(diǎn)直接放到當(dāng)前節(jié)點(diǎn)的位置上(相當(dāng)于刪除了p,并把替換節(jié)點(diǎn)移動(dòng)過(guò)來(lái)了) replacement.parent = p.parent; if (p.parent == null) root = replacement; else if (p == p.parent.left) p.parent.left = replacement; else p.parent.right = replacement; // 將p的各項(xiàng)屬性都設(shè)為空 p.left = p.right = p.parent = null; // 如果p是黑節(jié)點(diǎn),則需要再平衡 if (p.color == BLACK) fixAfterDeletion(replacement); } else if (p.parent == null) { // 如果當(dāng)前節(jié)點(diǎn)就是根節(jié)點(diǎn),則直接將根節(jié)點(diǎn)設(shè)為空即可 root = null; } else { // 如果當(dāng)前節(jié)點(diǎn)沒(méi)有子節(jié)點(diǎn)且其為黑節(jié)點(diǎn),則把自己當(dāng)作虛擬的替換節(jié)點(diǎn)進(jìn)行再平衡 if (p.color == BLACK) fixAfterDeletion(p); // 平衡完成后刪除當(dāng)前節(jié)點(diǎn)(與父節(jié)點(diǎn)斷絕關(guān)系) if (p.parent != null) { if (p == p.parent.left) p.parent.left = null; else if (p == p.parent.right) p.parent.right = null; p.parent = null; } } }
經(jīng)過(guò)上面的處理,真正刪除的肯定是黑色節(jié)點(diǎn)才會(huì)進(jìn)入到再平衡階段。
因?yàn)閯h除的是黑色節(jié)點(diǎn),導(dǎo)致整顆樹(shù)不平衡了,所以這里我們假設(shè)把刪除的黑色賦予當(dāng)前節(jié)點(diǎn),這樣當(dāng)前節(jié)點(diǎn)除了它自已的顏色還多了一個(gè)黑色,那么:
(1)如果當(dāng)前節(jié)點(diǎn)是根節(jié)點(diǎn),則直接涂黑即可,不需要再平衡;
(2)如果當(dāng)前節(jié)點(diǎn)是紅+黑節(jié)點(diǎn),則直接涂黑即可,不需要平衡;
(3)如果當(dāng)前節(jié)點(diǎn)是黑+黑節(jié)點(diǎn),則我們只要通過(guò)旋轉(zhuǎn)把這個(gè)多出來(lái)的黑色不斷的向上傳遞到一個(gè)紅色節(jié)點(diǎn)即可,這又可能會(huì)出現(xiàn)以下四種情況:
(假設(shè)當(dāng)前節(jié)點(diǎn)為父節(jié)點(diǎn)的左子節(jié)點(diǎn))
情況 | 策略 |
---|---|
1)x是黑+黑節(jié)點(diǎn),x的兄弟是紅節(jié)點(diǎn) | (1)將兄弟節(jié)點(diǎn)設(shè)為黑色; (2)將父節(jié)點(diǎn)設(shè)為紅色; (3)以父節(jié)點(diǎn)為支點(diǎn)進(jìn)行左旋; (4)重新設(shè)置x的兄弟節(jié)點(diǎn),進(jìn)入下一步; |
2)x是黑+黑節(jié)點(diǎn),x的兄弟是黑節(jié)點(diǎn),且兄弟節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色 | (1)將兄弟節(jié)點(diǎn)設(shè)置為紅色; (2)將x的父節(jié)點(diǎn)作為新的當(dāng)前節(jié)點(diǎn),進(jìn)入下一次循環(huán); |
3)x是黑+黑節(jié)點(diǎn),x的兄弟是黑節(jié)點(diǎn),且兄弟節(jié)點(diǎn)的右子節(jié)點(diǎn)為黑色,左子節(jié)點(diǎn)為紅色 | (1)將兄弟節(jié)點(diǎn)的左子節(jié)點(diǎn)設(shè)為黑色; (2)將兄弟節(jié)點(diǎn)設(shè)為紅色; (3)以兄弟節(jié)點(diǎn)為支點(diǎn)進(jìn)行右旋; (4)重新設(shè)置x的兄弟節(jié)點(diǎn),進(jìn)入下一步; |
3)x是黑+黑節(jié)點(diǎn),x的兄弟是黑節(jié)點(diǎn),且兄弟節(jié)點(diǎn)的右子節(jié)點(diǎn)為紅色,左子節(jié)點(diǎn)任意顏色 | (1)將兄弟節(jié)點(diǎn)的顏色設(shè)為父節(jié)點(diǎn)的顏色; (2)將父節(jié)點(diǎn)設(shè)為黑色; (3)將兄弟節(jié)點(diǎn)的右子節(jié)點(diǎn)設(shè)為黑色; (4)以父節(jié)點(diǎn)為支點(diǎn)進(jìn)行左旋; (5)將root作為新的當(dāng)前節(jié)點(diǎn)(退出循環(huán)); |
(假設(shè)當(dāng)前節(jié)點(diǎn)為父節(jié)點(diǎn)的右子節(jié)點(diǎn),正好反過(guò)來(lái))
情況 | 策略 |
---|---|
1)x是黑+黑節(jié)點(diǎn),x的兄弟是紅節(jié)點(diǎn) | (1)將兄弟節(jié)點(diǎn)設(shè)為黑色; (2)將父節(jié)點(diǎn)設(shè)為紅色; (3)以父節(jié)點(diǎn)為支點(diǎn)進(jìn)行右旋; (4)重新設(shè)置x的兄弟節(jié)點(diǎn),進(jìn)入下一步; |
2)x是黑+黑節(jié)點(diǎn),x的兄弟是黑節(jié)點(diǎn),且兄弟節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色 | (1)將兄弟節(jié)點(diǎn)設(shè)置為紅色; (2)將x的父節(jié)點(diǎn)作為新的當(dāng)前節(jié)點(diǎn),進(jìn)入下一次循環(huán); |
3)x是黑+黑節(jié)點(diǎn),x的兄弟是黑節(jié)點(diǎn),且兄弟節(jié)點(diǎn)的左子節(jié)點(diǎn)為黑色,右子節(jié)點(diǎn)為紅色 | (1)將兄弟節(jié)點(diǎn)的右子節(jié)點(diǎn)設(shè)為黑色; (2)將兄弟節(jié)點(diǎn)設(shè)為紅色; (3)以兄弟節(jié)點(diǎn)為支點(diǎn)進(jìn)行左旋; (4)重新設(shè)置x的兄弟節(jié)點(diǎn),進(jìn)入下一步; |
3)x是黑+黑節(jié)點(diǎn),x的兄弟是黑節(jié)點(diǎn),且兄弟節(jié)點(diǎn)的左子節(jié)點(diǎn)為紅色,右子節(jié)點(diǎn)任意顏色 | (1)將兄弟節(jié)點(diǎn)的顏色設(shè)為父節(jié)點(diǎn)的顏色; (2)將父節(jié)點(diǎn)設(shè)為黑色; (3)將兄弟節(jié)點(diǎn)的左子節(jié)點(diǎn)設(shè)為黑色; (4)以父節(jié)點(diǎn)為支點(diǎn)進(jìn)行右旋; (5)將root作為新的當(dāng)前節(jié)點(diǎn)(退出循環(huán)); |
讓我們來(lái)看看TreeMap中的實(shí)現(xiàn):
/** * 刪除再平衡 *(1)每個(gè)節(jié)點(diǎn)或者是黑色,或者是紅色。 *(2)根節(jié)點(diǎn)是黑色。 *(3)每個(gè)葉子節(jié)點(diǎn)(NIL)是黑色。(注意:這里葉子節(jié)點(diǎn),是指為空(NIL或NULL)的葉子節(jié)點(diǎn)?。? *(4)如果一個(gè)節(jié)點(diǎn)是紅色的,則它的子節(jié)點(diǎn)必須是黑色的。 *(5)從一個(gè)節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)。 */ private void fixAfterDeletion(Entry<K,V> x) { // 只有當(dāng)前節(jié)點(diǎn)不是根節(jié)點(diǎn)且當(dāng)前節(jié)點(diǎn)是黑色時(shí)才進(jìn)入循環(huán) while (x != root && colorOf(x) == BLACK) { if (x == leftOf(parentOf(x))) { // 如果當(dāng)前節(jié)點(diǎn)是其父節(jié)點(diǎn)的左子節(jié)點(diǎn) // sib是當(dāng)前節(jié)點(diǎn)的兄弟節(jié)點(diǎn) Entry<K,V> sib = rightOf(parentOf(x)); // 情況1)如果兄弟節(jié)點(diǎn)是紅色 if (colorOf(sib) == RED) { // (1)將兄弟節(jié)點(diǎn)設(shè)為黑色 setColor(sib, BLACK); // (2)將父節(jié)點(diǎn)設(shè)為紅色 setColor(parentOf(x), RED); // (3)以父節(jié)點(diǎn)為支點(diǎn)進(jìn)行左旋 rotateLeft(parentOf(x)); // (4)重新設(shè)置x的兄弟節(jié)點(diǎn),進(jìn)入下一步 sib = rightOf(parentOf(x)); } if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) { // 情況2)如果兄弟節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色 // (1)將兄弟節(jié)點(diǎn)設(shè)置為紅色 setColor(sib, RED); // (2)將x的父節(jié)點(diǎn)作為新的當(dāng)前節(jié)點(diǎn),進(jìn)入下一次循環(huán) x = parentOf(x); } else { if (colorOf(rightOf(sib)) == BLACK) { // 情況3)如果兄弟節(jié)點(diǎn)的右子節(jié)點(diǎn)為黑色 // (1)將兄弟節(jié)點(diǎn)的左子節(jié)點(diǎn)設(shè)為黑色 setColor(leftOf(sib), BLACK); // (2)將兄弟節(jié)點(diǎn)設(shè)為紅色 setColor(sib, RED); // (3)以兄弟節(jié)點(diǎn)為支點(diǎn)進(jìn)行右旋 rotateRight(sib); // (4)重新設(shè)置x的兄弟節(jié)點(diǎn) sib = rightOf(parentOf(x)); } // 情況4) // (1)將兄弟節(jié)點(diǎn)的顏色設(shè)為父節(jié)點(diǎn)的顏色 setColor(sib, colorOf(parentOf(x))); // (2)將父節(jié)點(diǎn)設(shè)為黑色 setColor(parentOf(x), BLACK); // (3)將兄弟節(jié)點(diǎn)的右子節(jié)點(diǎn)設(shè)為黑色 setColor(rightOf(sib), BLACK); // (4)以父節(jié)點(diǎn)為支點(diǎn)進(jìn)行左旋 rotateLeft(parentOf(x)); // (5)將root作為新的當(dāng)前節(jié)點(diǎn)(退出循環(huán)) x = root; } } else { // symmetric // 如果當(dāng)前節(jié)點(diǎn)是其父節(jié)點(diǎn)的右子節(jié)點(diǎn) // sib是當(dāng)前節(jié)點(diǎn)的兄弟節(jié)點(diǎn) Entry<K,V> sib = leftOf(parentOf(x)); // 情況1)如果兄弟節(jié)點(diǎn)是紅色 if (colorOf(sib) == RED) { // (1)將兄弟節(jié)點(diǎn)設(shè)為黑色 setColor(sib, BLACK); // (2)將父節(jié)點(diǎn)設(shè)為紅色 setColor(parentOf(x), RED); // (3)以父節(jié)點(diǎn)為支點(diǎn)進(jìn)行右旋 rotateRight(parentOf(x)); // (4)重新設(shè)置x的兄弟節(jié)點(diǎn) sib = leftOf(parentOf(x)); } if (colorOf(rightOf(sib)) == BLACK && colorOf(leftOf(sib)) == BLACK) { // 情況2)如果兄弟節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色 // (1)將兄弟節(jié)點(diǎn)設(shè)置為紅色 setColor(sib, RED); // (2)將x的父節(jié)點(diǎn)作為新的當(dāng)前節(jié)點(diǎn),進(jìn)入下一次循環(huán) x = parentOf(x); } else { if (colorOf(leftOf(sib)) == BLACK) { // 情況3)如果兄弟節(jié)點(diǎn)的左子節(jié)點(diǎn)為黑色 // (1)將兄弟節(jié)點(diǎn)的右子節(jié)點(diǎn)設(shè)為黑色 setColor(rightOf(sib), BLACK); // (2)將兄弟節(jié)點(diǎn)設(shè)為紅色 setColor(sib, RED); // (3)以兄弟節(jié)點(diǎn)為支點(diǎn)進(jìn)行左旋 rotateLeft(sib); // (4)重新設(shè)置x的兄弟節(jié)點(diǎn) sib = leftOf(parentOf(x)); } // 情況4) // (1)將兄弟節(jié)點(diǎn)的顏色設(shè)為父節(jié)點(diǎn)的顏色 setColor(sib, colorOf(parentOf(x))); // (2)將父節(jié)點(diǎn)設(shè)為黑色 setColor(parentOf(x), BLACK); // (3)將兄弟節(jié)點(diǎn)的左子節(jié)點(diǎn)設(shè)為黑色 setColor(leftOf(sib), BLACK); // (4)以父節(jié)點(diǎn)為支點(diǎn)進(jìn)行右旋 rotateRight(parentOf(x)); // (5)將root作為新的當(dāng)前節(jié)點(diǎn)(退出循環(huán)) x = root; } } } // 退出條件為多出來(lái)的黑色向上傳遞到了根節(jié)點(diǎn)或者紅節(jié)點(diǎn) // 則將x設(shè)為黑色即可滿足紅黑樹(shù)規(guī)則 setColor(x, BLACK); }
假設(shè)我們有下面這樣一顆紅黑樹(shù)。
我們刪除6號(hào)元素,則從右子樹(shù)中找到了最小元素7,7又沒(méi)有子節(jié)點(diǎn)了,所以把7作為當(dāng)前節(jié)點(diǎn)進(jìn)行再平衡。
我們看到7是黑節(jié)點(diǎn),且其兄弟為黑節(jié)點(diǎn),且其兄弟的兩個(gè)子節(jié)點(diǎn)都是紅色,滿足情況4),平衡之后如下圖所示。
我們?cè)賱h除7號(hào)元素,則從右子樹(shù)中找到了最小元素8,8有子節(jié)點(diǎn)且為黑色,所以8的子節(jié)點(diǎn)9是替代節(jié)點(diǎn),以9為當(dāng)前節(jié)點(diǎn)進(jìn)行再平衡。
我們發(fā)現(xiàn)9是紅節(jié)點(diǎn),則直接把它涂成黑色即滿足了紅黑樹(shù)的特性,不需要再過(guò)多的平衡了。
這次我們來(lái)個(gè)狠的,把根節(jié)點(diǎn)刪除,從右子樹(shù)中找到了最小的元素5,5沒(méi)有子節(jié)點(diǎn),所以把5作為當(dāng)前節(jié)點(diǎn)進(jìn)行再平衡。
我們看到5是黑節(jié)點(diǎn),且其兄弟為紅色,符合情況1),平衡之后如下圖所示,然后進(jìn)入情況2)。
對(duì)情況2)進(jìn)行再平衡后如下圖所示。
然后進(jìn)入下一次循環(huán),發(fā)現(xiàn)不符合循環(huán)條件了,直接把x涂為黑色即可,退出這個(gè)方法之后會(huì)把舊x刪除掉(見(jiàn)deleteEntry()方法),最后的結(jié)果就是下面這樣。
我們知道二叉查找樹(shù)的遍歷有前序遍歷、中序遍歷、后序遍歷。
(1)前序遍歷,先遍歷我,再遍歷我的左子節(jié)點(diǎn),最后遍歷我的右子節(jié)點(diǎn);
(2)中序遍歷,先遍歷我的左子節(jié)點(diǎn),再遍歷我,最后遍歷我的右子節(jié)點(diǎn);
(3)后序遍歷,先遍歷我的左子節(jié)點(diǎn),再遍歷我的右子節(jié)點(diǎn),最后遍歷我;
這里的前中后都是以“我”的順序?yàn)闇?zhǔn)的,我在前就是前序遍歷,我在中就是中序遍歷,我在后就是后序遍歷。
下面讓我們看看經(jīng)典的中序遍歷是怎么實(shí)現(xiàn)的:
public class TreeMapTest { public static void main(String[] args) { // 構(gòu)建一顆10個(gè)元素的樹(shù) TreeNode<Integer> node = new TreeNode<>(1, null).insert(2) .insert(6).insert(3).insert(5).insert(9) .insert(7).insert(8).insert(4).insert(10); // 中序遍歷,打印結(jié)果為1到10的順序 node.root().inOrderTraverse(); } } /** * 樹(shù)節(jié)點(diǎn),假設(shè)不存在重復(fù)元素 * @param <T> */ class TreeNode<T extends Comparable<T>> { T value; TreeNode<T> parent; TreeNode<T> left, right; public TreeNode(T value, TreeNode<T> parent) { this.value = value; this.parent = parent; } /** * 獲取根節(jié)點(diǎn) */ TreeNode<T> root() { TreeNode<T> cur = this; while (cur.parent != null) { cur = cur.parent; } return cur; } /** * 中序遍歷 */ void inOrderTraverse() { if(this.left != null) this.left.inOrderTraverse(); System.out.println(this.value); if(this.right != null) this.right.inOrderTraverse(); } /** * 經(jīng)典的二叉樹(shù)插入元素的方法 */ TreeNode<T> insert(T value) { // 先找根元素 TreeNode<T> cur = root(); TreeNode<T> p; int dir; // 尋找元素應(yīng)該插入的位置 do { p = cur; if ((dir=value.compareTo(p.value)) < 0) { cur = cur.left; } else { cur = cur.right; } } while (cur != null); // 把元素放到找到的位置 if (dir < 0) { p.left = new TreeNode<>(value, p); return p.left; } else { p.right = new TreeNode<>(value, p); return p.right; } } }
從上面二叉樹(shù)的遍歷我們很明顯地看到,它是通過(guò)遞歸的方式實(shí)現(xiàn)的,但是遞歸會(huì)占用額外的空間,直接到線程棧整個(gè)釋放掉才會(huì)把方法中申請(qǐng)的變量銷毀掉,所以當(dāng)元素特別多的時(shí)候是一件很危險(xiǎn)的事。
(上面的例子中,沒(méi)有申請(qǐng)額外的空間,如果有聲明變量,則可以理解為直到方法完成才會(huì)銷毀變量)
那么,有沒(méi)有什么方法不用遞歸呢?
讓我們來(lái)看看java中的實(shí)現(xiàn):
@Override public void forEach(BiConsumer<? super K, ? super V> action) { Objects.requireNonNull(action); // 遍歷前的修改次數(shù) int expectedModCount = modCount; // 執(zhí)行遍歷,先獲取第一個(gè)元素的位置,再循環(huán)遍歷后繼節(jié)點(diǎn) for (Entry<K, V> e = getFirstEntry(); e != null; e = successor(e)) { // 執(zhí)行動(dòng)作 action.accept(e.key, e.value); // 如果發(fā)現(xiàn)修改次數(shù)變了,則拋出異常 if (expectedModCount != modCount) { throw new ConcurrentModificationException(); } } }
是不是很簡(jiǎn)單?!
(1)尋找第一個(gè)節(jié)點(diǎn);
從根節(jié)點(diǎn)開(kāi)始找最左邊的節(jié)點(diǎn),即最小的元素。
final Entry<K,V> getFirstEntry() { Entry<K,V> p = root; // 從根節(jié)點(diǎn)開(kāi)始找最左邊的節(jié)點(diǎn),即最小的元素 if (p != null) while (p.left != null) p = p.left; return p; }
(2)循環(huán)遍歷后繼節(jié)點(diǎn);
尋找后繼節(jié)點(diǎn)這個(gè)方法我們?cè)趧h除元素的時(shí)候也用到過(guò),當(dāng)時(shí)的場(chǎng)景是有右子樹(shù),則從其右子樹(shù)中尋找最小的節(jié)點(diǎn)。
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) { if (t == null) // 如果當(dāng)前節(jié)點(diǎn)為空,返回空 return null; else if (t.right != null) { // 如果當(dāng)前節(jié)點(diǎn)有右子樹(shù),取右子樹(shù)中最小的節(jié)點(diǎn) Entry<K,V> p = t.right; while (p.left != null) p = p.left; return p; } else { // 如果當(dāng)前節(jié)點(diǎn)沒(méi)有右子樹(shù) // 如果當(dāng)前節(jié)點(diǎn)是父節(jié)點(diǎn)的左子節(jié)點(diǎn),直接返回父節(jié)點(diǎn) // 如果當(dāng)前節(jié)點(diǎn)是父節(jié)點(diǎn)的右子節(jié)點(diǎn),一直往上找,直到找到一個(gè)祖先節(jié)點(diǎn)是其父節(jié)點(diǎn)的左子節(jié)點(diǎn)為止,返回這個(gè)祖先節(jié)點(diǎn)的父節(jié)點(diǎn) Entry<K,V> p = t.parent; Entry<K,V> ch = t; while (p != null && ch == p.right) { ch = p; p = p.parent; } return p; } }
讓我們一起來(lái)分析下這種方式的時(shí)間復(fù)雜度吧。
首先,尋找第一個(gè)元素,因?yàn)榧t黑樹(shù)是接近平衡的二叉樹(shù),所以找最小的節(jié)點(diǎn),相當(dāng)于是從頂?shù)降琢?,時(shí)間復(fù)雜度為O(log n);
其次,尋找后繼節(jié)點(diǎn),因?yàn)榧t黑樹(shù)插入元素的時(shí)候會(huì)自動(dòng)平衡,最壞的情況就是尋找右子樹(shù)中最小的節(jié)點(diǎn),時(shí)間復(fù)雜度為O(log k),k為右子樹(shù)元素個(gè)數(shù);
最后,需要遍歷所有元素,時(shí)間復(fù)雜度為O(n);
所以,總的時(shí)間復(fù)雜度為 O(log n) + O(n * log k) ≈ O(n)。
雖然遍歷紅黑樹(shù)的時(shí)間復(fù)雜度是O(n),但是它實(shí)際是要比跳表要慢一點(diǎn)的。
關(guān)于“JDK中如何刪除元素”這篇文章就分享到這里了,希望以上內(nèi)容可以對(duì)大家有一定的幫助,使各位可以學(xué)到更多知識(shí),如果覺(jué)得文章不錯(cuò),請(qǐng)把它分享出去讓更多的人看到。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。