Lecture Note
University
University of California San DiegoCourse
CSE 100R | Advanced Data StructuresPages
2
Academic year
9
anon
Views
25
Understanding Splay Trees' Mathematical Basis. Self-balancing binary search trees of the splay tree variety are frequently employed in computer science. They are renowned for their swift operationtimes, which makes a variety of applications possible. To fully appreciate thepotential of these trees, it is necessary to comprehend the underlyingmathematical ideas. The arithmetic underlying splay trees, including thepotential function and the amortized cost of operations, will be examined inmore detail in this article. The Possible Purpose When examining splay trees, the potential function is a key idea. It aids in figuring out a tree's equilibrium, which is important for figuring out how wellthe tree will perform. The potential function is described as the total of all thetree nodes' ranks. The size of a node's subtree, which is the number of nodesthat are its descendants in the tree, is used to calculate the rank of a node. The potential function of a balanced tree will be roughly linear in the total number of nodes. The potential function of an unbalanced tree, on the otherhand, will be substantially larger and may even reach N(log(n)), where n is thetotal number of nodes in the tree. Thus, a tree's potential function being reducedindicates that the tree is getting more balanced. The Operational Amortized Cost It's crucial to take into account the amortized cost of any operations you do on a splay tree. The average cost of an operation across a series of operationsis what is known as the amortized cost of that operation. The amortized cost ofperforming O(D) work and then splaying a node of depth D in the context ofsplay trees is O(log(n)), where n is the total number of nodes in the tree. This outcome is attained by compensating for the additional labor necessary by simplifying the tree in some way. The potential function is atechnique for figuring out how simple the tree is. The tree becomes morebalanced as the potential function is reduced, which lowers the cost ofoperations.
Zig and Zig-Zig Operations The processes that make up splay trees include zig and zig-zig operations. To calculate these actions' amortized costs, it is crucial to comprehend how theyalter the tree's potential functionality. The new rank of the node being spread plus the new rank of its parent, less the old rank of the node and its parent, is all that changes in the potentialfunction during a zag operation. This calculation is rather simple because boththe parent and the node's new rank are unaffected. It is a little more difficult to modify the potential function during a zig-zag operation. The new ranks of the node being spread, its parent, and itsgrandparent are added together, less their previous ranks, to determine thepossible change. This shift is no more than three times the node's new rank lessits former rank, which is divided by two. This conclusion is supported by anumber of observations, including the fact that no other nodes in the tree hadtheir subtrees altered as a result of the operation. Splay trees are a crucial tool in computer science because they provide quick processing times for a variety of applications. However, it's crucial tocomprehend the mathematics underlying these trees in order to fully appreciatetheir powers. This contains the amortized cost of operations, a crucialcomponent of splay, and the potential function, which is used to calculate atree's balance.
Unveiling the Mathematical Foundations of Splay Trees
Please or to post comments