1. 首頁
  2. 問答
  3. 可能更新紅黑樹中的節點密鑰，而不刪除並插入？

可能更新紅黑樹中的節點密鑰，而不刪除並插入？

2014-03-27 40 views
1

通常，需要通過刪除然後重新插入節點來執行對紅黑樹中的鍵的更改。可能更新紅黑樹中的節點密鑰，而不刪除並插入？

是否有可能對紅黑樹中的某個節點執行密鑰更新，這比刪除+插入更有效？

來源

2014-03-27 Ned

+0

什麼是關鍵更新？刪除一個鍵值對，重新插入一個新的鍵下的值？ – delnan

+0

@delnan通常使用重新插入 - 有時候就地更新會更快。這是一個有趣的問題！ - 有沒有人試過這個？ – ideasman42

回答

1

實現與更新[搜索如果需要+]刪除+插入

1 - 刪除鍵O（log n）的
2 - 插入用新密鑰O的新節點（log n）的
即使您首先搜索密鑰，它也是O（log n）。

有關RBT的更多詳細信息，請參閱this頁面。

來源

2014-03-27 10:05:42 mok

+0

這個答案似乎不完整，算法至少可以檢查訂單是否與其他節點相關。雖然我不知道它是否可能，但似乎有理由認爲某些操作可能在沒有完全刪除+插入的情況下執行。 – ideasman42

相關問題

 相關問題