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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
/****************************************************************************
* *
* Loki - Programs for genetic analysis of complex traits using MCMC *
* *
* Simon Heath - CNG, Evry *
* *
* October 2002 *
* *
* bin_tree.c: *
* *
* Routines for binary tree stuff *
* *
* Copyright (C) Simon C. Heath 1997, 2000, 2002 *
* This is free software. You can distribute it and/or modify it *
* under the terms of the Modified BSD license, see the file COPYING *
* *
****************************************************************************/
#include <stdlib.h>
#ifdef USE_DMALLOC
#include <dmalloc.h>
#endif
#include "bin_tree.h"
struct bin_node *rotate_left(struct bin_node *node)
{
struct bin_node *l,*gc;
l=node->left;
if(l->balance==-1) {
node->left=l->right;
l->right=node;
node->balance=l->balance=0;
node=l;
} else {
gc=l->right;
l->right=gc->left;
gc->left=l;
node->left=gc->right;
gc->right=node;
switch(gc->balance) {
case -1:
node->balance=1;
l->balance=0;
break;
case 0:
node->balance=l->balance=0;
break;
case 1:
node->balance=0;
l->balance=-1;
}
gc->balance=0;
node=gc;
}
return node;
}
struct bin_node *rotate_right(struct bin_node *node)
{
struct bin_node *r,*gc;
r=node->right;
if(r->balance==1) {
node->right=r->left;
r->left=node;
node->balance=r->balance=0;
node=r;
} else {
gc=r->left;
r->left=gc->right;
gc->right=r;
node->right=gc->left;
gc->left=node;
switch(gc->balance) {
case -1:
node->balance=0;
r->balance=1;
break;
case 0:
node->balance=r->balance=0;
break;
case 1:
node->balance=-1;
r->balance=0;
}
gc->balance=0;
node=gc;
}
return node;
}
void free_bin_tree(struct bin_node *node,void (*free_node)(void *))
{
if(node->left) free_bin_tree(node->left,free_node);
if(node->right) free_bin_tree(node->right,free_node);
if(node->data) free_node(node->data);
free(node);
}
|
