Tree rotation

As explained in Advanced Algorithms and Data Structures

A tree rotation is a local restructuring operation that changes parent-child relationships while preserving the in-order sequence of a binary search tree.

A treap must keep its keys in binary-search-tree order while also satisfying a priority rule. After an insertion, a new leaf may be in the right place by key but the wrong place by priority. Swapping it with its parent could break key order; a rotation moves it up while preserving that order. section 3.3.1 section 3.3.4

A rotation reverses one parent–child relationship and reconnects the subtree between the two nodes:

• Right rotation: the left child X takes its parent Y’s place. Connect X’s former right subtree as Y’s left subtree, then make Y the right child of X. section 3.3.1
• Left rotation: the right child X takes Y’s place. Connect X’s former left subtree as Y’s right subtree, then make Y the left child of X. section 3.3.1
• In either direction, reconnect Y’s former parent to X—or update the tree’s root if Y was the root. An implementation must also keep parent links consistent. section 3.3.1

Moving a treap node

To insert an inventory entry, first place it as a BST leaf. If its priority violates the rule relative to its parent, rotate the new node upward; repeat if necessary. To delete an entry, rotate its highest-priority child upward until the entry becomes a leaf, then disconnect it. These are opposite uses of the same local operation. section 3.3.4 section 3.3.5

With pointer-linked nodes, one rotation changes a fixed number of links and takes constant time. A full insertion or deletion may need several rotations. Rotations can also make a tree less balanced, so a rotation alone is not a balancing guarantee. They are awkward for array-backed trees because moving the affected subtree can require linear-time work. section 3.3.1 section 3.3.2 section 3.4.1

Figure 3.5 The algorithm for performing a right rotation on a BST illustrated

Follow the right-rotation diagram to see where the child, parent, and intervening subtree reconnect. section 3.3.1

How Advanced Algorithms and Data Structures covers it

How deep it goes

Works through both rotation directions and their pointer updates, then applies repeated rotations to treap insertion and deletion.

Examples

Uses an inventory insertion that rotates a new leaf upward and a deletion that rotates an entry down to a leaf.

What it assumes

Assumes binary-search-tree key ordering and node links, but develops the rotation operation before using it in treap updates.

What you can do after

Build it from scratch by reconnecting parent and child links for left or right rotation, including a possible root change.

How it connects

Connects binary search trees, treaps, heap invariants, priority updates, and balanced trees.

liveBookmanning.com

Read Advanced Algorithms and Data Structures on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Grokking Algorithms, Second EditionA tree rotation is a local restructuring operation that changes parent-child relationships while preserving the tree's ordering.

Compare how 2 books explain tree rotation →

Related concepts

• treapused by · A treap is a randomized binary search tree whose nodes satisfy both binary-search-tree ordering by key and heap ordering by priority.
• AVL treeused by · An AVL tree is a self-balancing binary search tree that maintains bounded differences between subtree heights through rotations.
• heap invariantcontrasts with · A heap invariant is the ordering constraint requiring each node's value or priority to be properly ordered relative to its parent or children.
• binary search treeuses · A binary search tree is a binary tree whose nodes follow an ordering relation placing keys in designated left and right subtrees relative to each node.
• right rotationincludes · A right rotation is a binary-search-tree rotation in which a node's left child becomes the root of the rotated subtree.

This explainer was generated by Manning's knowledge graph from the text of Advanced Algorithms and Data Structures. The section links point to the parts of the book it draws on.