如何從Lisp中的二叉搜索樹中刪除

Question

如何從BST中刪除節點？

我需要一個算法來做博士計劃。

Answer 1

你基本上折騰了你現在的BST，並創建一個新的無效的元素。

您可以通過遞歸降序樹來完成此操作。如果您的項目小於根目錄數據，請創建一個BST，其根目錄和大於分支從您現在擁有的內容中複製而來，但其小於分支是遞歸調用的結果。

這與添加節點非常相似，但是當您找到正在搜索的節點時，請合併它下面的兩個BST並返回結果。目前確實存在關於如何做到這一點的問題。

Answer 2

假設你的二叉搜索樹使用直線前進利弊細胞，僅在葉的內容，並假設您正在處理一個家庭作業： 您可以使用set-car!或set-cdr!改變利弊單元格的內容。