AVL tree rotations in Data Structures Theory - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to perform a single right rotation on a node in an AVL tree.

Data Structures Theory

def right_rotate([1]):
    y = [1].left
    T2 = y.right

    y.right = [1]
    [1].left = T2

    return y

Drag options to blanks, or click blank then click option'

Az

Bx

Cnode

Droot

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variable names inconsistently.

Forgetting to update the left or right child pointers.

The function takes a node as input and performs a right rotation around it. The variable node is used consistently to refer to the node being rotated.

2fill in blank

medium

Complete the code to perform a single left rotation on a node in an AVL tree.

Data Structures Theory

def left_rotate([1]):
    y = [1].right
    T2 = y.left

    y.left = [1]
    [1].right = T2

    return y

Drag options to blanks, or click blank then click option'

Aroot

Bnode

Ctemp

Dcurrent

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up left and right child pointers.

Using inconsistent variable names.

The function rotates the given node to the left by adjusting pointers accordingly.

3fill in blank

hard

Fix the error in the code that performs a left-right rotation in an AVL tree.

Data Structures Theory

def left_right_rotate([1]):
    [1].left = left_rotate([1].left)
    return right_rotate([1])

Drag options to blanks, or click blank then click option'

Anode

Broot

Ctemp

Dcurrent

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variable names for the node parameter.

Incorrect order of rotations.

The parameter node is used consistently to perform the left-right rotation by first rotating the left child to the left, then the node to the right.

4fill in blank

hard

Fill both blanks to complete the right-left rotation function in an AVL tree.

Data Structures Theory

def right_left_rotate([1]):
    [1].right = [2]([1].right)
    return left_rotate([1])

Drag options to blanks, or click blank then click option'

Anode

Broot

Cleft_rotate

Dright_rotate

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping the order of rotations.

Using incorrect function names for rotations.

The function performs a right-left rotation by first rotating the right child to the left, then rotating the node to the left.

5fill in blank

hard

Fill all three blanks to complete the balance factor calculation and rotation decision in an AVL tree node insertion.

Data Structures Theory

def insert([1], key):
    if not [1]:
        return Node(key)

    if key < [1].key:
        [1].left = insert([1].left, key)
    else:
        [1].right = insert([1].right, key)

    balance = height([1].left) - height([1].right)

    if balance > 1 and key < [1].left.key:
        return right_rotate([1])

    if balance < -1 and key > [1].right.key:
        return left_rotate([1])

    if balance > 1 and key > [1].left.key:
        [1].left = left_rotate([1].left)
        return right_rotate([1])

    if balance < -1 and key < [1].right.key:
        [1].right = right_rotate([1].right)
        return left_rotate([1])

    return [1]

Drag options to blanks, or click blank then click option'

Anode

Broot

Ccurrent

Dtemp

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variable names inconsistently.

Forgetting to return the updated node after rotations.

The parameter node is used consistently to refer to the current node in the AVL tree during insertion and balancing.