COMPUTER SCIENCE AND ENGINEERING
DATA STRUCTURES
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
Zig-zag rotation is required to splay the node H
|
|
|
Zig-zag rotation is required to splay the node V
|
|
|
Zig-zag rotation is required to splay the node W
|
|
|
Zig-zag rotation is required to splay the node S
|
Detailed explanation-1: -Zig rotation: This rotation is similar to the right rotation in the AVL tree. In zig rotation, every node moves one position to the right of its current position. We use Zig rotation when the item which is to be searched is either a root node or a left child of the root node.
Detailed explanation-2: -There are six types of rotations used for splaying: Zig rotation (Right rotation) Zag rotation (Left rotation) Zig zag (Zig followed by zag) Zag zig (Zag followed by zig)
Detailed explanation-3: -Result of Analysis: Any sequence of M operations on a splay tree of size N takes O(M log N) time.
Detailed explanation-4: -Insertion Operation in Splay Tree Step 1-Check whether tree is Empty. Step 2-If tree is Empty then insert the newNode as Root node and exit from the operation. Step 3-If tree is not Empty then insert the newNode as leaf node using Binary Search tree insertion logic.