Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Do not change the next 7 lines
- #include "avl.h"
- #include <stdio.h>
- #include <stdlib.h>
- typedef enum Position {LEFT, RIGHT} Position; // TIP: use this in your code!
- #define MAX(X,Y) (((X)>(Y))?(X):(Y))
- #define ABS(X) ((X<0)?(-X):(X))
- // Fill your info here:
- /****
- Student1 name: ----- -----
- Student2 name: ----- -----
- Student1 ID: -----------
- Student2 ID: -----------
- ****/
- // Operations
- int height(AVLNodePtr tnode)
- {
- if (tnode == NULL)
- return 0;
- return tnode->height;
- }
- int getBalance(AVLNodePtr tnode)
- {
- if (tnode == NULL)
- return 0;
- return height(tnode->child[0]) - height(tnode->child[1]);
- }
- AVLNodePtr avl_search( AVLNodePtr tnode, int k ){
- if (tnode == NULL) return NULL;
- if (tnode->key == k)
- return tnode;
- if (tnode->key < k)
- return avl_search(tnode->child[1], k);
- return avl_search(tnode->child[0], k);
- }
- AVLNodePtr avl_insert( AVLNodePtr tnode, int k ){
- if (tnode == NULL)
- {
- tnode = (AVLNode*)malloc(sizeof(AVLNode));
- tnode->key = k;
- tnode->size = 1;
- tnode->height = 0;
- tnode->child[0] = NULL;
- tnode->child[1] = NULL;
- }
- else
- if (k > tnode->key) // insert in right subtree
- {
- tnode->child[1] = avl_insert(tnode->child[1], k);
- if (BF(tnode) == -2)
- if (k>tnode->child[1]->key)
- tnode = RR(tnode);
- else
- tnode = RL(tnode);
- }
- else
- if (k<tnode->key)
- {
- tnode->child[0] = avl_insert(tnode->child[0], k);
- if (BF(tnode) == 2)
- if (k < tnode->child[0]->key)
- tnode = LL(tnode);
- else
- tnode = LR(tnode);
- }
- if (tnode->child[0] == NULL && tnode->child[1] == NULL)
- tnode->size = 1;
- else if (tnode->child[0] == NULL && tnode->child[1] != NULL)
- tnode->size = tnode->child[1]->size + 1;
- else if (tnode->child[1] == NULL && tnode->child[0] != NULL)
- tnode->size = tnode->child[0]->size + 1;
- else tnode->size = tnode->child[0]->size + tnode->child[1]->size + 1;
- tnode->height = heightt(tnode);
- //tnode->size = sizee(tnode);
- return(tnode);
- }
- int sizee(AVLNodePtr node)
- {
- if (node == NULL)
- return 0;
- else
- return(sizee(node->child[0]) + 1 + sizee(node->child[1]));
- }
- AVLNodePtr avl_delete( AVLNodePtr tnode, int k ){
- AVLNodePtr p;
- if (tnode == NULL)
- {
- return NULL;
- }
- else
- if (k > tnode->key) // insert in right subtree
- {
- tnode->child[1] = avl_delete(tnode->child[1], k);
- if (BF(tnode) == 2)
- if (BF(tnode->child[0]) >= 0)
- tnode = LL(tnode);
- else
- tnode = LR(tnode);
- }
- else
- if (k<tnode->key)
- {
- tnode->child[0] = avl_delete(tnode->child[0], k);
- if (BF(tnode) == -2) //Rebalance during windup
- if (BF(tnode->child[1]) <= 0)
- tnode = RR(tnode);
- else
- tnode = RL(tnode);
- }
- else
- {
- //data to be deleted is found
- if (tnode->child[1] != NULL)
- { //delete its inorder succesor
- p = tnode->child[1];
- while (p->child[0] != NULL)
- p = p->child[0];
- tnode->key = p->key;
- tnode->child[1] = avl_delete(tnode->child[1], p->key);
- if (BF(tnode) == 2)//Rebalance during windup
- if (BF(tnode->child[0]) >= 0)
- tnode = LL(tnode);
- else
- tnode = LR(tnode);
- }
- else
- return(tnode->child[0]);
- }
- if (tnode->child[0] == NULL && tnode->child[1] == NULL)
- tnode->size = 1;
- else if (tnode->child[0] == NULL && tnode->child[1] != NULL)
- tnode->size = tnode->child[1]->size + 1;
- else if (tnode->child[1] == NULL && tnode->child[0] != NULL)
- tnode->size = tnode->child[0]->size + 1;
- else tnode->size = tnode->child[0]->size + tnode->child[1]->size + 1;
- tnode->height = heightt(tnode);
- return(tnode);
- }
- AVLNodePtr new_avl_node( int k ){
- AVLNode* node = (AVLNode*)malloc(sizeof(AVLNode));
- node->key = k;
- node->size = 1;
- node->height = 0;
- node->child[0] = NULL;
- node->child[1] = NULL;
- return node;
- }
- void delete_avl_tree( AVLNodePtr root ){
- if (root == NULL)
- {
- return;
- }
- delete_avl_tree(root->child[0]);
- delete_avl_tree(root->child[1]);
- free(root);
- }
- /*int sizee(AVLNodePtr T) {
- int rs, sl;
- if (T == NULL)
- return 0;
- if (T->child[0] == NULL)
- sl = 0;
- else
- sl = 1 + T->child[0]->size;
- if (T->child[1] == NULL)
- rs = 0;
- else
- rs = 1 + T->child[1]->size;
- return (rs + sl+1);
- }*/
- int heightt(AVLNodePtr T)
- {
- int lh, rh;
- if (T == NULL)
- return(0);
- if (T->child[0] == NULL)
- lh = 0;
- else
- lh = 1 + T->child[0]->height;
- if (T->child[1] == NULL)
- rh = 0;
- else
- rh = 1 + T->child[1]->height;
- if (lh>rh)
- return(lh);
- return(rh);
- }
- AVLNodePtr rotateright(AVLNodePtr x)
- {
- AVLNodePtr y;
- y = x->child[0];
- x->child[0] = y->child[1];
- y->child[1] = x;
- x->height = heightt(x);
- y->height = heightt(y);
- x->size = sizee(x);
- y->size = sizee(y);
- return(y);
- }
- AVLNodePtr rotateleft(AVLNodePtr x)
- {
- AVLNodePtr y;
- y = x->child[1];
- x->child[1] = y->child[0];
- y->child[0] = x;
- x->height = heightt(x);
- y->height = heightt(y);
- x->size = sizee(x);
- y->size = sizee(y);
- return(y);
- }
- AVLNodePtr RR(AVLNodePtr T)
- {
- T = rotateleft(T);
- return(T);
- }
- AVLNodePtr LL(AVLNodePtr T)
- {
- T = rotateright(T);
- return(T);
- }
- AVLNodePtr LR(AVLNodePtr T)
- {
- T->child[0] = rotateleft(T->child[0]);
- T = rotateright(T);
- return(T);
- }
- AVLNodePtr RL(AVLNodePtr T)
- {
- T->child[1] = rotateright(T->child[1]);
- T = rotateleft(T);
- return(T);
- }
- int BF(AVLNodePtr T)
- {
- int lh, rh;
- if (T == NULL)
- return(0);
- if (T->child[0] == NULL)
- lh = 0;
- else
- lh = 1 + T->child[0]->height;
- if (T->child[1] == NULL)
- rh = 0;
- else
- rh = 1 + T->child[1]->height;
- return(lh - rh);
- }
- // Queries
- int next_missing( AVLNodePtr tnode ){
- return 1; // Student code goes here. Feel free to remove this line.
- }
- int avl_rank( AVLNodePtr tnode, int k ){
- if (tnode == NULL)
- return NULL;
- else
- {
- AVLNodePtr result = avl_rank(tnode->child[1], k);
- if(result)
- k--;
- if (k == 0)
- return tnode->size;
- return avl_rank(tnode->child[0], k);
- }
- }
- int sizer(AVLNodePtr node) {
- if (node == NULL)
- return 0;
- return node->size;
- }
- /*AVLNodePtr Min(AVLNodePtr node)
- {
- if (node == NULL)
- return;
- else {
- AVLNodePtr current = node;
- while (current->child[0])
- {
- }
- }
- }*/
- AVLNodePtr avl_select( AVLNodePtr tnode, int k ){
- return NULL; // Student code goes here. Feel free to remove this line.
- }
- // Utilities
- // Tests
- // (when you're ready, remove the comments and test your code)
- typedef enum {FAILED,PASSED} TestResult;
- void avl_test();
- int avl_test_recurse( AVLNodePtr tnode, TestResult * res );
- void insert_delete_search_test();
- void rank_select_test();
- void next_missing_test();
- void avl_test(){
- int i=1;
- TestResult res = PASSED;
- AVLNodePtr root = NULL;
- for( i=1; i<100000; ++i )
- root = avl_insert( root, i );
- avl_test_recurse( root, &res );
- if( res == FAILED )
- printf("AVL test failed.\n");
- else
- printf("AVL test passed.\n");
- delete_avl_tree( root );
- }
- int avl_test_recurse( AVLNodePtr tnode, TestResult * res ){
- int h_left,h_right;
- if( !tnode )
- return -1;
- h_left = avl_test_recurse( tnode->child[LEFT], res );
- h_right = avl_test_recurse( tnode->child[RIGHT], res );
- *res = (ABS(h_left-h_right) > 1 ) ? FAILED:*res;
- return 1+MAX(h_left,h_right);
- }
- void insert_delete_search_test(){
- int i=1;
- AVLNodePtr node = NULL, root = NULL;
- TestResult res = PASSED;
- for( i=1; i<20; ++i )
- root = avl_insert( root, i );
- for( i=1; i<20; ++i ){
- if( !((node = avl_search( root, i )) && (node->key == i))){
- res = FAILED;
- break;
- }
- root = avl_delete( root, i );
- if( avl_search( root, i ) ){
- res = FAILED;
- break;
- }
- }
- if( res == FAILED )
- printf("insert/delete/search test failed.\n");
- else
- printf("insert/delete/search test passed.\n");
- delete_avl_tree( root );
- }
- void rank_select_test(){
- int i=11;
- AVLNodePtr node = NULL, root = NULL;
- TestResult res = PASSED;
- for( i=11; i<21; ++i )
- root = avl_insert( root, i );
- if( (avl_rank( root, 20 ) != 10) || \
- (avl_rank(root,11) != 1) || \
- (avl_rank(root, 15) != 5) )
- res = FAILED;
- if( res == FAILED )
- printf("rank/select test failed.\n");
- else
- printf("rank/select test passed.\n");
- delete_avl_tree( root );
- }
- /*
- void next_missing_test(){
- AVLNodePtr root = NULL;
- TestResult res = PASSED;
- root = avl_insert( root, 1 );
- res = (next_missing( root )==2)?res:FAILED;
- root = avl_insert( root, 3 );
- res = (next_missing( root )==2)?res:FAILED;
- root = avl_insert( root, 2 );
- res = (next_missing( root )==4)?res:FAILED;
- if( res == FAILED )
- printf("next_missing test failed.\n");
- else
- printf("next_missing test passed.\n");
- delete_avl_tree( root );
- }
- */
- int main(){
- avl_test();
- insert_delete_search_test();
- rank_select_test();
- //next_missing_test();
- printf("AVL: Hello World!\n");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement