-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathBST.cpp
159 lines (132 loc) · 22.4 KB
/
BST.cpp
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
157
158
159
#include <iostream>
using namespace std;
class Btree {
public:
Btree *lchild, *rchild, *parent;
int val;
bool empty;
Btree () {
lchild = rchild = parent = NULL;
empty = true;
}
Btree (Btree *p) {
lchild = rchild = NULL;
parent = p;
empty = true;
}
bool insert(int x) {
if (empty) {
val = x;
empty = false;
return true;
}
if (x == val) return false;
if (x < val) {
if (lchild == NULL) lchild = new Btree(this);
return lchild->insert(x);
}
else {
if (rchild == NULL) rchild = new Btree(this);
return rchild->insert(x);
}
}
bool erase(int x) {
Btree *cur = this;
if (empty) return false;
if (val == x && lchild == NULL && rchild == NULL) return (empty = true);
while (cur != NULL) {
if (cur->val < x) cur = cur->rchild;
else if (cur->val > x) cur = cur->lchild;
else if (cur->val == x) {
if (cur->lchild == NULL && cur->rchild == NULL) {
if (cur->val < cur->parent->val) cur->parent->lchild = NULL;
else cur->parent->lchild = NULL;
delete cur;
}
else if (cur->lchild == NULL || cur->rchild == NULL) {
Btree *activ = (cur->lchild == NULL) ? cur->rchild : cur->lchild;
if (cur != this) {
if (cur->val < cur->parent->val) cur->parent->lchild = activ;
else cur->parent->rchild = activ;
activ->parent = cur->parent;
delete cur;
}
else {
this->val = activ->val;
this->lchild = activ->lchild;
this->rchild = activ->rchild;
if (activ->lchild != NULL) activ->lchild->parent = this;
if (activ->rchild != NULL) activ->rchild->parent = this;
delete activ;
}
}
else {
Btree *cur2 = cur->rchild;
while (cur2->lchild != NULL) cur2 = cur2->lchild;
cur->val = cur2->val;
if (cur2->rchild != NULL) cur2->rchild->parent = cur2->parent;
if (cur2 != cur->rchild) cur2->parent->lchild = cur2->rchild;
else cur->rchild = cur2->rchild;
delete cur2;
}
return true;
}
}
return false;
}
int minimum() {
if (empty) return 0;
Btree *cur = this;
while (cur->lchild != NULL) cur = cur->lchild;
return cur->val;
}
int maximum() {
if (empty) return 0;
Btree *cur = this;
while (cur->rchild != NULL) cur = cur->rchild;
return cur->val;
}
bool search(int x) {
if (empty) return false;
Btree *cur = this;
while (cur != NULL) {
if (cur->val == x) return true;
if (cur->val < x) cur = cur->rchild;
else cur = cur->lchild;
}
return false;
}
void printTree() {
if (empty) return;
cout << val << endl;
if (lchild != NULL) lchild->printTree();
if (rchild != NULL) rchild->printTree();
}
int treeHeight() {
if (empty) return 0;
if (lchild == NULL && rchild == NULL) return 1;
if (lchild == NULL) return 1+rchild->treeHeight();
if (rchild == NULL) return 1+lchild->treeHeight();
int x = lchild->treeHeight();
int y = rchild->treeHeight();
return (x > y) ? 1 + x : 1 + y;
}
};
int main() {
//int ar[13] = {58, 43, 89, 5, 92, 55, 78, 12, 59, 60, 57, 44, 9};
//int ar[1000] = {512,484,384,831,330,937,848,993,961,295,194,812,960,948,569,551,357,260,554,694,666,698,725,27,718,382,144,169,539,516,450,671,908,799,751,572,527,374,920,505,351,79,765,870,835,942,724,317,888,404,311,7,464,104,632,456,613,370,497,78,476,528,112,851,790,677,558,535,487,229,167,1000,995,899,798,332,935,626,252,876,737,651,531,574,440,616,438,914,855,661,10,911,860,321,343,301,45,134,221,997,388,186,223,869,599,279,124,314,591,738,954,620,15,419,364,827,773,985,407,610,900,269,910,231,132,288,976,905,242,829,830,267,258,58,306,365,716,299,594,190,9,240,538,165,936,676,216,726,839,968,734,679,580,452,232,760,781,652,727,437,681,822,277,449,655,432,650,492,928,880,405,788,854,889,406,982,557,951,203,26,916,244,627,966,534,369,89,978,422,39,824,624,37,786,901,918,644,181,930,619,946,86,206,197,371,420,592,635,265,776,879,14,926,933,924,867,219,949,335,172,127,211,302,904,548,774,445,508,581,153,398,883,988,590,710,699,593,584,272,155,55,701,828,753,76,573,106,598,128,408,818,322,510,777,483,680,168,625,300,157,377,41,784,515,336,205,481,602,410,958,750,256,567,866,659,139,413,703,865,501,801,601,767,696,642,940,959,519,62,188,109,94,922,517,766,843,49,653,176,833,813,998,380,672,712,972,105,171,791,166,183,588,945,511,756,804,372,28,706,705,614,950,649,504,146,133,455,430,742,891,695,639,787,227,271,225,463,40,875,637,682,887,349,152,746,433,473,923,389,98,503,743,506,638,992,444,543,552,498,179,513,137,631,686,986,732,518,496,736,423,938,102,857,864,542,585,636,378,141,38,312,373,292,852,797,873,643,885,586,667,709,733,30,526,65,100,478,425,114,859,654,544,697,560,110,475,66,151,326,352,846,832,93,461,395,48,886,237,290,907,987,90,344,8,291,143,368,841,414,387,316,195,549,71,459,474,446,622,42,178,546,991,579,274,147,685,174,393,325,80,251,164,720,715,226,570,708,193,436,189,844,913,964,239,163,739,64,895,383,717,536,714,310,135,72,597,426,201,323,996,795,97,3,333,688,362,820,113,234,275,657,660,994,366,161,284,847,711,884,298,328,495,502,929,989,521,647,149,88,11,856,962,394,96,358,324,353,741,775,73,956,367,648,442,25,122,142,491,603,927,693,744,629,975,808,118,656,415,819,385,67,477,222,235,20,772,939,17,209,524,435,51,881,198,973,409,596,882,555,348,541,60,361,817,868,162,466,457,479,689,92,675,566,24,944,123,192,612,187,350,984,589,838,814,621,44,894,480,890,903,963,571,559,509,138,23,809,346,853,83,391,280,537,6,806,213,191,259,778,934,952,605,977,447,897,262,723,82,411,61,811,999,1,69,600,173,273,70,293,606,943,360,303,754,354,21,970,700,36,158,13,678,983,224,540,276,877,441,892,85,87,261,74,103,412,448,692,283,957,443,562,318,490,702,931,615,402,329,595,381,489,713,136,210,16,427,247,861,159,604,19,18,460,730,893,618,690,623,467,740,507,729,979,429,43,130,561,834,925,12,289,955,845,764,243,263,947,107,523,783,807,921,182,397,611,825,617,645,974,906,981,530,250,793,451,22,763,752,771,116,375,230,990,108,469,576,228,520,969,305,748,840,296,320,126,416,309,184,836,800,208,52,278,308,762,32,707,202,304,431,896,683,84,909,282,63,722,386,687,233,5,803,902,550,339,486,953,68,54,669,99,340,485,264,529,874,545,980,789,802,719,482,327,578,563,342,607,218,609,815,150,266,785,745,400,220,428,965,779,583,338,691,129,757,794,212,345,75,241,46,341,81,749,185,810,238,731,472,454,217,257,140,379,863,465,556,673,755,294,608,253,565,872,634,662,77,286,196,878,56,500,915,842,347,458,390,837,57,170,34,919,525,522,628,95,494,287,356,424,805,121,499,568,115,826,633,199,493,780,59,862,214,453,917,912,823,971,363,640,313,770,154,307,101,533,131,297,396,759,668,156,821,577,488,246,4,664,796,245,434,871,177,145,117,850,355,735,248,254,646,858,658,967,547,120,376,849,204,468,462,575,582,268,439,200,331,587,932,665,532,319,281,898,2,941,236,721,401,160,215,768,125,674,747,630,180,684,392,816,270,29,249,285,421,359,119,418,758,553,670,91,33,782,641,207,399,47,334,337,50,53,761,564,111,315,255,471,728,704,514,769,35,470,792,417,403,175,663,148,31};
//int ar[1000] = {336,798,936,717,426,79,110,213,407,3,689,702,520,28,939,364,402,254,498,875,976,416,351,125,107,884,303,310,492,704,410,738,316,105,98,468,523,321,212,859,257,486,332,92,376,269,338,378,270,578,405,573,17,233,66,311,58,449,805,380,372,816,956,862,955,393,545,340,958,220,291,132,289,883,94,629,72,36,530,43,542,758,967,789,352,621,632,981,245,590,63,55,565,119,50,740,346,93,412,597,39,698,33,749,610,787,786,96,716,942,304,124,908,341,580,561,297,281,790,440,536,102,957,526,646,952,527,841,593,400,672,588,779,807,950,558,755,169,819,624,533,854,826,61,522,817,157,184,609,343,954,174,528,10,122,423,84,611,941,101,885,394,40,968,469,990,1000,535,739,921,131,620,818,464,120,541,322,989,985,299,5,15,615,248,454,46,960,671,278,42,843,935,478,238,300,907,663,457,858,22,165,674,998,932,475,337,294,69,123,214,614,775,485,371,267,982,945,201,171,179,661,878,722,176,691,647,73,595,318,463,612,726,970,705,482,650,791,356,625,193,766,827,540,313,133,501,694,80,189,315,940,265,570,751,24,210,654,853,366,285,112,532,589,224,929,166,333,1,660,504,445,729,414,913,509,144,813,683,2,219,205,892,312,4,272,225,173,418,190,891,396,9,437,493,348,223,222,557,239,301,104,745,476,150,997,216,548,948,404,637,525,979,840,32,906,403,823,85,44,851,447,645,847,806,182,635,607,435,842,87,995,496,741,734,700,746,436,814,850,27,937,825,466,569,195,519,461,712,897,235,568,596,111,203,616,988,425,54,23,65,577,673,246,769,253,489,549,415,656,155,606,562,431,424,388,206,191,553,370,162,392,217,167,306,508,236,634,919,99,103,52,232,707,41,383,756,71,977,284,890,666,186,78,873,572,89,361,275,856,848,59,218,385,969,7,156,263,870,922,855,994,314,546,490,759,279,713,256,250,503,727,665,537,784,864,391,129,320,833,603,470,677,90,782,113,860,443,428,187,555,793,181,966,274,398,365,283,130,761,148,866,368,780,949,77,835,154,886,208,432,765,211,898,178,531,648,742,641,495,834,128,917,664,731,243,972,325,598,992,594,678,975,421,38,31,838,947,369,667,252,820,776,643,772,872,516,785,64,688,809,682,379,720,434,390,363,323,244,373,747,659,512,773,915,762,229,586,914,158,67,497,121,876,21,987,770,8,579,453,240,591,781,139,177,168,905,599,735,613,207,584,559,829,242,507,703,465,748,334,887,146,395,12,799,639,996,441,511,472,467,273,583,743,48,752,926,778,693,286,651,83,374,138,638,317,474,587,830,800,430,592,82,455,473,295,695,506,422,753,619,456,564,280,427,151,109,51,75,721,684,600,711,900,925,328,803,117,194,852,353,618,552,631,448,889,260,477,53,581,29,14,57,802,963,993,946,845,797,502,180,451,147,822,566,910,345,188,953,230,933,633,287,227,839,487,35,943,585,276,114,623,221,259,355,728,172,152,757,744,204,928,828,145,602,869,846,74,923,551,554,668,499,335,815,479,296,484,255,924,185,604,6,357,980,543,460,47,560,556,389,534,136,896,20,175,737,812,681,630,837,582,142,384,268,34,724,399,810,658,652,971,863,777,877,792,226,25,518,282,676,670,916,358,444,709,796,951,920,699,974,359,701,576,601,298,733,962,16,141,964,408,934,329,308,754,575,763,11,339,56,419,362,60,690,505,344,196,510,81,961,30,261,730,161,811,450,861,347,867,488,452,521,986,524,18,251,198,692,538,288,231,330,836,874,37,517,795,973,367,68,893,197,458,868,642,302,324,653,153,723,382,13,331,831,871,115,349,127,429,307,97,708,438,19,732,237,483,944,215,514,865,375,626,116,433,999,327,669,984,417,420,774,108,627,200,821,938,927,76,49,710,350,794,849,164,202,771,491,62,832,715,563,904,143,342,888,377,86,857,644,959,675,931,149,91,628,45,513,500,192,360,808,679,529,88,134,406,292,264,305,183,271,386,911,266,387,567,471,617,228,901,290,446,126,696,326,788,199,247,718,401,319,801,918,459,137,70,481,293,170,655,515,249,160,657,608,605,880,106,881,277,909,571,983,978,686,209,930,135,241,439,764,965,912,680,736,902,882,397,26,879,159,411,234,442,258,662,409,494,539,687,100,783,804,640,706,262,768,462,636,714,140,697,480,894,547,824,574,309,719,622,163,381,550,991,767,903,649,895,899,544,844,118,760,95,413,685,725,354,750};
//int ar[1000] = {821,985,399,55,182,796,852,400,354,910,688,93,60,289,51,832,286,787,670,931,590,283,101,785,478,512,119,504,112,650,338,733,988,635,65,33,145,827,458,724,307,680,869,339,759,189,806,403,691,82,76,858,447,864,402,27,265,346,863,603,195,610,609,17,9,409,531,628,715,845,928,710,4,327,633,367,45,46,132,143,882,908,972,424,995,747,754,658,993,602,558,303,330,413,50,359,704,480,358,788,879,345,344,643,757,790,746,660,833,280,503,37,241,467,830,880,883,846,23,829,666,575,904,687,723,260,573,807,935,701,393,717,110,408,533,315,124,588,441,106,876,228,513,947,434,868,653,662,663,44,545,32,793,274,391,613,460,385,619,851,678,874,933,39,979,949,692,341,194,577,79,945,983,353,349,350,528,179,555,607,946,239,211,745,114,370,206,708,185,968,405,537,99,380,287,703,284,895,888,699,776,494,621,309,210,941,530,987,732,999,615,559,889,501,891,819,314,978,900,237,959,3,394,165,257,248,97,805,568,835,932,884,397,252,877,267,181,153,340,277,332,279,726,565,608,561,546,734,844,887,476,926,316,167,113,123,552,251,233,668,141,490,803,306,38,224,42,689,180,526,174,918,861,673,94,969,506,760,268,510,404,814,557,161,737,495,129,616,924,226,991,955,70,902,743,342,669,604,765,913,866,58,379,10,131,587,264,214,336,373,105,768,294,771,570,940,28,794,556,360,534,269,720,795,171,420,406,164,418,445,41,52,192,524,578,240,713,977,774,415,571,96,270,465,865,617,664,834,302,966,825,641,714,953,68,448,997,784,872,547,422,100,389,371,599,378,421,323,230,440,554,914,744,739,742,529,538,116,84,515,725,329,470,826,849,75,917,773,333,894,994,862,281,705,652,563,190,986,209,102,899,223,842,954,786,878,386,461,647,502,207,80,216,499,696,254,516,854,126,801,168,292,337,927,320,782,134,756,423,288,13,614,831,684,31,541,697,560,215,295,853,812,125,232,580,567,922,475,536,752,921,387,34,313,543,594,685,626,939,998,605,15,761,158,677,85,631,451,544,462,618,275,482,234,532,712,920,574,638,962,271,850,69,535,870,25,81,300,7,363,442,893,276,963,948,656,750,104,24,818,22,671,855,792,272,177,549,627,361,885,488,859,304,362,375,758,611,828,509,716,443,427,155,956,412,78,166,992,11,197,915,159,967,376,753,816,937,636,706,351,16,493,238,881,637,321,87,514,118,449,26,702,120,740,140,707,29,952,172,675,301,151,308,163,219,551,95,989,390,184,147,258,654,218,838,36,905,466,797,259,203,53,205,62,582,152,646,127,256,749,620,200,86,735,202,542,176,417,965,103,592,923,148,798,398,840,245,366,736,644,769,822,589,63,649,896,242,468,67,453,907,61,396,318,572,401,175,428,598,511,273,778,54,57,491,48,837,348,974,860,262,1000,721,976,906,74,381,873,425,719,811,755,766,298,804,160,690,111,49,942,489,170,278,59,738,486,523,507,624,780,763,960,820,950,990,414,585,630,73,263,799,823,18,98,77,310,674,971,249,958,802,481,867,220,634,665,606,452,683,497,951,253,681,729,225,483,250,595,221,133,229,450,146,645,591,925,372,6,235,374,808,593,471,597,137,622,682,625,651,326,419,640,777,709,66,431,522,661,672,88,139,311,382,136,550,767,727,142,150,487,154,848,231,285,243,377,562,178,357,824,90,266,875,981,322,581,436,317,871,149,217,222,903,43,569,305,508,438,331,492,700,897,12,109,919,319,444,964,186,975,961,433,667,347,20,718,365,14,410,35,980,474,247,108,477,92,584,47,187,432,290,352,199,676,117,890,639,973,2,657,698,770,695,364,540,479,586,144,472,115,520,728,996,196,566,694,122,936,107,841,296,901,169,548,383,369,213,335,679,193,426,343,623,356,121,201,282,457,934,886,255,236,930,632,579,130,188,498,435,539,984,72,473,813,198,521,446,898,686,395,527,741,601,596,291,970,839,843,779,429,173,916,800,929,244,751,564,324,8,722,204,227,21,411,293,912,810,583,789,469,19,430,764,368,517,30,781,334,519,815,496,525,455,325,456,748,208,648,83,312,246,892,943,183,600,91,1,162,957,783,459,454,944,500,299,505,817,731,809,157,40,642,711,416,5,553,191,328,71,655,982,392,156,772,730,388,56,938,629,135,836,518,384,576,407,762,463,89,439,212,856,297,64,791,847,693,485,484,138,464,612,355,857,911,775,909,659,261,128,437};
//int ar[1000] = {510,255,391,822,272,657,419,233,802,622,160,757,735,456,953,117,936,8,467,187,896,804,158,668,973,372,589,125,153,163,586,71,4,803,600,287,157,145,579,974,663,845,161,344,283,981,940,958,962,581,765,640,816,77,647,840,800,654,38,563,262,361,756,639,770,141,764,165,214,380,368,370,83,776,334,366,566,813,132,156,775,995,86,130,662,22,952,723,619,594,286,120,747,65,931,606,972,985,465,500,444,711,104,159,538,485,92,191,201,820,149,256,339,682,841,437,661,309,466,630,304,740,565,894,399,166,897,207,568,580,520,422,527,596,858,429,702,302,381,121,611,230,267,496,560,285,677,535,649,531,220,337,930,638,695,323,796,628,468,274,470,616,805,134,924,460,79,114,27,688,205,552,66,551,373,667,674,629,139,946,826,29,717,102,239,523,403,100,222,737,669,246,969,28,605,45,327,862,676,152,578,282,123,265,58,704,778,440,91,87,861,335,902,950,752,247,454,355,294,701,821,637,644,681,321,650,646,407,691,41,558,330,970,798,686,462,290,543,266,693,607,869,595,827,308,588,501,835,847,455,811,305,111,39,874,912,319,920,234,318,181,400,923,258,2,509,866,128,736,959,82,808,618,817,70,684,968,89,461,521,511,534,363,430,642,679,15,252,748,793,947,828,224,990,801,506,751,475,544,621,781,762,424,809,576,226,537,175,784,434,708,999,948,476,982,597,739,887,921,792,901,481,954,126,540,281,81,856,477,846,67,398,592,945,749,301,480,991,442,225,216,795,263,208,49,346,689,40,487,859,240,325,203,730,885,169,32,54,33,505,574,512,876,609,115,984,357,742,452,844,536,656,932,333,546,122,881,260,643,660,683,312,766,699,819,554,728,872,474,497,377,880,417,612,138,997,838,367,199,88,721,573,227,85,218,185,577,326,503,307,155,855,696,275,738,499,490,178,418,164,96,195,210,347,483,463,507,75,237,310,479,402,144,625,235,758,143,450,518,956,645,53,113,830,297,967,971,832,349,769,865,610,992,868,978,697,1,949,652,360,448,7,727,212,712,977,489,94,547,46,172,836,553,925,522,17,47,993,150,351,432,13,929,582,829,525,180,306,292,374,634,401,545,933,559,515,340,720,893,755,288,900,966,209,184,726,119,602,864,148,705,317,331,541,137,833,451,587,567,406,97,548,56,200,295,192,753,504,445,583,118,529,732,389,177,385,570,395,273,779,168,449,659,189,561,825,706,397,369,911,714,680,410,698,271,575,98,987,983,899,539,910,744,996,413,136,707,176,390,238,774,341,760,731,382,857,50,447,124,428,675,236,593,186,342,905,458,904,549,182,425,231,299,311,63,215,315,773,524,313,850,190,963,700,415,528,129,834,101,472,431,293,935,492,482,336,188,217,743,783,895,672,1000,943,789,807,278,584,277,898,746,441,95,202,59,494,608,965,892,818,670,244,571,80,648,934,564,16,110,211,133,626,514,975,614,848,761,799,43,93,854,228,599,396,655,651,131,469,979,261,51,603,741,867,791,918,919,320,371,457,251,23,488,690,635,871,127,797,276,782,471,926,831,733,870,269,378,710,519,426,196,502,624,353,219,842,343,658,459,863,433,665,206,532,878,332,780,620,666,889,303,692,718,598,364,248,68,420,843,937,245,109,694,6,421,873,913,938,891,517,927,942,944,906,140,197,242,386,103,37,439,31,961,613,9,473,193,729,329,154,785,412,585,392,810,671,464,105,653,879,280,204,34,557,11,60,941,62,641,980,394,888,20,928,491,36,530,860,939,174,416,270,69,988,562,384,678,664,812,221,627,886,183,914,790,715,435,569,162,170,917,767,249,30,703,404,322,883,73,484,875,167,48,12,542,314,673,754,354,436,772,84,722,890,106,259,636,232,414,135,725,851,213,951,151,771,300,291,724,633,18,632,173,409,393,601,254,884,550,815,26,21,631,19,61,453,986,508,533,44,604,76,268,994,223,915,328,241,768,909,493,264,74,250,877,998,379,438,824,903,362,446,787,788,955,25,112,279,849,759,687,108,387,423,171,590,763,572,907,556,78,146,408,882,908,350,298,99,615,194,427,617,5,806,916,359,989,35,358,243,147,3,852,745,345,486,14,526,964,64,388,116,709,179,142,365,777,257,42,443,786,316,922,591,495,685,90,338,375,555,229,296,750,55,107,356,960,516,837,284,198,57,376,352,498,10,976,253,348,719,513,411,383,405,734,72,957,324,794,823,713,478,52,853,716,839,289,24,814,623};
int ar[1000] = {42,80,223,726,140,155,332,791,724,50,196,562,738,312,392,407,523,145,144,497,834,615,700,401,55,8,855,669,106,706,940,827,342,284,256,944,377,797,44,611,229,803,380,749,354,289,522,994,200,434,716,383,412,979,14,297,164,350,415,165,841,559,864,36,488,126,704,273,642,923,157,220,851,158,778,811,971,12,447,480,675,524,911,767,598,537,603,22,154,381,201,552,743,204,261,576,542,956,37,891,9,659,368,244,278,776,589,35,298,411,881,450,409,275,18,263,105,385,286,397,170,900,909,627,212,213,404,331,98,63,889,847,873,632,51,679,408,886,609,921,959,95,394,115,922,761,772,309,390,899,833,777,546,271,965,686,582,340,533,29,823,835,373,300,991,990,581,729,424,525,672,810,11,64,403,684,475,579,737,795,133,968,938,820,801,277,175,230,894,114,813,343,815,137,375,532,662,172,499,1000,351,676,764,400,858,498,417,751,7,292,668,327,902,771,238,929,521,208,520,217,528,602,156,766,136,677,287,748,983,419,860,784,650,339,879,347,70,604,195,918,26,10,247,81,370,689,31,20,279,313,210,804,512,301,514,688,722,333,745,89,585,91,96,304,322,568,560,211,262,494,160,648,365,999,358,703,674,250,943,99,290,159,405,483,633,770,792,624,361,147,570,502,631,930,258,907,414,107,896,870,316,877,402,53,536,736,465,112,960,251,840,246,474,199,427,452,357,618,890,268,48,454,425,167,948,186,65,727,619,338,622,719,946,548,329,717,470,395,698,75,283,865,124,104,135,364,382,254,183,461,323,871,185,744,25,207,526,138,23,678,932,472,288,859,169,760,237,732,816,162,28,794,728,809,664,644,436,515,82,713,360,442,266,94,599,267,849,549,984,850,534,931,484,605,550,317,202,67,326,963,782,989,853,253,584,509,435,307,482,378,516,692,444,74,49,234,87,623,441,606,867,756,996,765,601,260,457,660,663,346,721,6,975,862,969,527,125,471,812,808,848,747,895,468,203,638,161,374,398,556,389,590,910,174,384,303,796,39,216,973,168,819,793,473,733,491,226,846,459,788,116,148,192,496,219,742,555,682,336,143,966,709,393,759,557,386,255,372,321,683,714,861,594,652,17,634,769,276,489,666,58,866,802,233,428,56,593,315,654,887,953,731,388,892,437,206,88,933,318,725,935,754,302,790,198,583,453,406,177,807,166,163,863,93,487,997,592,653,843,661,529,800,567,190,597,430,490,52,832,224,667,152,90,699,121,626,257,314,122,19,985,69,328,269,752,353,134,118,410,191,694,387,97,433,21,893,976,730,898,912,100,836,906,656,544,493,218,718,103,319,565,399,586,282,695,814,123,578,715,920,176,735,109,955,464,610,440,993,451,43,977,543,951,854,335,651,712,241,711,264,33,421,882,324,780,57,571,423,680,914,510,517,799,945,775,639,111,779,620,60,16,265,829,61,429,108,438,187,934,420,27,46,92,561,426,974,334,281,205,117,455,232,376,129,913,643,504,507,486,179,101,54,84,15,245,707,998,839,670,443,740,588,299,671,467,66,757,479,746,629,705,32,646,345,982,741,617,995,173,272,852,987,130,702,171,658,868,883,837,68,41,34,236,970,758,422,194,131,325,988,949,243,222,962,363,572,62,416,924,755,113,830,768,305,647,503,24,723,928,826,540,554,38,708,806,348,573,45,925,563,596,492,73,231,818,110,885,821,151,880,950,240,418,828,371,577,71,193,844,541,628,188,448,259,888,291,822,295,239,308,341,831,501,366,904,449,875,876,462,13,355,967,508,986,142,30,413,690,311,228,227,635,456,941,362,856,83,927,625,673,458,917,591,367,872,630,280,180,242,330,936,789,352,120,786,150,545,76,481,681,79,432,916,445,86,539,884,587,184,558,937,580,939,600,961,739,310,901,396,696,569,344,824,181,4,518,379,685,139,908,616,197,78,972,825,478,649,476,915,655,146,720,595,274,750,431,477,252,359,466,439,149,47,535,645,612,575,460,296,942,903,608,215,574,773,306,783,531,221,77,640,182,249,641,2,349,869,519,3,957,978,178,838,551,72,958,980,607,753,270,547,59,235,926,225,785,1,85,320,40,469,992,878,553,102,787,248,566,657,897,781,905,153,687,506,701,128,710,446,189,857,613,954,369,774,805,845,636,874,762,637,485,842,209,500,119,293,5,697,141,511,127,285,564,952,817,665,947,513,391,505,214,798,356,734,495,919,463,981,294,337,691,614,132,530,621,763,538,693,964};
Btree x;
for (int i = 0; i < sizeof(ar)/sizeof(ar[0]); i++) x.insert(ar[i]);
//x.printTree();
cout << endl << x.treeHeight() << endl << endl;
// for (int i = 0; i < 1000; i++) {
// int m = x.minimum();
// cout << m << ' ';
// x.erase(m);
// }
cout << endl;
}