Splay Tree Deletion

user_8214951 0
Viewed 132

I'm having trouble conceptualising the process of deletion from a splay tree. Given this intial, tree, I want to delete the node 78.

splay tree initial

Based on the information from my course (derived from Goodrich, Tamassia and Goldwasser), the deleted node in a BST should be replaced by the next node reached by performing an in-order traversal from the node which should be 91. This node should then be splayed to the top of the tree. However, this is not the case as shown on this visualiser here. https://www.cs.usfca.edu/~galles/visualization/SplayTree.html

enter image description here

tree data-structures algorithm
1 Answers

The visualizer replaced 78 by its in order predecessor (70) instead and splayed that node. (The in order successor, i.e., the next key in sorted order is 83, not 91.) In general, splay trees are wonderfully malleable and as long as you approximately halve the length of the path you just descended while making every other path at most a little bit longer, you’re doing it right from an asymptotic performance standpoint (your professor may have different ideas, however).

user_21446690
Related