data_structure/gh_BST_lite.cpp at master · chogahui05/data_structure · GitHub

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
//Simple bst.
class gh_BST
{
    typedef struct node
    {
        int num; //real_data
        int is_removed;
        struct node *left,*right;
    }node;
private:
    node *root;
    node *new_root;
    int remove_count;
    //if remove_node is exceed remove node bound
    //reconstruct Tree
    int remove_node_bound;
public:
    gh_BST()
    {
    	remove_node_bound = 100;
        gh_init();
    }
public:
    void add(int x)
    {
    	add(&root,x);
    }
    //if x is exist in BST, return 1, otherwise return 0
    int find_num(int x)
    {
        node *tt = _find(root,x);
	if(tt==NULL)
	    return 0;
	return (tt->is_removed == 0);
    }
    void remove(int x)
    {
        if(find_num(x)==0) //if x is not find. ignore remove Query
            return;
        node *tt = _find(root,x); //have x is exist and tt->is_removed == 0
        tt->is_removed = 1; remove_count++;
        if(remove_count>=remove_node_bound)
        {
	    //rebuild_tree
	    rebuild();
	    remove_count = 0;
        }
    }
private:
    gh_init()
    {
        root = NULL;
    	remove_count = 0;
    }
    void rebuild()
    {
        new_root = NULL;

	//traverse.
	do_dfs(root,&new_root);
	remove_all(root);
	root = new_root;
    }
    void remove_all(node *cur)
    {
        if(cur==NULL)
            return;
        remove_all(cur->left);
        remove_all(cur->right);
        delete cur;
    }
    void do_dfs(node *cur,node **NEW_ROOT)
    {
        if(cur==NULL)
	    return;
        if(cur->is_removed==0)
	    add(NEW_ROOT,cur->num);
        do_dfs(cur->left,NEW_ROOT);
        do_dfs(cur->right,NEW_ROOT);
    }
    void add(node **root,int x)
    {
        node *cur,*tt;
        if(*root==NULL)
        {
            *root = make_node(x);
            return;
        }
	tt = _find(*root,x); //find node that have value x
	if(tt!=NULL)
	{
	    tt->is_removed = 0; remove_count--; return;
        }
        cur = *root;
        //find that where value x insert.
	while(1)
	{
	    int key = cur->num;
	    if(x<key)
	        tt = cur->left;
	    else
	        tt = cur->right;
	    if(tt==NULL)
		break;
	    cur = tt;
        }

        //ok. connect_node.
        _connect(cur,x);
    }
    void _connect(node *tar,int x)
    {
        if(x<(tar->num))
	    tar->left = make_node(x);
        else
            tar->right = make_node(x);
    }
    node *_find(node *root,int x)
    {
        node *cur = root;
    	while(cur!=NULL)
        {
    	    int key = cur->num;
    	    if(x<key)
    		cur = cur->left;
            else if(x>key)
    		cur = cur->right;
    	    else
    	        return cur;
	}
        return cur;
    }
    node *make_node(int x)
    {
        node *_new = new node;
        _new->num = x;
        _new->is_removed = 0;
        _new->left = _new->right = NULL;
        return _new;
    }
};
int main(void)
{
    gh_BST bst = gh_BST();
    bst.add(3); bst.add(7); bst.add(5); bst.remove(3);
    for(int i=0;i<500;i++)
        bst.add(i);
    for(int i=0;i<500;i++)
	bst.remove(4*i);
    for(int i=0;i<101;i++)
	printf("%d : %d\n",i,bst.find_num(i));
    return 0;
}