Purchasing System

Advanced Algorithm Splay Tree Algorithm

What is Splay Tree?

A balanced search tree data structure Splay trees are self branching binary search tree which has the property of re-accessing the elements quickly that which are recently accessed. A node in a Binary_Search_Tree is "splayed" when it is moved to the root of the tree by one or more "rotations". A binary search tree in which operations that access nodes restructure the tree. A binary tee with splaying.

Algorithm

Splay trees are self adjusting binary search trees which performs basic operations such as

Search Insertion Deletion

Search, Insert, Delete operations are like in Binary Search trees except at the end of each operation, a special step called Splaying is done. Splaying the tree rearranges the tree so that element is placed at the root of the tree. It uses tree rotations to bring the element to the top.

Operations

The main basic operations of the Splay tree are: Search Insert Delete Splaying

When to Splay

Search:

Successful: Splay node where key was found. Unsuccessful: Splay last-visited internal node (i.e., last node with a key).

Insert:

Splay newly added node.

Delete:

Splay parent of removed node (which is either the node with the deleted key or its successor).

Splay Tree Rotations (1)

Zig: Rotate the node about its parent (left or right). These are called Zig_Left and Zig_Right Rules: In this case, P is the root of the tree. 1. Zig_Left( X ) if X is a left child. 2. Zig_Right( X ) if X is a right child.

P

X

A B C A B

X P

C A

P X

B C A

X P

B

C

ZIG_LEFT

ZIG_RIGHT

Zig splaying

• Example: x is 20, y is 10, u is 30

Before Splaying

10

T1 T2 T3

After Splaying

20

30

T4 T1

20 10

T2 T3

30

T4

Splay Tree Rotations (2)

Zig_Zig: Rotate the parent about the grandparent (left or right), then rotate the node about its parent in the same direction. These are called Zig_Zig_Left or Zig_Zig_Right Rules: In this...