number of rotations in AVL tree

This is a discussion on number of rotations in AVL tree within the Tech Board forums, part of the Community Boards category; With AVL trees when does a removeElement operation require Θ(log n) trinode restructuring (rotations)? From wikipiedia removing a node "time ...

  1. #1
    Registered User
    Join Date
    Apr 2010
    Location
    Vancouver
    Posts
    108

    number of rotations in AVL tree

    With AVL trees when does a removeElement operation require Θ(log n) trinode restructuring (rotations)? From wikipiedia removing a node "time required is O(log n) for lookup, plus a maximum of O(log n) rotations on the way back to the root, so the operation can be completed in O(log n) time."

    I don't understand because what does n represent? The input size? That doesn't make any sense we pass removeElement a key and a tree.

    I thought removing any element from an AVL tree requires a single rotation, why do they say Θ(log n) rotations?

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,279
    I don't see them use Θ in there, just big-O. But still, it's O(log n) rotations because when you delete a node and replace it with a node from lower in the tree, you may need to rotate each node on the way back up from the replacement node to keep the tree and it's subtrees in balance. An AVL tree, by definition, must have the tree and all it's subtrees in balance.

  3. #3
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,892
    n is the number of nodes currently in the tree.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Question about computing the number of nodes in a Binary Tree
    By Overworked_PhD in forum C Programming
    Replies: 3
    Last Post: 12-12-2009, 12:10 PM
  2. finding the least bigger number from the tree
    By transgalactic2 in forum C Programming
    Replies: 0
    Last Post: 04-12-2009, 03:34 PM
  3. 2d rotations
    By beginner.alx in forum Game Programming
    Replies: 11
    Last Post: 09-19-2008, 08:57 PM
  4. Binary sort number arranging tree
    By newtocpp in forum C++ Programming
    Replies: 3
    Last Post: 11-14-2006, 04:19 AM
  5. number of nodes in tree
    By Unregistered in forum C++ Programming
    Replies: 2
    Last Post: 04-24-2002, 06:49 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21