AVL Tree (The advanced Binary Tree)
Author
Hi people,
I''m writing a AVL tree for my school assignment. Maybe this question doesn''t belong here, but the implementation will also help me for implementing 3D levels like Quake orso in the future!
AVL trees are binary trees, but the AVL kind is perfectly balanced.
The questions are:
- Does anyone know how to write a InsertNode function?
- Does anyone know how to write a DeleteNode function?
The functions also balance the tree right away. (So no BalanceTree function orso!)
I have never heard of AVL trees. Do you have any articles that I may read on the subject? Maybe then I can help you
- WitchLord
- WitchLord
I''ve heard of AVL trees. We talked about them in our Data Structures class. I did a quick search on NorthernLight.com. Here''s a few places that I thought were pretty good.
http://hissa.nist.gov/dads/HTML/avltree.html
http://dialspace.dial.pipex.com/town/road/xmx04/Source/C++/AVL-tree.htm
http://esus.cs.montana.edu/cs/course_pages/courses_F97/222/avl_tree.html
http://hissa.nist.gov/dads/HTML/avltree.html
http://dialspace.dial.pipex.com/town/road/xmx04/Source/C++/AVL-tree.htm
http://esus.cs.montana.edu/cs/course_pages/courses_F97/222/avl_tree.html
well, I don't know if this helps, but to add a node, I'll assume the existing tree is AVL satisfied. the child node is added onto the leaf of the parent node that best preserves the "left < right" relationship
-----------2-------------------2----------------------------
----------/-\----- ------------/-\--------------------------
---------1---3----+---5-->---1--4--------------------------
--------------\-----------------/-\-------------------------
---------------4---------------3---5------------------------
note that when 5 is attached to right of 4, the tree becomes unbalanced(/left branch levels - right branch levels/ > 1, /1 - 3/ = 2). You need to "rotate" w/respect to the parent node of the newly attached leaf node. There are various methods you can tinker with.
to delete a node, swap it with the root node, then swap the root node with the last child node and simply wipe it from the tree.(might be able to just swap it immediately with last leaf node) Then check for AVL satisfiability by working your way from top to bottom, swapping the larger of the 2 child nodes with its parent if a swap is needed.
You will need to do some more research on how to "rotate" to preserve balance, but the search efficiency of AVL trees is well worth the effort(O(lgn),worst) as opposed to a normal BST (O(n),worst)
cheers,
muffin
Edited by - cornmuffin on May 31, 2000 2:06:31 AM
-----------2-------------------2----------------------------
----------/-\----- ------------/-\--------------------------
---------1---3----+---5-->---1--4--------------------------
--------------\-----------------/-\-------------------------
---------------4---------------3---5------------------------
note that when 5 is attached to right of 4, the tree becomes unbalanced(/left branch levels - right branch levels/ > 1, /1 - 3/ = 2). You need to "rotate" w/respect to the parent node of the newly attached leaf node. There are various methods you can tinker with.
to delete a node, swap it with the root node, then swap the root node with the last child node and simply wipe it from the tree.(might be able to just swap it immediately with last leaf node) Then check for AVL satisfiability by working your way from top to bottom, swapping the larger of the 2 child nodes with its parent if a swap is needed.
You will need to do some more research on how to "rotate" to preserve balance, but the search efficiency of AVL trees is well worth the effort(O(lgn),worst) as opposed to a normal BST (O(n),worst)
cheers,
muffin
Edited by - cornmuffin on May 31, 2000 2:06:31 AM
Author
Thanks for all your response! You don''t know how much you helped me!
And now implement...sigh...
- Bas.
And now implement...sigh...
- Bas.
Author
An AVL tree is basicly the same as a binairy tree. The only difference is that the AVL tree is balanced.
Trees are just another way of storing your data. A tree has the advantage of sorting the data and providing a quick search.
In games, trees are often used to store level information. (Polygons & vertices)
If you put these all in a tree, you can search fast for visible polygons and skip the invisible ones.
Doom, Quake and lost of other games use a tree for this. An AVL tree of some sort is probably used, but I''m not sure about it.
Trees are just another way of storing your data. A tree has the advantage of sorting the data and providing a quick search.
In games, trees are often used to store level information. (Polygons & vertices)
If you put these all in a tree, you can search fast for visible polygons and skip the invisible ones.
Doom, Quake and lost of other games use a tree for this. An AVL tree of some sort is probably used, but I''m not sure about it.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
