朴素 BST 如何删除节点?
查看原帖
朴素 BST 如何删除节点?
285856
awdec楼主2024/7/23 22:32

虽然本题中没有,但是复习平衡树的时候突然意识到这个问题。

我想到两个办法:

  • 和替罪羊树一样,惰性删除,维护东西要稍微变一下。
  • 和 Treap 一样,把点转下去删除(和 Treap 的区别大概就在于 Treap 要按照堆的性质转,朴素 BST 可以左右儿子随便选一个转)
2024/7/23 22:32
加载中...