Chuong trinh cay do den
0 likes299 views
1. The document describes operations on red-black trees, which are self-balancing binary search trees. It includes functions for inserting and deleting nodes from the tree while maintaining the red-black properties. 2. Functions are provided for getting a new node, performing basic insertion into the binary search tree, and then fixing any violations of the red-black properties during insertion. 3. Similarly for deletion, a function searches for a node to delete, removes it from the tree, and then fixes any red-black property violations caused by the deletion.
Chuong trinh cay do den
- 1. 1 RedBlack Tree 2 typedef structnode * ref; struct node { int key; int color; ref parent; ref left; ref right; } ref getnode(int key, int color, ref nil) { p = new node; p>key = key; p>color = color; p>left = p>right = p>parent = nil; return p; } ref nil, root; nil = new node; nil>color = BLACK; nil>left = nil>right = nil>parent = nil; root = nil;
- 2. 3 void leftRotate(ref &root, ref x) { ref nil = root>parent; y = x>right; x>right = y>left; if (y>left != nil) y>left>parent = x; y>parent = x>parent; if (x>parent == nil) root = y; else if (x == x>parent>left) x>parent>left = y; else x>parent>right = y; y>left = x; x>parent = y; } 4 void RBT_Insertion(ref &root, int key) { x = getNode(key, RED, NIL); BST_Insert(root, x); Insertion_FixUp(root, x); } Thao t叩c th棚m ph畉n t畛
- 3. 5 void BST_Insert(ref &root, ref x) { ref nil = root>parent; y = nil; z = root; while (z != nil) { y = z; if (x>key < z>key) z = z>left; else z = z>right; } x>parent = y; if (y == nil) root = x; else if (x>key < y>key) y>left = x; else y>right = x; } 6 void Insertion_FixUp(ref &root, ref x) { while (x>parent>color == RED) if (x>parent == x>parent>parent>left) ins_leftAdjust(root, x); else ins_rightAdjust(root, x); root>color = BLACK; }
- 4. 7 void ins_leftAdjust(ref &root, ref &x) { u = x>parent>parent>right; if (u>color == RED) { // TH 2 x>parent>color = BLACK; u>color = BLACK; x>parent>parent>color = RED; x = x>parent>parent; } else { if (x == x>parent>right) { // TH 4 x = x>parent; leftRotate(root, x); } // TH 3 x>parent>color = BLACK; x>parent>parent>color = RED; rightRotate(root, x>parent>parent); } } 8 Thao t叩c x坦a ph畉n t畛
- 5. 9 void RBT_Deletion(ref &root, int k) { z = searchTree(root, k); if (z == nil) return; y = ((z>left == nil) || (z>right == nil)) ? z : TreeSuccessor(root, z); x = (y>left == nil) ? y>right : y>left; x>parent = y>parent; if (y>parent == nil) root = x; else if (y == y>parent>left) y>parent>left = x; else y>parent>right = x; if (y != z) { z>key = y>key; z>color = y>color; } if (y>color == BLACK) Deletion_FixUp(root, x); free(y); } 10 void Deletion_FixUp(ref root, ref x) { while ((x->color == BLACK) && (x != root)) if (x == x->parent->left) del_leftAdjust(root, x); else del_rightAdjust(root, x); x->color = BLACK; // TH 1 }
- 6. 11 void del_leftAdjust(ref &root, ref &x) { w = x->parent->right; if (w->color == RED) { // TH 3 w->color = BLACK; x->parent->color = RED; leftRotate(root, x->parent); w = x->parent->right; } // TH 2 if ((w->right->color == BLACK) && (w->left->color == BLACK)) { w->color = RED; x = x->parent; } else { if (w->right->color == BLACK) { // TH 4 (i) w->left->color= BLACK; w->color = RED; rightRotate(root, w); w = x->parent->right; } // TH 4 (ii) w->color = x->parent->color; x->parent->color= BLACK; w->right->color = BLACK; leftRotate(root, x->parent); x = root; } }