[go: up one dir, main page]
Scribd
Upload
6 views2 pages

AVL Tree

The document contains C code for implementing an AVL tree, including functions for inserting nodes while maintaining balance through rotations. It features a pre-order traversal function to display the tree's keys. The main function demonstrates the insertion of several keys into the AVL tree and outputs the result of the pre-order traversal.

Uploaded by

pravinemmanuelbalasampath.26csb
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
6 views2 pages

AVL Tree

The document contains C code for implementing an AVL tree, including functions for inserting nodes while maintaining balance through rotations. It features a pre-order traversal function to display the tree's keys. The main function demonstrates the insertion of several keys into the AVL tree and outputs the result of the pre-order traversal.

Uploaded by

pravinemmanuelbalasampath.26csb
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 2

1.

x->height = max(getHeight(x->right), getHeight(x->left)) + 1;


2. y->height = max(getHeight(y->right), getHeight(y->left)) + 1;
3.
4. return y;
5. }
6.
7. struct Node *insert(struct Node* node, int key){
8. if (node == NULL)
9. return createNode(key);
10.
11. if (key < node->key)
12. node->left = insert(node->left, key);
13. else if (key > node->key)
14. node->right = insert(node->right, key);
15.
16. node->height = 1 + max(getHeight(node->left), getHeight(
node->right));
17. int bf = getBalanceFactor(node);
18.
19. // Left Left Case
20. if(bf>1 && key < node->left->key){
21. return rightRotate(node);
22. }
23. // Right Right Case
24. if(bf<-1 && key > node->right->key){
25. return leftRotate(node);
26. }
27. // Left Right Case
28. if(bf>1 && key > node->left->key){
29. node->left = leftRotate(node->left);
30. return rightRotate(node);
31. }
32. // Right Left Case
33. if(bf<-1 && key < node->right->key){
34. node->right = rightRotate(node->right);
35. return leftRotate(node);
36. }
37. return node;
38. }
39.
40. void preOrder(struct Node *root)
41. {
42. if(root != NULL)
43. {
44. printf("%d ", root->key);
45. preOrder(root->left);
46. preOrder(root->right);
47. }
48. }
49.
50. int main(){
51. struct Node * root = NULL;
52.
53.
54. root = insert(root, 1);
55. root = insert(root, 2);
56. root = insert(root, 4);
57. root = insert(root, 5);
58. root = insert(root, 6);
59. root = insert(root, 3);
60. preOrder(root);
61. return 0;
62. }

You might also like