search

amitbansal7 / Data-Structures-and-Algorithms

Implementation of various Data Structures and algorithms - Linked List, Stacks, Queues, Binary Search Tree, AVL tree,Red Black Trees, Trie, Graph Algorithms, Sorting Algorithms, Greedy Algorithms, Dynamic Programming, Segment Trees etc.
252 stars 90 forks source link

The height of the node in AVL tree is wrong #1

Open zhiyuanpeng opened 5 years ago

zhiyuanpeng commented 5 years ago

I input the data 10, 4, 6. After the rebalance, the height of each of the three nodes should be ZERO. However, in your AVL tree code, the height isn't ZERO. You can check it.

amitbansal7 commented 5 years ago

hey, i am not sure what are you trying to say. can you please elaborate? And how height of all the three nodes can be zero? One of these three has to be the root node. right? and the root can have minimum height of 1 if there are three nodes.

zhiyuanpeng commented 5 years ago

hey, i am not sure what are you trying to say. can you please elaborate? And how height of all the three nodes can be zero? One of these three has to be the root node. right? and the root can have minimum height of 1 if there are three nodes.

The first input data 10 is the root, then the sencond data 4 is the left substree of 10. After the third data 6 is inserted in the AVL tree. The balance factor of the root is 2>1, so, the tree is unbalanced. This is a right of left unbalanced tree, so, after the rebalance processing, the three nodes' balance factors should all be ZERO. However, I run your code, the result is that the balance factors are not all zero.

amitbansal7 commented 5 years ago 
void preorder(struct Node* root)
{
    if(root==NULL)
        return;

    printf("Data : %d  | Balancing factor : %d\n",root->data, Balance(root));
    preorder(root->left);
    preorder(root->right);
}

So i inserted (10, 4, 6) in that order. After rebalancing(left right case) i did the above preorder traversal. And this was the output. this looks good to me. Can you share the changes you made in the code?

Preorder traversal of tree is : 
Data : 6  | Balancing factor : 0
Data : 4  | Balancing factor : 0
Data : 10  | Balancing factor : 0
zhiyuanpeng commented 5 years ago

Do we use the same code? I only modify the "outpreorder" function so that I can print the balance factor. The attachment is your code with my modification. You can run it.

Amit Bansal notifications@github.com 于2018年11月29日周四 上午12:49写道：

`void preorder(struct Node* root) { if(root==NULL) return;

printf("Data : %d | Balancing factor : %d\n",root->data, Balance(root)); preorder(root->left); preorder(root->right);

} So i inserted (10, 4, 6) in that order. After rebalancing(left right case) i did the above preorder traversal. And this was the output. this looks good to me. Can you share the changes you made in the code. Preorder traversal of tree is : Data : 6 | Balancing factor : 0 Data : 4 | Balancing factor : 0 Data : 10 | Balancing factor : 0 `

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/amitbansal7/Data-Structures-and-Algorithms/issues/1#issuecomment-442753317, or mute the thread https://github.com/notifications/unsubscribe-auth/AfSuZbc-1jUX9uJ4_FtEnVnXup2tFl_Yks5uz5-ngaJpZM4Yv-Hr .

-- "PZY make life better ! "

amitbansal7 commented 5 years ago

There is no attachment here. And i am using the same code as in my repository with only changes made in preorder traversal which are shown above.