Giáo trình Cấu trúc dữ liệu và giải thuật - Chương 10: Cây nhiều nhánh

ngược lại chỉ là đối xứng. Chúng ta 
cần phân biệt hai trường hợp tương ứng với màu của nút con còn lại của nút ông, 
nghĩa là nút chú của nút đỏ mới xuất hiện. 
Trước tiên, giả sử nút chú có màu đen. Trường hợp này có gộp cả trường hợp 
nút chú rỗng, do quy ước cây con rỗng có màu đen. Các đặc tính của cây đỏ đen 
sẽ được khôi phục nhờ một phép quay đơn hay một phép quay kép qua phải, như 
hai phần đầu của hình 10.17. Trong cả hai sơ đồ này, phép quay, kéo theo sự thay 
đổi các màu nút tương ứng, sẽ loại được sự vi phạm điều kiện đỏ, đồng thời bảo 
toàn điều kiện đen do không làm thay đổi số nút đen trong bất kỳ đường đi nào 
từ gốc đến các nút lá. 
Giờ chúng ta giả sử nút chú có màu đỏ, như hai phần bên dưới của hình 10.17. 
Việc biến đổi rất đơn giản: không có phép quay nào xảy ra, chỉ có sự thay đổi các 
màu. Nút cha và nút chú trở thành màu đen, nút ông trở thành màu đỏ. Điều kiện 
đỏ vẫn bảo đảm khi xét mối quan hệ giữa nút ông và nút cha, nút chú; giữa nút 
Chương 10 – Cây nhiều nhánh 
Giáo trình Cấu trúc dữ liệu và Giải thuật 279
cha và nút con màu đỏ mới xuất hiện bên dưới. Điều kiện đen không bị vi phạm 
do số nút đen trong các đường đi dọc theo cây không hề thay đổi. Tuy nhiên, khi 
nút ông vừa được biến đổi thành màu đỏ, điều kiện đỏ có thể bị vi phạm khi xét 
mối quan hệ với nút cha của nút này. Quá trình xử lý chưa thể chấm dứt. Mặc dù 
vậy, chúng ta có thể thấy rằng nút ông vừa được đổi sang màu đỏ hoàn toàn giống 
với trường hợp một nút đỏ mới xuất hiện lúc trước. Vậy chúng ta chỉ cần để lại 
cho các lần gọi đệ quy bên trên xử lý tại các nút bên trên nữa trong cây, bằng 
cách lại cho chỉ số trạng thái về lại trường hợp có một nút đỏ mới xuất hiện. Như 
vậy quá trình xử lý khi điều kiện đỏ bị vi phạm được lan truyền dọc lên phía trên 
của cây. Quá trình này có thể kết thúc tại một nút nào đó, hoặc có thể lan truyền 
lên tận gốc. Và khi nút gốc cần được đổi sang màu đỏ, thì chương trình ngoài 
cùng chỉ cần đổi nút này thành màu đen cho đúng quy ước. Điều này cũng không 
vi phạm điều kiện đen, do nó làm cho số nút đen trong tất cả các đường đi dọc 
theo cây tăng thêm một đơn vị. Và đây cũng chính là trường hợp duy nhất làm 
cho số nút đen trong các đường đi này tăng lên. 
10.4.5. Phương thức thêm vào. Hiện thực 
Chúng ta sẽ chuyển giải thuật trên thành chương trình C++. Cũng như mọi 
khi, phần lớn công việc đều được thực hiện bởi hàm đệ quy, phương thức insert 
chỉ cần đổi nút gốc thành màu đen khi cần và kiểm tra lỗi. Phần quan trọng nhất 
của giải thuật thêm phần tử vào cây đỏ đen là nắm giữ được chỉ số trạng thái mỗi 
khi có một lần đệ quy kết thúc. Chúng ta cần một kiểu liệt kê mới để phân biệt 
các trạng thái: 
enum RB_code {okay, red_node, left_red, right_red, duplicate}; 
/* Các giá trị trạng thái mà một lần đệ quy cần chuẩn bị trước khi kết thúc để trả về cho lần đệ 
quy bên trên như sau (giả sử gọi nút đang được xử lý trong lần đệ quy hiện tại là *current): 
okay: Màu của *current không có sự thay đổi nào. 
red_node: Màu của *current vừa chuyển từ đen sang đỏ. Lần đệ quy bên trên khi nhận được 
thông tin này cần xem xét để xử lý. 
right_red: Màu của *current và nút con phải của nó đều là đỏ, có sự vi phạm điều kiện đỏ. 
Lần đệ quy bên trên khi nhận được thông tin này cần thực hiện phép quay hoặc đổi 
màu cần thiết. 
left_red: Màu của *current và nút con trái của nó đều là đỏ, có sự vi phạm điều kiện đỏ. 
Lần đệ quy bên trên khi nhận được thông tin này cần thực hiện phép quay hoặc đổi 
màu cần thiết. 
duplicate: Phần tử cần thêm vào cây đã có trong cây. 
*/ 
template 
Error_code RB_tree::insert(const Record &new_entry) 
Chương 10 – Cây nhiều nhánh 
Giáo trình Cấu trúc dữ liệu và Giải thuật 280
/* 
post: Nếu khóa trong new_entry đã có trong RB_tree, phương thức trả về 
duplicate_error. Ngược lại, phương thức trả về success và new_entry được thêm 
vào cây sao cho cây vẫn thỏa cây RB-tree. 
uses: Các phương thức của struct RB_node và hàm đệ quy rb_insert. 
*/ 
{ 
 RB_code status = rb_insert(root, new_entry); 
 switch (status) { 
 case red_node: 
 root->set_color(black); 
 case okay: 
 return success; 
 case duplicate: 
 return duplicate_error; 
 case right_red: 
 case left_red: 
 cout << "WARNING: Program error detected in RB_tree::insert" << 
endl; 
 return internal_error; 
 } 
} 
Hàm đệ quy rb_insert thực hiện thực sự việc thêm phần tử mới vào cây: tìm 
kiếm trong cây theo cách thông thường, gặp cây con rỗng, thêm nút mới vào tại 
đây, các việc còn lại được thực hiện trên đường quay về của các lần gọi đệ quy. 
Hàm này có gọi modify_left hoặc modify_right để thực hiện các phép quay 
và đổi màu tương ứng với các trường hợp trong hình 10.17. 
template 
RB_code RB_tree::rb_insert(Binary_node *¤t, 
 const Record &new_entry) 
/* 
pre: current là NULL hoặc là địa chỉ của nút gốc của một cây con trong RB_tree. 
post: Nếu khóa trong new_entry đã có trong RB_tree, phương thức trả về 
duplicate_error. Ngược lại, phương thức trả về success và new_entry được thêm 
vào cây con có gốc là current. Tính chất cây đỏ đen trong cây con này vẫn thỏa ngoại 
trừ màu tại nút gốc của nó và một trong hai nút con của nút gốc này. Trạng thái này sẽ 
được hàm modify_right hoặc modify_left điều chỉnh thích hợp (tương ứng các trị của 
RB_code) để trả về cho lần đệ quy bên trên của lần gọi rb_insert này. 
uses: Các phương thức của lớp RB_node, các hàm rb_insert (một cách đệ quy), 
modify_left, và modify_right. 
*/ 
{ 
 RB_code status, 
 child_status; 
 if (current == NULL) { 
 current = new RB_node(new_entry); 
 status = red_node; 
 } 
 else if (new_entry == current->data) 
 return duplicate; 
 else if (new_entry data) { 
Chương 10 – Cây nhiều nhánh 
Giáo trình Cấu trúc dữ liệu và Giải thuật 281
 child_status = rb_insert(current->left, new_entry); 
 status = modify_left(current, child_status); 
 } 
 else { 
 child_status = rb_insert(current->right, new_entry); 
 status = modify_right(current, child_status); 
 } 
 return status; 
} 
Hàm modify_left dựa vào trạng thái của các nút con để thực hiện phép quay 
hay sửa đổi màu tương ứng, đồng thời cập nhật lại và trả về chỉ số trạng thái cho 
rb_insert. Chính trong hàm này chúng ta quyết định trì hoãn công việc khôi 
phục các đặc tính của cây đỏ đen. Khi modify_left được gọi, chúng ta biết rằng 
việc thêm vào vừa được thực hiện trong cây con bên trái của nút hiện tại, biết 
được màu của nút hiện tại, và thông qua chỉ số trạng thái, chúng ta còn biết được 
trường hợp nào đã xảy ra ở cây con trái của nó. Bằng cách sử dụng các thông tin 
này, chúng ta có thể xác định chính xác những việc cần làm để khôi phục các đặc 
tính của cây đỏ đen. 
template 
RB_code RB_tree::modify_left(Binary_node *¤t, 
 RB_code &child_status) 
/* 
pre: Cây con bên trái của current vừa được thêm nút mới, trị trong child_status sẽ quyết 
định việc xử lý kế tiếp trong hàm này. 
post: Việc đổi màu hoặc quay cần thiết đã được thực hiện, trạng thái thích hợp được trả về bởi 
hàm này. 
uses: Các phương thức của struct RB_node, các hàm rotate_right, 
double_rotate_right, và flip_color. 
*/ 
{ 
 RB_code status = okay; 
 Binary_node *aunt = current->right; 
 Color aunt_color = black; 
 if (aunt != NULL) aunt_color = aunt->get_color(); 
 switch (child_status) { 
 case okay: 
 break; // Việc xử lý đã kết thúc và không cần lan truyền lên trên nữa. 
 case red_node: 
 if (current->get_color() == red) 
 status = left_red; 
 else 
 status = okay;// current màu đen, nút con trái màu đỏ, đã thỏa cây 
RB-tree. 
 break; 
 case left_red: 
 if (aunt_color == black) status = rotate_right(current); 
 else status = flip_color(current); 
 break; 
 case right_red: 
 if (aunt_color == black) status = double_rotate_right(current); 
 else status = flip_color(current); 
Chương 10 – Cây nhiều nhánh 
Giáo trình Cấu trúc dữ liệu và Giải thuật 282
 break; 
 } 
 return status; 
} 
Hàm phụ trợ modify_right cũng tương tự, nó xử lý cho các tình huống cây có 
dạng như những hình ảnh phản chiếu qua gương của các tình huống trong hình 
10.17. Hàm đổi màu flip_color được xem như bài tập. Các hàm quay dựa trên 
cơ sở các hàm quay của cây AVL, có thêm việc gán lại các màu và chỉ số trạng 
thái thích hợp. 
10.4.6. Loại một nút 
Cũng như cây B-tree, việc loại bỏ một nút phức tạp hơn việc thêm vào, đối 
với cây đỏ đen, việc loại nút còn khó khăn hơn rất nhiều. Việc thêm vào tạo ra 
một nút mới màu đỏ dẫn đến nguy cơ vi phạm điều kiện đỏ, chúng ta cần xem xét 
một cách cẩn thận để giải quyết các vi phạm này. Việc loại một nút đỏ ra khỏi 
cây không khó lắm. Tuy nhiên, việc loại một nút đen khỏi cây dẫn đến nguy cơ vi 
phạm điều kiện đen, và nó đòi hỏi chúng ta phải xem xét rất nhiều trường hợp 
đặc biệt để khôi phục điều kiện đen cho cây.