Balancing a tree (AVL Tree)

This is a discussion on Balancing a tree (AVL Tree) within the C Programming forums, part of the General Programming Boards category; Yeah, that's wrong. Your code doesn't do an avl tree, it just does a regular bst without any balancing logic, ...

  1. #16
    Registered User Noir's Avatar
    Join Date
    Mar 2007
    Posts
    218
    Yeah, that's wrong. Your code doesn't do an avl tree, it just does a regular bst without any balancing logic, so where a node goes, it stays. The tree looks like this with that sequence of insertions:
    Code:
    3,7,5,4,2,1,6
    
        3
       / \
      2   7
     /   /
    1   5
       / \
      4   6

  2. #17
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,211
    As others are stating, an AVL tree is always supposed to be balanced with the exception of during an insertion or deletion. By the end of the insertion or deletion, however, you should have balanced the tree.

  3. #18
    Lean Mean Coding Machine KONI's Avatar
    Join Date
    Mar 2007
    Location
    Luxembourg, Europe
    Posts
    444
    1. insert a node
    2. check if balanced
    3. if not balanced, balance

  4. #19
    Brak BoneXXX's Avatar
    Join Date
    Mar 2007
    Location
    Bangkok
    Posts
    62
    Thanks for the replies.
    “Example isn't another way to teach, it is the only way to teach” Albert Einstein

  5. #20
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,239
    Quote Originally Posted by BoneXXX View Post
    I still couldn't figure out how to write a function that builds a balanced tree from a sorted array.
    Take the middle element of the sorted array. This will be the root of the tree. Take everything left of this middle element and construct a balanced tree from it, and make this the left subtree. Same for the right. Recursive implementation is just a few lines.

    If the data is already sorted, there is no need to make a tree out of it. Just do binary search.

    Is this for an assignment? If not, you're making things harder than they need to be. The height of ANY balanced tree of N nodes is simply floor(log2(N))+1.

  6. #21
    Registered User
    Join Date
    Apr 2007
    Posts
    129
    Quote Originally Posted by brewbuck View Post
    Take the middle element of the sorted array. This will be the root of the tree. Take everything left of this middle element and construct a balanced tree from it, and make this the left subtree. Same for the right. Recursive implementation is just a few lines.

    If the data is already sorted, there is no need to make a tree out of it. Just do binary search.

    Is this for an assignment? If not, you're making things harder than they need to be. The height of ANY balanced tree of N nodes is simply floor(log2(N))+1.
    Thats the way I intend to balance my ternary tree code. Adding the logic to balance the tree during every insertion and deletion is just a pain. Of course if the tree is large and unbalanced, you might run out of stack space. Thus iteration with a stack (LIFO) allocated from the heap for your node traversal is in order, rather than the more elegant recursive solution.

    My question, however, is this:
    Is generating a sorted list from a potentially unbalanced ternary (or even binary) tree of order n, the number of entries? For a binary tree I think the answer is yes, that you only have to visit each node at most three times as you do a depth first traversal. For ternary trees where the sort is in lexigraphical order I think you visit a node at most 4 times.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. AVL tree balancing problem
    By sweets in forum C++ Programming
    Replies: 4
    Last Post: 05-06-2004, 12:17 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

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