red-black-tree.cpp

// incomplete

#include <iostream>
using namespace std;

class RBT {
public:

	struct Node;
	Node *root, *nil;

	RBT () {
		nil = new Node();
		root = nil;
	}

	struct Node {
		Node *lchild, *rchild, *parent;
		int val;
		bool isBlack;

		Node () {
			rchild = lchild = parent = NULL;
			isBlack = true;
		}
		Node (Node* p) {
			rchild = lchild = NULL;
			parent = p;
			isBlack = false;
		}
		void printNodes(Node *nil) {
			cout << val << ' ' << ((isBlack) ? "black" : "red") << endl;
			if (lchild != nil) lchild->printNodes(nil);
			if (rchild != nil) rchild->printNodes(nil);
		}
		int NodeLevel(Node *nil) {
			if (lchild == nil && rchild == nil) return 1;
			if (lchild == nil) return 1+rchild->NodeLevel(nil);
			if (rchild == nil) return 1+lchild->NodeLevel(nil);
			int x = lchild->NodeLevel(nil);
			int y = rchild->NodeLevel(nil);
			return (x > y) ? 1 + x : 1 + y;
		}
	};

	void left_rotate(Node *p) {
		Node *x = p->rchild;
		if (x == nil) return;

		if (p != root) {
			if (p->parent->lchild == p) p->parent->lchild = x;
			else p->parent->rchild = x;
		}
		else root = x;
		p->rchild = x->lchild;
		if (x->lchild != nil) x->lchild->parent = p;
		x->lchild = p;
		x->parent = p->parent;
		p->parent = x;
	}

	void right_rotate(Node *p) {
		Node *x = p->lchild;
		if (x == nil) return;

		if (p != root) {
			if (p->parent->lchild == p) p->parent->lchild = x;
			else p->parent->rchild = x;
		}
		else root = x;
		p->lchild = x->rchild;
		if (x->rchild != nil) x->rchild->parent = p;
		x->rchild = p;
		x->parent = p->parent;
		p->parent = x;
	}

	bool insert(int k) {
		Node *cur = root;
		Node *cur2 = nil;

		while (cur != nil) {
			cur2 = cur;
			if (cur->val == k) return false;
			if (cur->val < k) cur = cur->rchild;
			else cur = cur->lchild;
		}
		Node *z = new Node(cur2);
		z->val = k;
		z->lchild = z->rchild = nil;

		if (cur2 == nil) root = z;
		else if (cur2->val < k) cur2->rchild = z;
		else cur2->lchild = z;

		while (!z->parent->isBlack) {
			Node *y;						// y is uncle of z

			if (z->parent->parent->lchild == z->parent) y = z->parent->parent->rchild;
			else y = z->parent->parent->lchild;

			if (!y->isBlack) {
				z->parent->isBlack = true;
				y->isBlack = true;
				y->parent->isBlack = false;
				z = y->parent;
			}
			else {
				if (y == z->parent->parent->rchild) {
					if (z == z->parent->lchild) {
						z->parent->isBlack = true;
						z->parent->parent->isBlack = false;
						right_rotate(z->parent->parent);
					}
					else {
						left_rotate(z->parent);
						right_rotate(z->parent);
						z->isBlack = true;
						z->rchild->isBlack = false;
					}
				}
				else {
					if (z == z->parent->rchild) {
						z->parent->isBlack = true;
						z->parent->parent->isBlack = false;
						left_rotate(z->parent->parent);
					}
					else {
						right_rotate(z->parent);
						left_rotate(z->parent);
						z->isBlack = true;
						z->lchild->isBlack = false;
					}
				}
				break;
			}
		}
		root->isBlack = true;
		return true;
	}

	int minimum() {
		if (root == nil) return 0;
		Node *cur = root;

		while (cur->lchild != nil) cur = cur->lchild;
		return cur->val;
	}

	int maximum() {
		if (root == nil) return 0;
		Node *cur = root;

		while (cur->rchild != nil) cur = cur->rchild;
		return cur->val;
	}

	bool search(int x) {
		Node *cur = root;
		while (cur != nil) {
			if (cur->val == x) return true;
			if (cur->val < x) cur = cur->rchild;
			else cur = cur->lchild;
		}
		return false;
	}

	void printTree() {
		if (root == nil) return;
		root->printNodes(nil);
	}

	int treeHeight() {
		if (root == nil) return 0;
		return root->NodeLevel(nil);
	}

};

int main() {
	//int ar[13] = {58, 43, 89, 5, 92, 55, 78, 12, 59, 60, 57, 44, 9};
	//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[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
	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};
	RBT 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 < 13; i++) {
	// 	int m = x.minimum();
	// 	cout << m << ' ';
	// 	x.erase(m);
	// }
	cout << endl;
}