Member Avatar for The 1

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
  • 333 Views
  • 2 Weeks Discussion Span
  • Latest Post Latest Post by The 1
Member Avatar for The 1

This is what iv got but not sure if its correct:

http://i45.tinypic.com/29o52j7.jpg

If any1 could confirm if that is correct id appreciate it, but i have no idea about AVL and how it works...

Member Avatar for Narue

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

Edited by Narue because: n/a
Member Avatar for abhimanipal

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

Member Avatar for The 1

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 because: n/a
Member Avatar for The 1

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 because: n/a
Member Avatar for abhimanipal

So I take it your confusion got cleared ?

Member Avatar for Rashakil Fol

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.

Member Avatar for The 1

Thank you for the links synfist, appreciate it :)

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.