## Height Balanced Tree

A height-balanced tree is a binary search tree where the height of the left and right subtrees of every node differs by at most one. The aim of a height-balanced tree is to reduce the time complexity of search, insertion, and deletion operations by ensuring that the height of the tree is always logarithmic in the number of nodes.

## Splay Tree

A splay tree is a self-adjusting binary search tree that utilizes the principle of locality of reference. The splay tree reorganizes its structure based on the recent history of accessed nodes to improve the efficiency of access to frequently accessed nodes.

The splay tree performs splaying operations to move a node accessed to the root of the tree. Splaying is performed by a series of rotations, where the accessed node is rotated upwards to the root, and its ancestors are rotated downwards to maintain the order of the tree.

**Insertion Operation on Splay Tree:**

- Search for the key in the splay tree. If the key is found, splay the node to the root. If not found, create a new node with the key and perform a splay operation on it to make it the root of the tree.
- If the splay tree is empty, then insert the new node as the root.
- If the key is less than the root node key, insert it in the left subtree of the root. Otherwise, insert it in the right subtree of the root.
- After insertion, perform a splay operation on the new node to make it the root of the tree.

**Deletion Operation on Splay Tree:**

- Search for the node to be deleted in the splay tree. If the node is found, splay the node to the root. If not found, return.
- If the node has two children, find the node with the maximum key in the left subtree or the node with the minimum key in the right subtree. Splay the found node to the root, and then remove the node to be deleted.
- If the node has one child, replace the node with its child, and then splay the child node to the root.
- If the node has no child, remove the node from the tree.

The deletion operation on a splay tree also involves splaying the nodes to maintain the balance of the tree.

In conclusion, splay trees are self-adjusting binary search trees that are optimized for frequently accessed nodes. The insertion and deletion operations on splay trees involve searching for the node, splaying the node to the root, and then performing the required operations to maintain the balance of the tree. The splay tree is an efficient data structure for a wide range of applications where frequently accessed nodes are critical to performance.

- Q-1.
- What do you understand by time and space complexity? What is asymptotic notation? Why it is important? Discuss using suitable example.
- Q-2.
- What is recurrence? Discuss in detail the master method for solving a recurrence.
- Q-3
- What is a Travelling Salesman problem? Discuss the greedy algorithm for solving the Travelling Salesman Problem.
- Q-4
- What do you understand by height balanced tree? What is a splay tree? Discuss the insertion/deletion operation on splay tree.
- Q-5
- What is Minimum Spanning Tree? Discuss the Steps for finding Minimum Spanning Tree using Kruskal’s Algorithm.
- Q-6
- What is a Graph? Discuss the depth first traversal of a graph and its computational complexity. Also discuss the topological sort using depth first traversal.
- Q-7
- What is a flow network? Explain Ford-Fulkerson Algorithm for Maximum Flow Problem.
- Q-8
- What is bitonic sequence? What is merging network? Explain.