avl tree c implementation

1#include <stdio.h>
2#include "avltree.h"
3/*
4    remove all nodes of an AVL tree
5*/
6void dispose(node* t)
7{
8    if( t != NULL )
9    {
10        dispose( t->left );
11        dispose( t->right );
12        free( t );
13    }
14}
15 
16/*
17    find a specific node's key in the tree
18*/
19node* find(int e, node* t )
20{
21    if( t == NULL )
22        return NULL;
23    if( e < t->data )
24        return find( e, t->left );
25    else if( e > t->data )
26        return find( e, t->right );
27    else
28        return t;
29}
30 
31/*
32    find minimum node's key
33*/
34node* find_min( node* t )
35{
36    if( t == NULL )
37        return NULL;
38    else if( t->left == NULL )
39        return t;
40    else
41        return find_min( t->left );
42}
43 
44/*
45    find maximum node's key
46*/
47node* find_max( node* t )
48{
49    if( t != NULL )
50        while( t->right != NULL )
51            t = t->right;
52 
53    return t;
54}
55 
56/*
57    get the height of a node
58*/
59static int height( node* n )
60{
61    if( n == NULL )
62        return -1;
63    else
64        return n->height;
65}
66 
67/*
68    get maximum value of two integers
69*/
70static int max( int l, int r)
71{
72    return l > r ? l: r;
73}
74 
75/*
76    perform a rotation between a k2 node and its left child
77 
78    note: call single_rotate_with_left only if k2 node has a left child
79*/
80 
81static node* single_rotate_with_left( node* k2 )
82{
83    node* k1 = NULL;
84 
85    k1 = k2->left;
86    k2->left = k1->right;
87    k1->right = k2;
88 
89    k2->height = max( height( k2->left ), height( k2->right ) ) + 1;
90    k1->height = max( height( k1->left ), k2->height ) + 1;
91    return k1; /* new root */
92}
93 
94/*
95    perform a rotation between a node (k1) and its right child
96 
97    note: call single_rotate_with_right only if
98    the k1 node has a right child
99*/
100 
101static node* single_rotate_with_right( node* k1 )
102{
103    node* k2;
104 
105    k2 = k1->right;
106    k1->right = k2->left;
107    k2->left = k1;
108 
109    k1->height = max( height( k1->left ), height( k1->right ) ) + 1;
110    k2->height = max( height( k2->right ), k1->height ) + 1;
111 
112    return k2;  /* New root */
113}
114 
115/*
116 
117    perform the left-right double rotation,
118 
119    note: call double_rotate_with_left only if k3 node has
120    a left child and k3's left child has a right child
121*/
122 
123static node* double_rotate_with_left( node* k3 )
124{
125    /* Rotate between k1 and k2 */
126    k3->left = single_rotate_with_right( k3->left );
127 
128    /* Rotate between K3 and k2 */
129    return single_rotate_with_left( k3 );
130}
131 
132/*
133    perform the right-left double rotation
134 
135   notes: call double_rotate_with_right only if k1 has a
136   right child and k1's right child has a left child
137*/
138 
139 
140 
141static node* double_rotate_with_right( node* k1 )
142{
143    /* rotate between K3 and k2 */
144    k1->right = single_rotate_with_left( k1->right );
145 
146    /* rotate between k1 and k2 */
147    return single_rotate_with_right( k1 );
148}
149 
150/*
151    insert a new node into the tree
152*/
153node* insert(int e, node* t )
154{
155    if( t == NULL )
156    {
157        /* Create and return a one-node tree */
158        t = (node*)malloc(sizeof(node));
159        if( t == NULL )
160        {
161            fprintf (stderr, "Out of memory!!! (insert)\n");
162            exit(1);
163        }
164        else
165        {
166            t->data = e;
167            t->height = 0;
168            t->left = t->right = NULL;
169        }
170    }
171    else if( e < t->data )
172    {
173        t->left = insert( e, t->left );
174        if( height( t->left ) - height( t->right ) == 2 )
175            if( e < t->left->data )
176                t = single_rotate_with_left( t );
177            else
178                t = double_rotate_with_left( t );
179    }
180    else if( e > t->data )
181    {
182        t->right = insert( e, t->right );
183        if( height( t->right ) - height( t->left ) == 2 )
184            if( e > t->right->data )
185                t = single_rotate_with_right( t );
186            else
187                t = double_rotate_with_right( t );
188    }
189    /* Else X is in the tree already; we'll do nothing */
190 
191    t->height = max( height( t->left ), height( t->right ) ) + 1;
192    return t;
193}
194 
195/*
196    remove a node in the tree
197*/
198node* delete( int e, node* t )
199{
200    printf( "Sorry; Delete is unimplemented; %d remains\n", e );
201    return t;
202}
203 
204/*
205    data data of a node
206*/
207int get(node* n)
208{
209    return n->data;
210}
211 
212/*
213    Recursively display AVL tree or subtree
214*/
215void display_avl(node* t)
216{
217    if (t == NULL)
218        return;
219    printf("%d",t->data);
220 
221    if(t->left != NULL)
222        printf("(L:%d)",t->left->data);
223    if(t->right != NULL)
224        printf("(R:%d)",t->right->data);
225    printf("\n");
226 
227    display_avl(t->left);
228    display_avl(t->right);
229}
230