Sinisterly
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

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

(06-12-2014, 10:09 AM)Psycho_Coder Wrote:
(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 Tongue 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 Tongue
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.
Yes, i understood.

Do you know any algorithm about traversing across a complete binary tree ? (at C for example)

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

You can traverse aTree in post order or preorder or inorder. Just Google for it.

RE: Help with an AVL TREE - alok9shm - 06-13-2014

@Psycho_Coder already got it correct.
Anyways, I added the Balance factor in his Tree.

[Image: l0TFyH0.jpg]

Do it like this:
The First Element in your Array is your Root node [at least for now. It will be changed later]

Add 100 as the root node

Now pick the next element, if this element is bigger than the root node, insert it as the Right Child, else as the Left Child, and repeat with the rest elements.

In each step, write down the Balance factor beside each node. [BF = Height of the node's Left Subtree - Right Subtree]

Now, if the BF for a node is +1, -1 or 0, you can proceed normally, but if the BF becomes -2 or +2, you have to rotate the tree from the current node's position [Node that has BF +2 or -2].
Rotate if clockwise if +2 and Anti-clockwise if -2. [You do the opposite if it doesn't work out]

Remember to add the next element only when your AVL tree is balanced, ie. you do not have +2 or -2 BF somewhere in the tree.

RE: Help with an AVL TREE - alok9shm - 06-13-2014

@Psycho_Coder already got it correct.
Anyways, I added the Balance factor in his Tree.

[Image: l0TFyH0.jpg]

Do it like this:
The First Element in your Array is your Root node [at least for now. It will be changed later]

Add 100 as the root node

Now pick the next element, if this element is bigger than the root node, insert it as the Right Child, else as the Left Child, and repeat with the rest elements.

In each step, write down the Balance factor beside each node. [BF = Height of the node's Left Subtree - Right Subtree]

Now, if the BF for a node is +1, -1 or 0, you can proceed normally, but if the BF becomes -2 or +2, you have to rotate the tree from the current node's position [Node that has BF +2 or -2].
Rotate if clockwise if +2 and Anti-clockwise if -2. [You do the opposite if it doesn't work out]

Remember to add the next element only when your AVL tree is balanced, ie. you do not have +2 or -2 BF somewhere in the tree.