二叉搜索樹更新

Question

我正在開發一個需要將值存儲在二叉搜索樹中的應用程序。這是一些類似於通過將每行存儲爲一個鍵值來實現textpad的應用程序。如果刪除一行，則在O（n）中更新之後的行的鍵。通過考慮類似於行號的參數（在該示例中）作爲密鑰，我能夠在我的應用程序中實現O（n）時間。

有沒有辦法通過選擇其他鍵來實現O（log n）時間？

Answer 1

如果您需要保證O(logN) peformance從二叉樹你應該使用自平衡版本，例如， Splay Tree或Red black tree

Answer 2

如果您的要求是插入/更新，刪除和搜索，然後嘗試Hash Table具有良好的散列函數。許多語言提供散列表實現unordered_map在C++中，dict在python中，{}在javascript中...哦，順便說一句，你可以自己寫一個。

此外，你可以嘗試一些平衡bst O(log(n))像紅黑樹，avl樹，2-3樹。