Thread: avl question with example

  1. #1
    Registered User
    Join Date
    Apr 2019
    Posts
    662

    avl question with example

    lets suppose i have this tree
    avl question with example-avl-out-balance-jpg

    the node with data = 35 was the last node added and has thrown the balance out of wack.
    balance of 35 = 0 left 0 right
    balance of 40 = 1 left 1 right ....still ok
    balance of 30 = 1 left 2 right... still ok
    balance of 20 = 1 left 3 right ... problem

    so 20 is the first unbalanced node.
    q1) is that a right right left problem?
    q2) if so do i solve it with a left right rotation
    q3) how do i decide which is the rt node and which nodes are A B and C ie which node do i rotate about and keep track of its children and grandchildren

  2. #2
    Registered User
    Join Date
    May 2019
    Posts
    200
    I don't think an AVL would get to this state, it would have been tightly balanced before this condition.

    I say that because 35 is what you're adding, but if I say 35 didn't exist (the state before the insertion), the tree was already not balanced.

    That's key to AVL. AVL can't balance a tree if it was more than 1 node out of balance. That is, AVL will allow only one node to be slightly out of balance simply because that last node was an "odd entry". I'm not saying trees have even numbers when balanced. Factually, only an odd number of entries could be perfectly balanced. You can see that with just 3 nodes. A balanced 3 node tree would have one left, one right and the root. An even number of nodes would unbalance that tree no matter what, but by only 1 node. So when I say an "odd entry", I'm saying that one unbalanced node situation AVL can permit.

    So, I must first imagine than not only 35, but 40 and 25 are not there.

    At that point the tree is perfectly balanced.

    EDIT:

    Ok, I'm wrong.

    I found this really nice looking visualization tool you'll want to use.

    AVL Tree Visualzation


    I'll refresh my memory, pour the second, and by the third I'll be in shape to be more coherent on what's next.
    Last edited by Niccolo; 06-13-2019 at 05:41 AM.

  3. #3
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    i don't understand why the tree is out of balance if you are allowed -1 0 or 1
    avl question with example-balanced-avl-jpg

    just focusing on the right side from the root and skipping the nodes with no children (bf = balance factor)
    node 30: 1 node left and 1 node right bf = 1 - 1 = 0
    node 20: 1 node left and 2 nodes right bf = 1 - 2 = -1
    node 15: 2 nodes left and 3 nodes right bf = 2 - 3 = -1

    if we add node 35 back in
    node 40: 1 node left 0 nodes right bf = 1 - 0 = 1
    node 30: 1 node left 2 nodes right bf = 1 - 2 = -1
    node 20: 1 node left 3 nodes right bf = 1 - 2 = -2 first issue do a rotation of some sort

    coop

  4. #4
    Registered User
    Join Date
    May 2019
    Posts
    200
    Like I edited - I needed more coffee...check the visual tool I linked. It's quite good.

    It animates the balancing, you can build this exact tree there and watch the solution.

    Even back it up and roll it forward.

  5. #5
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    sorry you must of edited as i posted

  6. #6
    Registered User
    Join Date
    May 2019
    Posts
    200
    It turns out that when 35 is added, the rotation happens at 20. It is rotated to the left, so 30 is connected to 15, 20 is on it's left, 40 on it's right.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 08-25-2014, 05:41 PM
  2. Replies: 1
    Last Post: 03-23-2011, 09:00 AM
  3. *szString = things question/memory question
    By Jang in forum C Programming
    Replies: 3
    Last Post: 01-20-2011, 04:59 AM
  4. Newbish Question file reading question....
    By kas2002 in forum C Programming
    Replies: 23
    Last Post: 05-17-2007, 12:06 PM
  5. Self regiserting DLLs question and libraries question.
    By ApocalypticTime in forum Windows Programming
    Replies: 2
    Last Post: 03-22-2003, 02:02 PM

Tags for this Thread