Those data structures can not learn from Leetcode — Splay Tree

Not grantee 100% balanced yet still useful. explained step by step.

Beginning

Continuing with advanced DSA topic: Skip list, B Tree Step by Step, Treap, Red-Black Tree, AVL

In this post, I will go over the process of the Splay tree.

Unlike other Self-Balancing BST. Splay Tree is not granted to be balanced. but it’s very simple to implement (compared to Red-Black, AVL, or 2–3–4)

Definition

In the Splay tree, recently accessed elements are quick to access again. all normal operations on a binary search tree are combined with one basic operation, called splaying . Splaying the tree for a certain element rearranges the tree so that the element is placed at the root of the tree.

From the definition, I find the idea very interesting: every accessed node will be placed at the root. (that’s a smell of cache)

Let’s dive into the details.

Insertion

insert 10

The only node. nothing to do.

insert 5

2 nodes, and yes, looks already balanced (left and right height difference ≤1), but not finished yet. based on the definition of Splay Tree, the newly inserted node needs to be placed at the root. so again, rotation happens (same as other self-balancing BST). let’s call this case “zig” (recall how the…