87 lines
2.2 KiB
C
87 lines
2.2 KiB
C
#include "AVL.h"
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
|
|
#define SIZE 16
|
|
|
|
int main(void) {
|
|
Node *root = NULL;
|
|
|
|
printTree(root);
|
|
|
|
printf("After inserting 10:\n");
|
|
insertNode(&root, 10);
|
|
printTree(root);
|
|
|
|
printf("\nAfter inserting 5:\n");
|
|
insertNode(&root, 5);
|
|
printTree(root);
|
|
|
|
printf("\nAfter inserting 15:\n");
|
|
insertNode(&root, 15);
|
|
printTree(root);
|
|
|
|
printf("\nAfter inserting 9, 13:\n");
|
|
insertNode(&root, 9);
|
|
insertNode(&root, 13);
|
|
printTree(root);
|
|
|
|
printf("\nAfter inserting 2, 6, 12 (single right rotation), 14:\n");
|
|
insertNode(&root, 2);
|
|
insertNode(&root, 6);
|
|
insertNode(&root, 12);
|
|
insertNode(&root, 14);
|
|
printTree(root);
|
|
|
|
printf("\nSearching for 10, 6, 13, 14, 1, 3, 11, 16:\n");
|
|
printf(findNode(root, 10)->key == 10 ? "true\n" : "false\n");
|
|
printf(findNode(root, 6)->key == 6 ? "true\n" : "false\n");
|
|
printf(findNode(root, 13)->key == 13 ? "true\n" : "false\n");
|
|
printf(findNode(root, 14)->key == 14 ? "true\n" : "false\n");
|
|
printf(findNode(root, 1) == NULL ? "true\n" : "false\n");
|
|
printf(findNode(root, 3) == NULL ? "true\n" : "false\n");
|
|
printf(findNode(root, 11) == NULL ? "true\n" : "false\n");
|
|
printf(findNode(root, 16) == NULL ? "true\n" : "false\n");
|
|
|
|
printf("\nAfter deleting 12 (double right left rotation):\n");
|
|
free(deleteNode(&root, 12));
|
|
printTree(root);
|
|
|
|
printf("\nAfter deleting 13 (which has no children):\n");
|
|
free(deleteNode(&root, 13));
|
|
printTree(root);
|
|
|
|
printf("\nAfter deleting 9 (which has a left child):\n");
|
|
free(deleteNode(&root, 9));
|
|
printTree(root);
|
|
|
|
printf("\nAfter deleting 5 (which has two children):\n");
|
|
free(deleteNode(&root, 5));
|
|
printTree(root);
|
|
|
|
printf("\nAfter deleting 10 (which has two children):\n");
|
|
free(deleteNode(&root, 10));
|
|
printTree(root);
|
|
|
|
destroyTree(root);
|
|
|
|
printf("\n--------------------\nSee slides 16-17, chapter 10, and slides "
|
|
"10-13, chapter 11:\n\n");
|
|
|
|
root = NULL;
|
|
int values[SIZE] = {3, 2, 1, 4, 5, 6, 7, 16, 15, 14, 13, 12, 11, 10, 8, 9};
|
|
for (int i = 0; i < SIZE; i++) {
|
|
printf("inserting %d:\n", values[i]);
|
|
insertNode(&root, values[i]);
|
|
printTree(root);
|
|
printf("\n");
|
|
}
|
|
for (int i = 0; i < SIZE; i++) {
|
|
printf("deleting %d:\n", values[i]);
|
|
deleteNode(&root, values[i]);
|
|
printTree(root);
|
|
printf("\n");
|
|
}
|
|
return 0;
|
|
}
|