Home > other >  is this Ternary expression redundant in splay function
is this Ternary expression redundant in splay function

Time:02-23

https://www.geeksforgeeks.org/splay-tree-set-1-insert/

When I was learning about splay trees, I referred to this article and had a little doubt about the code in it.

this is splay function in this article

struct node *splay(struct node *root, int key)
{
    // Base cases: root is NULL or key is present at root
    if (root == NULL || root->key == key)
        return root;
 
    // Key lies in left subtree
    if (root->key > key)
    {
        // Key is not in tree, we are done
        if (root->left == NULL) return root;
 
        // Zig-Zig (Left Left)
        if (root->left->key > key)
        {
            // First recursively bring the key as root of left-left
            root->left->left = splay(root->left->left, key);
 
            // Do first rotation for root, second rotation is done after else
            root = rightRotate(root);
        }
        else if (root->left->key < key) // Zig-Zag (Left Right)
        {
            // First recursively bring the key as root of left-right
            root->left->right = splay(root->left->right, key);
 
            // Do first rotation for root->left
            if (root->left->right != NULL)
                root->left = leftRotate(root->left);
        }
 
        // Do second rotation for root
        return (root->left == NULL)? root: rightRotate(root);
    }
    else // Key lies in right subtree
    {
        // Key is not in tree, we are done
        if (root->right == NULL) return root;
 
        // Zag-Zig (Right Left)
        if (root->right->key > key)
        {
            // Bring the key as root of right-left
            root->right->left = splay(root->right->left, key);
 
            // Do first rotation for root->right
            if (root->right->left != NULL)
                root->right = rightRotate(root->right);
        }
        else if (root->right->key < key)// Zag-Zag (Right Right)
        {
            // Bring the key as root of right-right and do first rotation
            root->right->right = splay(root->right->right, key);
            root = leftRotate(root);
        }
 
        // Do second rotation for root
        return (root->right == NULL)? root: leftRotate(root);
    }
}

Here is a snippet from the source code return (root->left == NULL)? root: rightRotate(root);, it appears in the last paragraph of the function. My question is if I can write like thisreturn rightRotate(root), Because we have already judged whether this pointer is NULL above, It seems to me that after we do the rotate operation, the root->left can not be NULL. If this pointer can be null, hope to point out the situation that does not hold

CodePudding user response:

is this Ternary expression redundant in splay function

No, root = rightRotate(root); and root = leftRotate(root); change root.

  • Related