Do đó, nếu bạn chạy các chức năng splaying chúng ta sẽ phát triển trên cây ví dụ, bạn sẽ có được kết quả tương tự như làm splaying từ dưới lên bằng tay khi mục tiêu là chuyển một số thậm chí của các cấp, nhưng kết quả sẽ khác nhau khi nó di chuyển một số lẻ của các cấp. | Section Splay Trees A Self-Adjusting Data Structure 495 Hence if you run the splaying function we shall develop on the example trees you will obtain the same results as doing bottom-up splaying by hand when the target is moved an even number of levels but the results will be different when it moves an odd number of levels. Algorithm Development We shall develop only one splaying function that can be used both for retrieval 382 and for insertion. Given a target key the function will search through the tree for the key splaying as it goes. If it finds the key then it retrieves it if not then the function inserts it as a new node. In either case the node with the target key ends up as the root of the tree. We shall implement splay trees as a derived class of the class Search_tree so that in addition to the special splay method all of the usual Search_tree methods can be applied to splay trees. The class specification follows template class Record class Splay_tree public Search_tree Record public Error_code splay const Record target private Add auxiliary function prototypes here. A splay tree does not keep track of heights and does not use any balance factors like an AVL tree. three-way tree split three-way invariant 1. Three-Way Tree Partition Top-down splaying uses the same moves zig-zig zig-zag and the rest illustrated in Figure but while splaying proceeds the root must be left empty so that at the end the target node can be moved or inserted directly into the root. Hence while splaying proceeds the tree temporarily falls apart into separate subtrees which are reconnected after the target is made the root. We shall use three subtrees as follows The central subtree contains nodes within which the target will lie if it is present. The smaller-key subtree contains nodes with keys strictly less than the target in fact every key in the smaller-key subtree is less than every key in the central subtree. The larger-key subtree contains nodes with keys .
