[数据结构与算法]红黑树-插入-分配池

#include<iostream>
#include<vector>
#include<list>
using namespace std;
template<typename T>
class Pool {
public:
	int cnt;
	list<T*> unused;
	Pool(int n) {
		cnt = n;
		T* a = (T*)malloc(n * sizeof T);
		for (int i = 0; i < n; i++) {
			unused.push_back(&a[i]);
		}
	}
	T* ask() {
		if (unused.size()==0) {
			cnt <<= 1;
			T* a =(T*) malloc(cnt * sizeof T);
			for (int i = 0; i < cnt; i++) {
				unused.push_back(&a[i]);
			}
		}
		auto t = unused.front();
		unused.pop_front();
		return t;
	}
	void back(T* e) {
		unused.push_back(e);
	}
};
template<typename T>
class RBTree {
public:
	static constexpr bool black = true;
	static constexpr bool red = false;
	struct TreeNode {
		T val;
		TreeNode *left;
		TreeNode *right;
		TreeNode *parent;
		bool color;
		TreeNode() {}
		TreeNode(T v,TreeNode *nil,bool color) {
			left = right =parent= nil;
			val = v;
			this->color = color;
		}
	};
	Pool<TreeNode> pool=Pool<TreeNode>(10);
	TreeNode Nil;
	TreeNode* nil;
	TreeNode* root;
	RBTree() {
		nil = &Nil;
		Nil = TreeNode(0, nil, black);
		root = nil;
		//pool = Pool<TreeNode>(10);
	}

	void left_rotate(TreeNode* x) {
		auto y = x->right;
		x->right = y->left;
		if (y->left)y->left->parent = x;
		y->parent = x->parent;
		if (x->parent == nil)root = y;
		else if (x->parent->left == x)
			x->parent->left = y;
		else
			x->parent->right = y;
		y->left = x;
		x->parent = y;
	}
	void right_rotate(TreeNode* y) {
		auto x = y->left;
		y->left = x->right;
		if (x->right)x->right->parent = y;
		x->parent = y->parent;
		if (y->parent == nil) {
			root = x;
		}
		else if (y->parent->left == y)y->parent->left = x;
		else y->parent->right = x;
		x->right = y;
		y->parent = x;

	}
	void insert(T val) {
		auto x = root;
		auto y = nil;
		while (x != nil) {
			y = x;
			if (val == x->val)return;
			if (val < x->val)
				x = x->left;
			else
				x = x->right;
		}
		auto z = pool.ask(); // new TreeNode(val, nil, red);
		//pool.ask();
		z->parent=z->left = z->right = nil;
		z->val = val;
		z->color = red;
		z->parent = y;
		if (y == nil) {
			root = z;
		}
		else if (val < y->val) {
			y->left = z;
		}
		else {
			y->right = z;
		}
		rb_insert_fixup(z);
		//__asm int 3;
	}
	void rb_insert_fixup(TreeNode* z) {
		while (z->parent->color == red) {
			if (z->parent == z->parent->parent->left) {
				auto y = z->parent->parent->right;
				if (y->color == red) {
					z->parent->color = black;
					y->color = black;
					z->parent->parent->color = red;
					z = z->parent->parent;
				}
				else if (z == z->parent->right) {
					z = z->parent;
					left_rotate(z);
				}
				z->parent->color = black;
				z->parent->parent->color = red;
				right_rotate(z->parent->parent);
			}
			else {
				if (z->parent == z->parent->parent->right) {
					auto y = z->parent->parent->left;
					if (y->color == red) {
						z->parent->color = black;
						y->color = black;
						z->parent->parent->color = red;
						z = z->parent->parent;
					}
					else if (z == z->parent->left) {
						z = z->parent;
						right_rotate(z);
					}
					z->parent->color = black;
					z->parent->parent->color = red;
					left_rotate(z->parent->parent);
				}
			}
		}
		root->color = black;
	}
};
int main() {
	vector<int> test = { 1,2,3,4,5 ,34,34,34,5,34,25,4,2,9};
	RBTree<int> t;
	for (auto i : test) {
		t.insert(i);
	}
	cout << "t" << endl;
}