CODEWITHSUNDEEP
binary-treeavl-treeproof
guardianfecal
guardianfecal

Reputation: 1

What is the simplest AVL tree structure to demonstrate a complete right rotation?

I'm learning about AVL trees and their rotations in data structures. I wish my lectures had showcased the simplest complete right rotation because I found the topic became way easier for me when I conceptualized it this way.

By "complete right rotation", I mean:

  1. The node being rotated (let's call it A) has a parent.
  2. A also has a left child (let's call it B).
  3. B has a right child.

This setup should cover all possible node relationships for a right rotation. I'm curious about the structure where, if my right rotation logic passes this test, it's very likely to handle all cases of right rotations correctly. What is the simplest AVL tree structure that showcases this kind of right rotation, with the least amount of nodes?

This is the simplest example I've come up with. 9 nodes

Rotation happens at node 0040

End result

Upvotes: 0

Views: 97

Answers (1)

trincot
trincot

Reputation: 350147

There are two cases you may want to look at: A is a left child of its parent P, or A is a right child of its parent P. Depending on how you implement the rotation, this difference may be important, as the rotation give P a different child. Here is the first case:

    P                    P
   /                    /
  A             =>     B
 / \                    \
B   C                    A
 \                      / \
  D                    D   C

You required that A had a right child, but to be honest, it doesn't play a significant role in this rotation, as the link between A and C does not change.

There are three edges that are mutated. Here is the pseudo code for it (assuming you have a reference to P):

A = P.left
B = A.left
D = B.right
A.left = D
B.right = A
P.left = B

The second case, where A is the right child of P, is easy to construct from this.

Upvotes: 1

Related Questions