Splay树删除
Splay Tree Deletion
我无法概念化从 splay 树中删除的过程。给定这个初始树，我想删除节点 78。
根据我课程中的信息（来自 Goodrich、Tamassia 和 Goldwasser），BST 中删除的节点应替换为从节点执行顺序遍历到达的下一个节点，该节点应为 91 . 然后这个节点应该展开到树的顶部。但是，此处的可视化工具显示的情况并非如此。 https://www.cs.usfca.edu/~galles/visualization/SplayTree.html
可视化工具将 78 替换为其顺序前身 (70)，并展开该节点。 （顺序后继，即排序顺序中的下一个键是 83，而不是 91。）通常，八字树具有极好的可塑性，只要您将刚刚下降的路径的长度大约减半，同时使所有其他路径都在最多一点点，从渐近性能的角度来看，你是正确的（但是，你的教授可能有不同的想法）。
我无法概念化从 splay 树中删除的过程。给定这个初始树，我想删除节点 78。
根据我课程中的信息（来自 Goodrich、Tamassia 和 Goldwasser），BST 中删除的节点应替换为从节点执行顺序遍历到达的下一个节点，该节点应为 91 . 然后这个节点应该展开到树的顶部。但是，此处的可视化工具显示的情况并非如此。 https://www.cs.usfca.edu/~galles/visualization/SplayTree.html
可视化工具将 78 替换为其顺序前身 (70)，并展开该节点。 （顺序后继，即排序顺序中的下一个键是 83，而不是 91。）通常，八字树具有极好的可塑性，只要您将刚刚下降的路径的长度大约减半，同时使所有其他路径都在最多一点点，从渐近性能的角度来看，你是正确的（但是，你的教授可能有不同的想法）。