avltree.h 1023 Bytes
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/**
 * struct node
 * avl tree node
 */
typedef struct Node
{
	int data;
	struct Node* left;
	struct Node* right;
	int height;
} Node;

/**
 * max function
 * @param a		first number
 * @param b		second number
 * @returns		maximum
 */
int max(int, int);

/**
 * node constructor
 * @param val	node data
 * @returns		node
 */
Node* construct_node(int);

/**
 * right rotation
 * @param node	current root
 * @returns		new root
 */
Node* rotate_right(Node*);

/**
 * left rotation
 * @param node	current root
 * @returns		new root
 */
Node* rotate_left(Node*);

/**
 * get balance value of a node
 * how much longer is the left subtree compared to the right subtree?
 * @param node	root node
 * @returns int	balance value
 */
int get_balance(Node*);

/**
 * insert node to given node
 * @param node		root node
 * @param key		node data to be inserted
 * @returns			new root
 */
Node* insert(Node*, int);

/**
 * print tree
 * @param node		root node
 * @param space		how much space to next level
 */
void print_tree(Node*, int);