hêm Node mới vào cây đỏ đen - Cấu trúc cây

void insert_case1(struct node *n) {
  if (n->parent == NULL)
    n->color = BLACK; 
  else insert_case2(n); 
}

void insert_case2(struct node *n) { 
  if (n->parent->color== BLACK) 
    return;
  else
    insert_case3(n); 
} 

void insert_case3(struct node *n) {
  if (uncle(n) != NULL && uncle(n)->color == RED) {
    n->parent->color = BLACK;
    uncle(n)->color = BLACK; grandparent(n)->color = RED;
    insert_case1(grandparent(n)); 
  } 
  else insert_case4(n); 
}

void insert_case4(struct node *n) { 
  if (n == n->parent->right && n->parent == grandparent(n)->left) {
    rotate_left(n->parent); n = n->left; } 
  else if (n == n->parent->left && n->parent == grandparent(n)->right) {
    otate_right(n->parent); n = n->right; 
  } 
  insert_case5(n);
}

void insert_case5(struct node *n) { 
  n->parent->color = BLACK; 
  grandparent(n)->color = RED; 
  if (n == n->parent->left && n->parent == grandparent(n)->left) {
    rotate_right(grandparent(n)); } 
  else {
    rotate_left(grandparent(n)); 
  } 
}

#include <iostream>
using namespace std; 
/* khai báo thuộc tính color */
enum Color {RED, BLACK}; 
/* khai báo cấu trúc node */
struct Node 
{ 
	int data; 
	bool color; 
	Node *left, *right, *parent; 

	// Constructor 
	Node(int data) 
	{ 
	this->data = data; 
	left = right = parent = NULL; 
	this->color = RED; 
	} 
}; 
/* class đại diện cho cây đỏ-đen */
class RBTree 
{ 
private: 
	Node *root; 
protected: 
	void rotateLeft(Node *&, Node *&); 
	void rotateRight(Node *&, Node *&); 
	void fixViolation(Node *&, Node *&); 
public: 
	/* Constructor */ 
	RBTree() { root = NULL; } 
	void insert(const int &n); 
	void inorder(); 
	// void levelOrder(); 
}; 

/* Một hàm đệ quy để thực hiện việc duyệt thứ tự cấp độ */
void inorderHelper(Node *root) 
{ 
	if (root == NULL) 
		return; 

	inorderHelper(root->left); 
	cout << root->data << " "; 
	inorderHelper(root->right); 
} 

/* insert Node  */
Node* BSTInsert(Node* root, Node *pt) 
{ 
	/* Nếu cây trống thì trả về một Node mới  */
	if (root == NULL) 
	return pt; 

	/* Nếu không thì tiếp tục duyệt xuống dưới cây */
	if (pt->data < root->data) 
	{ 
		root->left = BSTInsert(root->left, pt); 
		root->left->parent = root; 
	} 
	else if (pt->data > root->data) 
	{ 
		root->right = BSTInsert(root->right, pt); 
		root->right->parent = root; 
	} 

	/* trả về con trỏ Node */
	return root; 
} 

/* thuật toán xoay trái */
void RBTree::rotateLeft(Node *&root, Node *&pt) 
{ 
	Node *pt_right = pt->right; 

	pt->right = pt_right->left; 

	if (pt->right != NULL) 
		pt->right->parent = pt; 

	pt_right->parent = pt->parent; 

	if (pt->parent == NULL) 
		root = pt_right; 

	else if (pt == pt->parent->left) 
		pt->parent->left = pt_right; 

	else
		pt->parent->right = pt_right; 

	pt_right->left = pt; 
	pt->parent = pt_right; 
} 
/*thuật toán xoay phải*/
void RBTree::rotateRight(Node *&root, Node *&pt) 
{ 
	Node *pt_left = pt->left; 

	pt->left = pt_left->right; 

	if (pt->left != NULL) 
		pt->left->parent = pt; 

	pt_left->parent = pt->parent; 

	if (pt->parent == NULL) 
		root = pt_left; 

	else if (pt == pt->parent->left) 
		pt->parent->left = pt_left; 

	else
		pt->parent->right = pt_left; 

	pt_left->right = pt; 
	pt->parent = pt_left; 
} 

/* sửa lại cấu trúc khi chèn Node vào hoặc xóa node */
void RBTree::fixViolation(Node *&root, Node *&pt) 
{ 
	Node *parent_pt = NULL; 
	Node *grand_parent_pt = NULL; 

	while ((pt != root) && (pt->color != BLACK) && 
		(pt->parent->color == RED)) 
	{ 

		parent_pt = pt->parent; 
		grand_parent_pt = pt->parent->parent; 

		/* trường hợp A:
			Node cha của pt là con trái của Node cha của pt */
		if (parent_pt == grand_parent_pt->left) 
		{ 

			Node *uncle_pt = grand_parent_pt->right; 

			/* trường hợp : 1 
			Node chú của pt là Node đỏ khi này chỉ cần đổi màu cho Node đó thành đen */
			if (uncle_pt != NULL && uncle_pt->color == RED) 
			{ 
				grand_parent_pt->color = RED; 
				parent_pt->color = BLACK; 
				uncle_pt->color = BLACK; 
				pt = grand_parent_pt; 
			} 

			else
			{ 
				/* trường hợp : 2 
				pt là Node con phải của Node cha nó ta thực hiện xoay trái*/
				if (pt == parent_pt->right) 
				{ 
					rotateLeft(root, parent_pt); 
					pt = parent_pt; 
					parent_pt = pt->parent; 
				} 

				/* trường hợp : 3 
				pt là con trái của node cha nó ta thực hiện xoay phải */
				rotateRight(root, grand_parent_pt); 
				swap(parent_pt->color, grand_parent_pt->color); 
				pt = parent_pt; 
			} 
		} 

		/* trường hợp : B 
		Node cha của pt là con phải của Node cha của pt */
		else
		{ 
			Node *uncle_pt = grand_parent_pt->left; 

			/* trường hợp : 1 
				Node chú của pt là Node đỏ khi này chỉ cần đổi màu cho Node đó thành đen */
			if ((uncle_pt != NULL) && (uncle_pt->color == RED)) 
			{ 
				grand_parent_pt->color = RED; 
				parent_pt->color = BLACK; 
				uncle_pt->color = BLACK; 
				pt = grand_parent_pt; 
			} 
			else
			{ 
				/* Case : 2 
				pt là con trái của node cha nó ta thực hiện xoay phải */
				if (pt == parent_pt->left) 
				{ 
					rotateRight(root, parent_pt); 
					pt = parent_pt; 
					parent_pt = pt->parent; 
				} 

				/* Case : 3 
				pt là Node con phải của Node cha nó ta thực hiện xoay trái */
				rotateLeft(root, grand_parent_pt); 
				swap(parent_pt->color, grand_parent_pt->color); 
				pt = parent_pt; 
			} 
		} 
	} 

	root->color = BLACK; 
} 

/* chèn một Node mới với dữ liệu đã cho */
void RBTree::insert(const int &data) 
{ 
	Node *pt = new Node(data); 

	/* thực hiện chèn như bình thường */
	root = BSTInsert(root, pt); 

	/* sửa lại lỗi của quy tắc cây đỏ đen */ 
	fixViolation(root, pt); 
} 
 
void RBTree::inorder()	 { inorderHelper(root);} 

/* hàm main để thực hiện kiểm tra kết quả */
int main() 
{ 
	RBTree tree; 

	tree.insert(7); 
	tree.insert(6); 
	tree.insert(5); 
	tree.insert(4); 
	tree.insert(3); 
	tree.insert(2); 
	tree.insert(1); 

	cout << "Output: 
"; 
	tree.inorder(); 

  cout<<"
-------------------------------------
";
  cout<<"Chương trình này được đăng tại Zaidap.com.net";
}