Help with an AVL TREE - Printable Version

Help with an AVL TREE - Printable Version

+- Sinisterly (https://sinister.ly)
+-- Forum: Coding (https://sinister.ly/Forum-Coding)
+--- Forum: Coding (https://sinister.ly/Forum-Coding--71)
+--- Thread: Help with an AVL TREE (/Thread-Help-with-an-AVL-TREE)

Pages: 1 2

Help with an AVL TREE - Apocalypse - 06-11-2014

Guys i need your help.
I would like to draw the AVL TREE of the following numbers.
[ 100 1 45 39 -23 63 207 23 43 11 9 57 440 13 -8 ]

Draw the AVL TREE, step by step, with this particular serie of numbers.
!(After each entry, you should make the weights at each node.)

Guys,can you help me please?
@Deque , @Psycho_Coder , @Legolas , @ArkPhaze , @Ex094 , @Slarek , @Geoff , @chmod

(Sorry for the mention-but i need your help )

RE: Help with an AVL TREE - erpicci - 06-12-2014

What do you mean by "draw"?

If you just need hints for the algorithm, just check AVL tree - Wikipedia. If you have doubts about this, just ask.

If you need help with the implementation, you should first say if you are using C or C++, then describe your data structure and the problems you are facing.

If you already have a working program and need to "draw" your tree graphically, you should consider Graphviz with its DOT language: you can easily write a procedure/method to export your tree to that format.

RE: Help with an AVL TREE - ArkPhaze - 06-12-2014

Help with what? I've already written a full AVL class in C++, but I'm not just going to hand over some code for nothing.

RE: Help with an AVL TREE - Ex094 - 06-12-2014

You present us with the code you've written so far and we'll help ya out further

RE: Help with an AVL TREE - Psycho_Coder - 06-12-2014

@ArkPhaze and @Ex094 I don't think he wants the Code instead he wants to understand how the AVL is being contructed and what does the final AVL tree looks like for the number series he gave. He has already said that he wants to draw the AVL tree by hand. Everything cannot be done by code at first. I believe he wants to understand the mechanism of how AVL tree works taking into account the number he gave.

@Apocalypse

This is the final AVL tree you're looking for :-

[Image: eiW1DmV.png]

RE: Help with an AVL TREE - Apocalypse - 06-12-2014

(06-12-2014, 07:13 AM)Psycho_Coder Wrote: @ArkPhaze and @Ex094 I don't think he wants the Code instead he wants to understand how the AVL is being contructed and what does the final AVL tree looks like for the number series he gave. He has already said that he wants to draw the AVL tree by hand. Everything cannot be done by code at first. I believe he wants to understand the mechanism of how AVL tree works taking into account the number he gave.

@Apocalypse

This is the final AVL tree you're looking for :-

Yes!! You have right my friend. I want help with the graph of AVL tree.

But i think you made the graph wrong.
I think that you din't make it, with this particular serie of numbers.
[ 100 --> 1 --> 45 --> 39 --> -23 --> 63 --> 207 --> 23 --> 43 --> 11 --> 9 --> 57 --> 440 --> 13 --> -8 ]
You started from the number 23. I think you 're wrong.
Also, after each entry, you should make the weights at each node.

But well down, because you unterstood where i wanted the help.
So, what's your opinion?

RE: Help with an AVL TREE - Psycho_Coder - 06-12-2014

NO, My answer is correct and I did follow the sequence you gave. But he final graph will be this and I am very sure.

AVL tree is a height balanced tree and so after a certain condition the graphs undergo LL, RR, LR, RL or Double Rotation and due to the rotations the final root node will change.

I think you are getting confused with AVL or BST. Yes I was too lazy to write the weights in each node Tongue

but the final AVL representation is what I gave.

EDIT :

I found this http://www.cs.usfca.edu/~galles/visualization/AVLtree.html

You can generate the AVL using your values and see the tree that you obtain. My tree is correct Tongue

RE: Help with an AVL TREE - Psycho_Coder - 06-12-2014

Thread Moved to General Programming Section

RE: Help with an AVL TREE - Apocalypse - 06-12-2014

(06-12-2014, 09:38 AM)Psycho_Coder Wrote: NO, My answer is correct and I did follow the sequence you gave. But he final graph will be this and I am very sure.

AVL tree is a height balanced tree and so after a certain condition the graphs undergo LL, RR, LR, RL or Double Rotation and due to the rotations the final root node will change.

I think you are getting confused with AVL or BST. Yes I was too lazy to write the weights in each node but the final AVL representation is what I gave.

EDIT :

I found this http://www.cs.usfca.edu/~galles/visualization/AVLtree.html

You can generate the AVL using your values and see the tree that you obtain. My tree is correct

Hm,
if i had a binary tree, would it be the same?
Which is the difference?

:Thumbs-Up:

RE: Help with an AVL TREE - Psycho_Coder - 06-12-2014

(06-12-2014, 10:03 AM)Apocalypse Wrote:
(06-12-2014, 09:38 AM)Psycho_Coder Wrote: NO, My answer is correct and I did follow the sequence you gave. But he final graph will be this and I am very sure.

AVL tree is a height balanced tree and so after a certain condition the graphs undergo LL, RR, LR, RL or Double Rotation and due to the rotations the final root node will change.

I think you are getting confused with AVL or BST. Yes I was too lazy to write the weights in each node but the final AVL representation is what I gave.

EDIT : See this http://www.slideshare.net/patawad/binary-search-tree-and-avl

I found this http://www.cs.usfca.edu/~galles/visualization/AVLtree.html

You can generate the AVL using your values and see the tree that you obtain. My tree is correct
Hm,
if i had a binary tree, would it be the same?
Which is the difference?

:Thumbs-Up:

A binary search tree (BST) is a binary tree data structure which has the following properties :

1. Every node in BST has a value;
2. a total order is defined on these values;
3. the left subtree of a node contains only values less than the node's value;
4. the right subtree of a node contains only values greater than or equal to the node's value.

An AVL tree on the other hand is a self-balancing binary search tree. In an AVL tree the heights of the two child subtrees of any node differ by at most one, and thereby it is known as height-balanced too. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases. Additions and deletions may require the tree to be rebalanced by one or more tree rotations like LL, RR, LR, RL or double rotation.