Binary Search Tree (二元搜尋樹)，是用來存放多筆資料，並快速搜尋的資料結構。大概的原則就是，大的放右邊，小的放左邊。
新增，刪除一個值都只要 \(O(log(N))\)
以下為實作範例
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
| #include
using namespace std;
template
class bst{
private:
struct node{
T val;
node* l,r;
node(){
l=r=nullptr;
}
node(T v){
l=r=nullptr;
val=v;
}
};
bool find(node *n,T v){
if(n->val==v){
return true;
}else if(n->val > v && n->r!=nullptr){
find(n->r,v);
}else if(n->val < v && n->l!=nullptr){
find(n->l,v);
}else{
return false;
}
}
void insert(node *&n,T v){
if(n==nullptr){
node nd=new node(v);
n=&nd;
}else if(n->val > v && n->r!=nullptr){
insert(n->r,v);
}else if(n->val < v && n->l!=nullptr){
insert(n->l,v);
}
}
void DeleteNode(node *&n){
if(n->l==nullptr && n->r==nullptr){
delete n;
n=nullptr;
}else{
node *left,*right;
if(n->l==nullptr){
right=n->r;
n->val=right->val;
n->l=right->l;
n->r=right->r;
delete right;
}else if(n->r==nullptr){
left=n->l;
n->val=left->val;
n->l=left->l;
n->r=left->r;
delete left;
}else{
right=n;
left=n->l;
while(left->r!=nullptr){
right=left;
left=left->l;
}
n->val=left->val;
if(right!=n)
right->r=left->l;
else
right->l=left->l;
delete left;
}
}
}
void erase(node *n,T v){
if(n->val==v){
DeleteNode(n);
}else if(n->val > v && n->r!=nullptr){
erase(n->r,v);
}else if(n->val < v && n->l!=nullptr){
erase(n->l,v);
}
}
void DeleteTree(node *n){
if(n->l!=nullptr)
DeleteTree(n->l);
if(n->r!=nullptr)
DeleteTree(n->r);
delete n;
}
public:
bst(){
root=nullptr;
sz=0;
}
~bst(){
if(root!=nullptr)
DeleteTree(root);
}
bool find(T v){
if(root!=nullptr)
return find(root,v);
}
void insert(T v){
if(root==nullptr){
node n=new node(v);
root=&n;
}else{
insert(root,v);
}
sz++;
}
void erase(T v){
if(root==nullptr) return;
erase(root,v);
sz--;
}
int size(){
return sz;
}
private:
node *root;
int sz;
};
|
相同的，C++都幫你做好了，就是所謂的Set & Map。
以下為使用範例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include
using namespace std;
int main(){
vector v(100);
for(int i=0;i<100;++i){
v[i]=i;
}
random_shuffle(v.begin(),v.end());
set s;
for(auto a:v){
s.insert(a);
}
random_shuffle(v.begin(),v.end());
for(auto a:v){
cout<<*s.lower_bound(a)<<" ";
cout<<*s.upper_bound(a)<<"\n";
}
s.erase(10);
cout<<*s.lower_bound(10);
}
|
我相信許多人跟我一樣，一開始不知道這些東西要用在哪？
以下我找了幾個範例
1. 在O(Nlog(26))以內找出是否有一個字母在兩個字串中均能被找到(題目連結：Two Strings | HackerRank)
1
2
3
4
5
6
7
8
9
10
11
12
| string twoStrings(string s1, string s2) {
set s;
for(auto a:s1){
s.insert(a);
}
for(auto a:s2){
if(s.count(a)){
return "YES";
}
}
return "NO";
}
|
2. 以O(N^3log(N))找出一個字串中無序變形子串對的數目(題目連結：Sherlock and Anagrams | HackerRank) 最重要的，就是其刪除快速的特性
1
2
3
4
5
6
7
8
9
| int sherlockAndAnagrams(string s) {
int ct=0,len=s.size();
for(int i=0;i st,tt;
for(int k=i;k<=j;k++){
st.insert(s[k]);
tt.insert(s[k]);
}
for(int k=i+1;k
|
3. 最後一個是Map的應用範例，Map是以first做排序依據，second存放對應資料。最常見的就是數字與出現頻率，以下甚至還有用來存頻率的頻率的用法。(題目連結：Frequency Queries | HackerRank) m 放<數字 , 頻率>，ct 放<頻率 , 頻率的頻率>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| vector freqQuery(vector<int> q) {
vector<int> ans;
map<int,int> m,ct;
for(auto a:q){
if(a[0]==1){
ct[m[a[1]]]=max(ct[m[a[1]]]-1,0);
m[a[1]]++;
ct[m[a[1]]]++;
}else if(a[0]==2){
ct[m[a[1]]]=max(ct[m[a[1]]]-1,0);
m[a[1]]=max(m[a[1]]-1,0);
ct[m[a[1]]]++;
}else{
ans.push_back(bool(ct[a[1]]));
}
}
return ans;
}
|
下一篇心得會補 pointer (指標) 的部分，在此之前可以先Google搜尋(C++指標)。`