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:

  1. 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.
  2. If the splay tree is empty, then insert the new node as the root.
  3. 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.
  4. After insertion, perform a splay operation on the new node to make it the root of the tree.

Deletion Operation on Splay Tree:

  1. 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.
  2. 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.
  3. If the node has one child, replace the node with its child, and then splay the child node to the root.
  4. 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.