0

Hi all, im having a problem getting my head around "drawing" a Binary Search Tree and AVL Tree.

Im studying computer science, and have an exam in 4 days so need help quite quick lol.

Im looking over past exam papers and having trouble with this question:

Start with an initially empty tree, insert the values:
{81,62,93,34,75,30,56,47,18,59,50} (in that order into:

1. a binary search tree, giving the final diagram;
2. an AVL tree, giving diagrams before and after each rotation

:s i just can't get my head around it. I had a shot but not sure how i can show my diagram (which iv written on paper) here on this thread as a whole diagram/image.

Kind Regards

6
Contributors
11
Replies
12
Views
7 Years
Discussion Span
Last Post by The 1
0

Check out the tree tutorials here for a simple ASCII art method I use to draw trees.

Edited by Narue: n/a

0

If you have to insert data into a binary search tree, they get inserted into the tree depending upon their data values . So if my data is 10,11,12, My tree would be some thing of this sort
10
\
11
\
12
\

In such a scenario many of the O(log n) algorithms like search, insert become O(n). To overcome this problem we would like to make 11 the root and 10 and 12 the children. Enter AVL tree. AVL tree is a self balancing binary search tree. After each insertion, the tree calculates the difference between the left tree and the right tree. If the difference is more the 1 , the tree rotates itself. Play around with this applet
http://www.cs.jhu.edu/~goodrich/dsa/trees/avltree.html

0

Hmm thanks for your reply guys, i can't seem to figure out how AVL tree works...

I made up my own random numbers:

7,99,28,2,56,88,13,29,41,10

When i use the applet and for example enter 1st 2 digits this happens:

Step 1:
7

Step 2:
7
\
99

Step 3:
28
/ \
7 99

And so on, but why does the "28" go at top? Im guessing if that can be explained then the rest would be pretty much easy to understand. Unless someone can give me a step by step tutorial on few random numbers, and use AVL tree...

Edited by The 1: n/a

0

EDITING POST: Wrote a whole long post trying to explain if how i was doing AVL tree's was correct, and turns out i was doing it rite, so there was no need for post. Sorry for double posting...

http://people.ksp.sk/~kuko/bak/

Above linked helped explain it abit better :)

Edited by The 1: n/a

0

You could try reading the algorithm for AVL tree insertion. If you can't read an algorithm and then manually interpret its steps out on paper, you should study something other than computer science.

0

Thank you for the links synfist, appreciate it :)

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.