tailieunhanh - Data Structures and Program Design in C++ phần 8

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 .

• Kỹ thuật lập trình
• thủ thuật hệ điều hành
• tìm hiểu hệ điều hành
• thủ thuật windows
• lập trình windows
• lập trình ứng dụng
• lập trình máy tính
• thủ thuật lập trình
• mẹo hay cho lập trình
• bí quyết lập trình
• thủ thuật máy tính
• phần mềm máy tính
• quản trị hệ thống
• hệ điều hành linux
• hệ điều hành mac
• mẹo cài hệ điều hành
• hệ điều hành unix
• hệ điều hành windows
• kỹ năng máy tính
• Hệ Điều Hành
• các hệ điều hành Windows
• giáo trình hệ điều hành
• các vấn đề hệ điều hành
• tài liệu hệ điều hành
• Tổng quan về hệ điều hành
• windows 7
• Refresh hệ điều hành Android
• Hệ điều hành Android cũ
• Hệ điều hành Android
• Cài đặt hệ điều hành Android
• Thủ thuật hệ điều hành Android
• Khôi phục hệ điều hành Android
• đồ họa máy tính
• mỹ thuật đa truyền thông
• học hệ điều hành
• cách sử dụng hệ điều hành
• hệ điều hành windows 7
• mẹo hay hệ điều hành