markdown:
# Cây đỏ đen
|Bài viết này cần thêm
|**Cây đỏ đen** ( [tiếng Anh](/wiki/Ti%E1%BA%BFng_Anh): *red-black tree*) là một dạng [cây tìm kiếm nhị phân](/wiki/C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n) tự cân bằng, một [cấu trúc dữ liệu](/wiki/C%E1%BA%A5u_tr%C3%BAc_d%E1%BB%AF_li%E1%BB%87u) được sử dụng trong [khoa học máy tính](/wiki/Khoa_h%E1%BB%8Dc_m%C3%A1y_t%C3%ADnh). Cấu trúc ban đầu của nó được đưa ra vào năm [1972](/wiki/1972) bởi [Rudolf Bayer](/w/index.php?title=Rudolf_Bayer&action=edit&redlink=1). Ông gọi chúng là các " [B-cây](/wiki/B-c%C3%A2y) cân bằng" còn tên hiện nay được đưa ra từ [1978](/wiki/1978) bởi Leo J. Guibas và [Robert Sedgewick](/w/index.php?title=Robert_Sedgewick&action=edit&redlink=1). Nó là cấu trúc phức tạp nhưng cho kết quả tốt về thời gian trong trường hợp xấu nhất. Các phép toán trên chúng như tìm kiếm (search), chèn (insert), và xóa (delete) trong thời gian [O](/wiki/K%C3%AD_hi%E1%BB%87u_O_l%E1%BB%9Bn) (log *n*), trong đó *n* là số các phần tử của cây.
## Mục lục
## Thuật ngữ[
[sửa](/w/index.php?title=C%C3%A2y_%C4%91%E1%BB%8F_%C4%91en&veaction=edit&vesection=1) | [sửa mã nguồn](/w/index.php?title=C%C3%A2y_%C4%91%E1%BB%8F_%C4%91en&action=edit§ion=1)]
Một cây đỏ-đen là một
[cây nhị phân](/wiki/C%C3%A2y_(l%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%93_th%E1%BB%8B)), là một cấu trúc dữ liệu trong [khoa học máy tính](/wiki/Khoa_h%E1%BB%8Dc_m%C3%A1y_t%C3%ADnh) để tổ chức các thành phần dữ liệu có thể so sánh, chẳng hạn các số. Trong cây nhị phân các thành phần dữ liệu được đưa vào các nút (node). Trong các nút có một nút nằm ở vị trí khởi đầu không là con của nút nào được gọi là **gốc**. Các nút khác đều là con của một nút nào đó và có không quá hai con. Từ nút gốc có một đường đi duy nhất đến mỗi nút khác trên cây.
Các nút không có con được gọi là
[lá](/w/index.php?title=N%C3%BAt_l%C3%A1&action=edit&redlink=1) (leaf node). Trong cây đỏ đen, các lá được gán giả là *null*; nghĩa là chúng không chứa bất kỳ dữ liệu nào.
Các
[cây tìm kiếm nhị phân](/wiki/C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n), bao gồm cả cây đỏ-đen, thỏa mãn tính chất: mỗi nút được gán một giá trị sao cho giá trị trên mỗi nút nhỏ hơn hoặc bằng tất cả các giá trị trên các nút thuộc cây con phải và lớn hơn các giá trị nằm trên cây con trái. Điều đó làm cho quá trình tìm kiếm nhanh hơn.
## Thuận lợi khi sử dụng[
[sửa](/w/index.php?title=C%C3%A2y_%C4%91%E1%BB%8F_%C4%91en&veaction=edit&vesection=2) | [sửa mã nguồn](/w/index.php?title=C%C3%A2y_%C4%91%E1%BB%8F_%C4%91en&action=edit§ion=2)]
Các cây đỏ đen cùng với các
[cây AVL](/wiki/C%C3%A2y_AVL), thường đảm bảo một thời gian tốt nhất trong trường hợp xấu nhất cho các phép toán chèn (insertion), xóa (deletion),và tìm kiếm (search)..
Các cây đỏ-đen là một đồng cấu của các
[cây 2-3-4](/wiki/C%C3%A2y_2-3-4). Ngược lại, cho một cây 2-3-4, có ít nhất một cây đỏ-đen với các thầnh phần dữ liệu theo đúng thứ tự ấy. Các phép chèn và xóa trên cây 2-3-4 cũng tương đương với đổi màu và quay trong cây đỏ đen. Điều này làm cho các cây 2-3-4 có một công cụ quan trọng tương đương lôgic với cây đỏ-đen. Do đó các giải thuật trên các cây 2-3-4 tuy có trươc cây đỏ-đen nhưng thường ít được dùng hơn cây đỏ đen.
## Các tính chất[
[sửa](/w/index.php?title=C%C3%A2y_%C4%91%E1%BB%8F_%C4%91en&veaction=edit&vesection=3) | [sửa mã nguồn](/w/index.php?title=C%C3%A2y_%C4%91%E1%BB%8F_%C4%91en&action=edit§ion=3)]
Mỗi nút của cây đỏ-đen có thuộc tinh "màu" nhận một trong hai giá trị "đỏ" hoặc "đen". Ngoài ra:
- Một nút hoặc là đỏ hoặc đen.
- Gốc là đen.
- Tất cả các lá là đen.
- Cả hai con của mọi nút đỏ là đen. (và suy ra mọi nút đỏ có nút cha là đen.)
- Tất cả các đường đi từ một nút đã cho tới các lá chứa một số như nhau các nút đen.
Tính chất 5 còn được gọi là tính chất "cân bằng đen". Số các nút đen trên một đường đi từ gôc tới mỗi lá được gọi là độ dài đen của đường đi đó. Trong bài này chỉ xét các đường đi từ gốc tới các lá nên ta sẽ gọi tắt các đường đi như vậy là
**đường đi**. Sức mạnh của cây đỏ đen nằm trong các tính chất trên. Từ các tính chất này suy ra trong các đường đi từ gốc tới các lá đường đi dài nhất không vượt quá hai lần đường đi ngắn nhất. Do đó cây đỏ đen là gần cân bằng. Vì các thuật toán chèn, xóa, tìm kiếm trong trường hợp xấu nhất đều tỷ lệ với chiều cao của cây nên cây đỏ đen rất hiệu quả trong các trường hợp xấu nhất,không giống như [cây tìm kiếm nhị phân](/wiki/C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n) thông thường.
Để thấy rõ sức mạnh này, ta chú ý rằng không có đường đi nào từ gôc tới một lá chứa hai nút đỏ liền nhau (theo tính chất 4). Do đó trên mỗi đường số nút đỏ không nhiều hơn số nút đen. Đường đi ngắn nhất là đường đi chỉ có nút đen, đường đi dài nhất có thể là đường đi xen kẽ giữa các nút đỏ và đen. Theo tính chất 5, số các nút đen trên hai đường đi đó bằng nhau, và do đó đường đi dài nhất không vượt quá hai lần đường đi ngắn nhất.
Trong nhiều biểu diễn của dữ liệu cây, có thể có các nút chỉ có một con và có các lá có chứa dữ liệu. Tuy nhiên có thể biểu diễn cây đỏ đen ta có một chút thay đổi mà không làm thay đổi tính chất cơ bản của cây và độ phức tạp của các thuật toán. Với mục đích này, ta đưa thêm các
*lá null* vào làm con phải hoặc con trái hoặc cả hai của những nút không có chúng, các lá này không chứa dữ liệu mà chỉ làm nhiệm vụ thông báo rằng tại đây cây đã kết thúc, như hình vẽ ở trên. Việc thêm các nút này làm cho tất cả các nút trong của cây đều chứa dữ liệu và có hai con, hay khác đi cây đỏ đen cùng với các lá null là cây nhị phân đầy dủ. Khi đó số các "lá null" nhiều hơn số các nút chứa dữ liệu của cây một lá.
Một số người định nghĩa cây đỏ đen bằng cách gán màu đỏ đen cho các cạnh chứ không phải các nút. Tuy nhiên điều đó không tạo nên sự khác biệt. Khi ấy màu của mỗi nút tương ứng với màu của cạnh nối nó với nút cha.
## Các phép toán trên cây đỏ đen[
[sửa](/w/index.php?title=C%C3%A2y_%C4%91%E1%BB%8F_%C4%91en&veaction=edit&vesection=4) | [sửa mã nguồn](/w/index.php?title=C%C3%A2y_%C4%91%E1%BB%8F_%C4%91en&action=edit§ion=4)]
Có thể áp dụng ngay các phép chèn, xóa trong
[cây tìm kiếm nhị phân](/wiki/C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n) vào cây đỏ đen mà không cần sửa chữa gì vì cây đỏ đen là trường hợp riêng của cây tìm kiếm nhị phân. Tuy nhiên, khi đó có thể có một số tính chất trong định nghĩa của cây đỏ đen sẽ bị vi phạm. Việc khôi phục các tính chất đỏ đen sẽ cần một số nhỏ cỡ O(log *n*) hoặc trung bình chỉ O(1) các phép đổi màu (tốn rất ít thời gian) và không quá ba [phép quay](/wiki/Ph%C3%A9p_quay_c%C3%A2y_nh%E1%BB%8B_ph%C3%A2n) cho phép xóa, hai cho phép chèn. Toàn bộ các giải thuật chèn và xóa có độ phức tạp thời gian cỡ O(log *n*).
### Phép chèn[
[sửa](/w/index.php?title=C%C3%A2y_%C4%91%E1%BB%8F_%C4%91en&veaction=edit&vesection=5) | [sửa mã nguồn](/w/index.php?title=C%C3%A2y_%C4%91%E1%BB%8F_%C4%91en&action=edit§ion=5)]
Phép chèn bắt đầu bằng việc bổ sung một nút
[như trong cây tìm kiếm nhị phân bình thường](/wiki/C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n#ph.C3.A9p_ch.C3.A8n) và gán cho nó màu đỏ. Ta xem xét để bảo toàn tính chất đỏ đen từ các nút lân cận với nút mới bổ sung. Thuật ngữ *nút chú bác* sẽ dùng để chỉ nút anh (hoặc em) với nút cha của nút đó như trong cây phả hệ. Chú ý rằng:
- Tính chất 3 (Tất cả các lá -là các nút
*null*là đen) giữ nguyên.
- Tính chất 4 (Cả hai con của nút đỏ là đen) nếu bị thay đổi chỉ bởi việc thêm một nút đỏ có thể sửa bằng cách gán màu đen cho một nút đỏ hoặc một phép quay.
- Tính chất 5 (Tất cả các đường đi từ gôc tới các lá có cùng một số nút đen) nếu bị thay đổi chỉ bởi việc thêm một nút đỏ có thể sửa bằng cách gán màu đen cho một nút đỏ hoặc một phép quay.
*Chú ý*: Nhãn **N**sẽ dùng để chỉ nút đang chèn vào, **P**chỉ nút cha của **N'**, **G**chỉ ông của **N'**, và **U**chỉ chú bác của **N'**. Nhớ rằng,giữa các trường hợp, vai trò và nhãn của các nút có thể thay đổi còn trong cùng một trường hợp thì không.
Mỗi trường hợp được giới thiệu bằng một đoạn mã
**C**. Nút chú bác và nút ông dễ dàng xác định nhờ các hàm sau:
struct node *grandparent(struct node *n) { return n->parent->parent; }
struct node *uncle(struct node *n) { if (n->parent == grandparent(n)->left) return grandparent(n)->right; else return grandparent(n)->left; }
**Trường hợp 1:** Nút mới thêm **N** ở tại gốc. Trong trường hợp này, gán lại màu đen cho **N**, để bảo toàn tính chất 2 (Gốc là đen). Vì mới chỉ bổ sung một nút, Tính chất 5 được bảo đảm vì mọi đường đi chỉ có một nút.
void insert_case1(struct node *n) { if (n->parent == NULL) n->color = BLACK; else insert_case2(n); }
**Trường hợp 2:** Nút cha **P** của nút mới thêm là đen, khi đó Tính chất 4 (Cả hai nút con của nút đỏ là đen) không bị vi phạm vì nút mới thêm có hai con là "null' là đen. Tính chất 5 cũng không vi phạm vì nút mới thêm là đỏ không ẩnh hưởng tới số nút đen trên tất cả đường đi.
void insert_case2(struct node *n) { if (n->parent->color == BLACK) return; /* Tree is still valid */ else insert_case3(n); }
*Chú ý:*Trong trường hợp tiếp theo nếu **N**có ông là nút **G**, vì nếu cha **P**là đỏ và **P**không ở gốc thì **G**là đen. Như vậy, **N**cũng có chú bác là **U**, although it may be a leaf in cases 4 and 5.
|
|
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); }
*Chú ý:*Trong các trường hợp tiếp theo, giả sử rằng nút cha **P**là con trái của cha của nó. Nếu nó là con phải, *left*và *right*đổi chỗ cho nhau trong cases 4 and 5.
|
|
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) { rotate_right(n->parent); n = n->right; } insert_case5(n); }
|
|P là đỏ nhưng nút bác U là đen, nút mới N là con trái của nút P, và P là con trái của nút ông G. Trong trường hợp này, một phép quay phải trên nút ông G được thực hiện; kết quả của phep quay là trong cây mới nút P trở thành cha của cả hai nít N và nút G. Đã biết G là đen, vì bây giờ nó là con của P. Đổi màu của P và G thì cây thỏa mãn tính chất 4. Tính chất 5 không bị vi phạm vì các đường đi qua G trươc đây bây giờ đi qua P.
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 { /* Here, n == n->parent->right && n->parent == grandparent(n)->right */ rotate_left(grandparent(n)); } }
### Phép xóa[
[sửa](/w/index.php?title=C%C3%A2y_%C4%91%E1%BB%8F_%C4%91en&veaction=edit&vesection=6) | [sửa mã nguồn](/w/index.php?title=C%C3%A2y_%C4%91%E1%BB%8F_%C4%91en&action=edit§ion=6)]
Trong cây tìm kiếm nhị phân bình thường khi xóa một nút có cả hai con (không là
*lá null*), ta tìm phần tử lớn nhất trong cây con trái hoặc phần tử nhỏ nhất trong cây con phải, chuyển giá trị của nó vào nút đang muốn xóa (xem [Cây tìm kiếm nhị phân](/wiki/C%C3%A2y_t%C3%ACm_ki%E1%BA%BFm_nh%E1%BB%8B_ph%C3%A2n#ph.C3.A9p_x.C3.B3a)). Khi đó chúng ta xóa đi nút đã được copy giá trị, nút này có ít hơn hai con (không là *lá null*). Vì việc copy giá trị không làm mất tính chất đỏ đen nên không cần phải sửa chữa gì cho thao tác này. Việc này chỉ đặt ra khi xóa các nút có nhiều nhất một con (không là *lá null*).
Chúng ta sẽ thảo luận về việc xóa một nút có nhiều nhất một con (không là lá null).
Nếu ta xóa một nút đỏ, ta có thể chắc chắn rằng con của nó là nút đen. Tất cả các đường đi đi qua nút bị xóa chỉ đơn giản bớt đi một nút đỏ do đó tính chất 5 không thay đổi. Ngoài ra, cả nút cha và nút con của nút bị xóa đều là nút đen, do đó tính chất 3 và 4 vẫn giữa nguyên.. Một trường hợp đơn giản khác là khi xóa một nút đen chỉ có một con là nút đỏ. Khi xóa nút đó các tính chất 4 và 5 bị phá vỡ, nhưng nếu gán lại màu cho nút con là đen thì chúng lại được khôi phục.
Trường hợp phức tạp xảy ra khi cả nút bị xóa và nút con của nó đều là đen. Chúng ta sẽ bắt đầu bằng việc thay nút bị xóa bằng nút con của nó. Chúng ta sẽ gọi nút con này (trong vị trí mới của nó là
**N**, và anh em với nó (con khác của nút cha mới) là **S**. Tiếp theo ta vẫn dùng **P** chỉ cha mới của **N**, **S L** chỉ con trái của **S**, và **S**chỉ con phải của R **S**(chúng tồn tại vì **S**không thể là lá). *Chú ý*: Giữa các trường hợp khác nhau, vai trò và nhãn của các nút có thể thay đổi, nhưng trong một trường hợp mọi nhãn giữ vai trò không thay đổi. Trong hình vẽ các màu đỏ đen được thể hiện khi màu của nút đã rõ ràng, màu trắng biểu thị một màu chưa rõ (hoặc đỏ hoặc đen).
Chúng ta sẽ sử dụng hàm sau tìm người anh em của
*N'*:
struct node *sibling(struct node *n) { if (n = = n->parent->left) return n->parent->right; else return n->parent->left; }
*Chú ý*: Tất nhiên, chúng ta cần hoàn chỉnh các lá null sau mọi phép thay đổi. Nếu nút bị xóa không có con **N**khác "lá null", dễ dàng thấy rằng các tính chất được thỏa mãn. Còn nếu **N**là một "lá nulll", có thể sửa chữa lược đồ (hoặc code) để trong tất cảc các trường hợp các tính chất được thỏa mãn.
Trươc mỗi bước ta có thể dùng hàm (function)
replace_node thay thế nút con
child vào vị trí của nút bị xóa trên cây. Để thuận tiện các đoạn code trong mục này quy ước rằng các "lá null" được biểu diễn bằng các đối tượng nút thực sự khác biệt một chút với NULL (code trong
*phép chèn* có biểu diễn không nư vậy).
void delete_one_child(struct node *n) { /* Giả thiết: n có ít nhất một nút con
null*/ struct node *child = is_leaf(n->right) ? n->left: n->right; replace_node(n, child); if (n->color == BLACK) { if (child->color == RED) child->color = BLACK; else delete_case1(child); } free(n); } *Ghi chú*: Nếu **N**là "lá nul" và ta khong muốn biểu diễn các "lá null" bằng các đối tượng nút thực, ta có thể sửa giải thuật bằng cách trước hết gọi delete_case1() trên cha của nó (nghĩa là nút bị xóa
ntrong đoạn code trên) rồi sau đó mới xóa nó. Ta có thể làm như vậy vì cha của nó là đen, do đó có diễn biến như với "lá null" (một số người gọi là "lá ảo", "lá ma"). Ta cũng có thể xóa nó khỏi cuối của
nvà sẽ khôi phục lại sau tất cả các phép toán.
Nếu cả
**N** và gốc ban đầu của nó là đen thì sau khi xóa các đường qua "N" giảm bớt một nút đen. Do đó vi phạm Tính chất 5, cây cần phải cân bằng lại. Có các trường hợp sau:
#### Trường hợp 1[
[sửa](/w/index.php?title=C%C3%A2y_%C4%91%E1%BB%8F_%C4%91en&veaction=edit&vesection=7) | [sửa mã nguồn](/w/index.php?title=C%C3%A2y_%C4%91%E1%BB%8F_%C4%91en&action=edit§ion=7)] **Trường hợp 1:** **N** là gốc mới. Trong trường hợp này chúng ta dừng lại. Ta đã giải phóng một nút đen khỏi mọi đường đi và gôc mới lại là đen. Không tính chất nào bị vi phạm.
void delete_case1(struct node *n) { if (n->parent == NULL) return; else delete_case2(n); }
*Chú ý*: Trong các trường hợp 2, 5, và 6, ta quy ước **N**là con trái của cha **P**. Nếu no là con phải, *left*và *right*sẽ tráo đổi cho nhau. Tuy nhiên code ví dụ làm cho cả hai trường hợp.
#### Trường hợp 2[
[sửa](/w/index.php?title=C%C3%A2y_%C4%91%E1%BB%8F_%C4%91en&veaction=edit&vesection=8) | [sửa mã nguồn](/w/index.php?title=C%C3%A2y_%C4%91%E1%BB%8F_%C4%91en&action=edit§ion=8)]
|
|
void delete_case2(struct node *n) { if (sibling(n)->color == RED) { n->parent->color = RED; sibling(n)->color = BLACK; if (n == n->parent->left) rotate_left(n->parent); else rotate_right(n->parent); } delete_case3(n); }
#### Trường hợp 3[
[sửa](/w/index.php?title=C%C3%A2y_%C4%91%E1%BB%8F_%C4%91en&veaction=edit&vesection=9) | [sửa mã nguồn](/w/index.php?title=C%C3%A2y_%C4%91%E1%BB%8F_%C4%91en&action=edit§ion=9)]
|
|
void delete_case3(struct node *n) { if (n->parent->color == BLACK && sibling(n)->color == BLACK && sibling(n)->left->color == BLACK && sibling(n)->right->color == BLACK) { sibling(n)->color = RED; delete_case1(n->parent); } else delete_case4(n); }
#### Trường hợp 4[
[sửa](/w/index.php?title=C%C3%A2y_%C4%91%E1%BB%8F_%C4%91en&veaction=edit&vesection=10) | [sửa mã nguồn](/w/index.php?title=C%C3%A2y_%C4%91%E1%BB%8F_%C4%91en&action=edit§ion=10)] **Trường hợp 4:** **S** và các con của **S** là đen nhưng **P** là đỏ. Trong trường hợp này, chúng ta đổi ngược màu của **S** và **P**. Điều này không ảnh hưởng tới số nút đen trên các đường đi không qua **N**, nhưng thêm một nút đen trên các đường đi qua **N**, thay cho nút đen đã bị xóa trên các đường này.
void delete_case4(struct node *n) { if (n->parent->color == RED && sibling(n)->color == BLACK && sibling(n)->left->color == BLACK && sibling(n)->right->color == BLACK) { sibling(n)->color = RED; n->parent->color = BLACK; } else delete_case5(n); }
#### Trường hợp 5[
[sửa](/w/index.php?title=C%C3%A2y_%C4%91%E1%BB%8F_%C4%91en&veaction=edit&vesection=11) | [sửa mã nguồn](/w/index.php?title=C%C3%A2y_%C4%91%E1%BB%8F_%C4%91en&action=edit§ion=11)] **Trường hợp 5:** **S** là đen, con trái của **S** là đỏ, con phải của **S** là đen, còn **N** là con trái của cha nó. Trong trường hợp này chúng ta quay phải tại **S**, khi đó con trái của **S** trở thành cha của **S** và **N** là anh em mới của nó. Sau đó ta tráo đổi màu của **S** và cha mới của nó. Tất cả các đường đi sẽ có số nút đen như nhau, nhưng bây giờ **N** có một người anh em đen mà con phải của nó lại là đỏ, chúng ta chuyển sang Trường hợp 6. Hoặc **N** hoặc cha của nó bị tác động bởi việc dịch chuyên này.
(Lưu ý trong trường hợp 6, ta đặt lại nút anh em mới của
**N** là **S**.)
void delete_case5(struct node *n) { if (n == n->parent->left && sibling(n)->color == BLACK && sibling(n)->left->color == RED && sibling(n)->right->color == BLACK) { sibling(n)->color = RED; sibling(n)->left->color = BLACK; rotate_right(sibling(n)); } else if (n == n->parent->right && sibling(n)->color == BLACK && sibling(n)->right->color == RED && sibling(n)->left->color == BLACK) { sibling(n)->color = RED; sibling(n)->right->color = BLACK; rotate_left(sibling(n)); } delete_case6(n); }
#### Trường hợp 6[
[sửa](/w/index.php?title=C%C3%A2y_%C4%91%E1%BB%8F_%C4%91en&veaction=edit&vesection=12) | [sửa mã nguồn](/w/index.php?title=C%C3%A2y_%C4%91%E1%BB%8F_%C4%91en&action=edit§ion=12)]
|
|
Trong lúc đó, với một đường đi không đi qua
Như vậy, số các nút đen trên các đường đi là không thay đổi. Do đó các tính chất 4 và 5 đã được khôi phục. Nút trắng trong hình vẽ có thể là đỏ hoặc đen, nhưng phải ghi lại trước và sau khi thay đổi.
void delete_case6(struct node *n) { sibling(n)->color = n->parent->color; n->parent->color = BLACK; if (n == n->parent->left) { /* Here, sibling(n)->right->color == RED */ sibling(n)->right->color = BLACK; rotate_left(n->parent); } else { /* Here, sibling(n)->left->color == RED */ sibling(n)->left->color = BLACK; rotate_right(n->parent); } }
Nhắc lại rằng các hàm này có lời gọi đệ quy. Thêm nữa lời gọi không đệ quy sẽ được goi sau một phép quay, do đó số lần thực hiện các phép quay là không đổi (không quá 3).
## Xem thêm[
[sửa](/w/index.php?title=C%C3%A2y_%C4%91%E1%BB%8F_%C4%91en&veaction=edit&vesection=13) | [sửa mã nguồn](/w/index.php?title=C%C3%A2y_%C4%91%E1%BB%8F_%C4%91en&action=edit§ion=13)]
|
|![]()
|Wikimedia Commons có thêm thư viện hình ảnh và phương tiện truyền tải về
|

Content-language: vi

X-UA-Compatible: IE=Edge

Vary: Accept-Encoding,Cookie

Via: 1.1 varnish, 1.1 varnish

X-Cache: cp1068 miss (0), cp1055 frontend miss (0)

Cache-Control: private, s-maxage=0, max-age=0, must-revalidate


markdown:
# Nehmten
Bách khoa toàn thư mở Wikipedia
|
|Nehmten
|
|Huy hiệu |
|Vị trí
|
|Hành chính
|
|[Đức](/wiki/%C4%90%E1%BB%A9c) [Bang](/wiki/Bang_c%E1%BB%A7a_%C4%90%E1%BB%A9c) [Schleswig-Holstein](/wiki/Schleswig-Holstein) [Huyện](/wiki/Huy%E1%BB%87n_c%E1%BB%A7a_%C4%90%E1%BB%A9c) [Plön](/wiki/Pl%C3%B6n_(huy%E1%BB%87n)) [Amt](/w/index.php?title=Amt&action=edit&redlink=1) [Thị trưởng](/wiki/Burgomaster) **Số liệu thống kê cơ bản** [Diện tích](/wiki/Di%E1%BB%87n_t%C3%ADch) [Cao độ](/wiki/Cao_%C4%91%E1%BB%99) [Dân số](/wiki/D%C3%A2n_s%E1%BB%91) *(31/12/2006)* [Mật độ](/wiki/M%E1%BA%ADt_%C4%91%E1%BB%99_d%C3%A2n_s%E1%BB%91) **Các thông tin khác** [Múi giờ](/wiki/M%C3%BAi_gi%E1%BB%9D) [CET](/wiki/Gi%E1%BB%9D_Trung_%C3%82u)/ [CEST](/wiki/Gi%E1%BB%9D_m%C3%B9a_H%C3%A8_Trung_%C3%82u)( [UTC+1](/wiki/UTC%2B1)/ [+2](/wiki/UTC%2B2)) [Biển số xe](/wiki/Bi%E1%BB%83n_s%E1%BB%91_xe) [Mã bưu chính](/wiki/Danh_s%C3%A1ch_m%C3%A3_b%C6%B0u_ch%C3%ADnh_%E1%BB%9F_%C4%90%E1%BB%A9c) [Mã vùng](/w/index.php?title=M%C3%A3_v%C3%B9ng_%E1%BB%9F_%C4%90%E1%BB%A9c&action=edit&redlink=1) [Website](/wiki/Website) [www.amt-grosser-](http://www.amt-grosser-ploener-see.de/)
ploener-see.de
ploener-see.de
**Nehmten** là một [đô thị](/w/index.php?title=%C4%90%C3%B4_th%E1%BB%8B_c%E1%BB%A7a_%C4%90%E1%BB%A9c&action=edit&redlink=1) thuộc [huyện Plön](/wiki/Pl%C3%B6n_(huy%E1%BB%87n)), trong [bang](/wiki/Bang_c%E1%BB%A7a_%C4%90%E1%BB%A9c) [Schleswig-Holstein](/wiki/Schleswig-Holstein), nước [Đức](/wiki/%C4%90%E1%BB%A9c). Đô thị Nehmten có [diện tích](/wiki/Di%E1%BB%87n_t%C3%ADch) 22,04 [kilômét vuông](/wiki/Kil%C3%B4m%C3%A9t_vu%C3%B4ng), [dân số](/wiki/D%C3%A2n_s%E1%BB%91) thời điểm [31 tháng 12](/wiki/31_th%C3%A1ng_12) năm 2006 là 273 người.

WARC-Type: response

Content-Type: application/http; msgtype=response

Content-Type: text/html; charset=UTF-8

Connection: close

X-Content-Type-Options: nosniff

Content-Encoding: gzip

Accept-Ranges: bytes


markdown:
*Philautus ocularis*
Bách khoa toàn thư mở Wikipedia
|
|Pseudophilautus ocularis
|
|[Phân loại khoa học](/wiki/Ph%C3%A2n_lo%E1%BA%A1i_sinh_h%E1%BB%8Dc) [Giới](/wiki/Gi%E1%BB%9Bi_(sinh_h%E1%BB%8Dc))( *regnum*) [Animalia](/wiki/%C4%90%E1%BB%99ng_v%E1%BA%ADt) [Ngành](/wiki/Ng%C3%A0nh_(sinh_h%E1%BB%8Dc))( *phylum*) [Chordata](/wiki/%C4%90%E1%BB%99ng_v%E1%BA%ADt_c%C3%B3_d%C3%A2y_s%E1%BB%91ng) [Lớp](/wiki/L%E1%BB%9Bp_(sinh_h%E1%BB%8Dc))( *class*) [Amphibia](/wiki/%C4%90%E1%BB%99ng_v%E1%BA%ADt_l%C6%B0%E1%BB%A1ng_c%C6%B0) [Bộ](/wiki/B%E1%BB%99_(sinh_h%E1%BB%8Dc))( *ordo*) [Anura](/wiki/B%E1%BB%99_Kh%C3%B4ng_%C4%91u%C3%B4i) [Họ](/wiki/H%E1%BB%8D_(sinh_h%E1%BB%8Dc))( *familia*) [Rhacophoridae](/wiki/Rhacophoridae) [Phân họ](/wiki/Ph%C3%A2n_h%E1%BB%8D)( *subfamilia*) [Rhacophorinae](/w/index.php?title=Rhacophorinae&action=edit&redlink=1) [Chi](/wiki/Chi_(sinh_h%E1%BB%8Dc))( *genus*) [Philautus](/wiki/Philautus) [Loài](/wiki/Lo%C3%A0i)( *species*) **P. ocularis** [Danh pháp hai phần](/wiki/Danh_ph%C3%A1p_hai_ph%E1%BA%A7n) *Pseudophilautus ocularis*
(
[Manamendra-Arachchi](/w/index.php?title=Kelum_Manamendra-Arachchi&action=edit&redlink=1)& [Pethiyagoda](/w/index.php?title=Rohan_Pethiyagoda&action=edit&redlink=1), [2005](/wiki/2005)) ![ Pseudophilautus ocularis map-fr.svg](//upload.wikimedia.org/wikipedia/commons/thumb/8/82/Pseudophilautus_ocularis_map-fr.svg/280px-Pseudophilautus_ocularis_map-fr.svg.png)
![ Pseudophilautus ocularis map-fr.svg](http://upload.wikimedia.org/wikipedia/commons/thumb/8/82/Pseudophilautus_ocularis_map-fr.svg/280px-Pseudophilautus_ocularis_map-fr.svg.png)
[Danh pháp đồng nghĩa](/wiki/T%C3%AAn_%C4%91%E1%BB%93ng_ngh%C4%A9a_(sinh_v%E1%BA%ADt_h%E1%BB%8Dc)) *Philautus ocularis*Manamendra-Arachchi & Pethiyagoda, 2004 * là một loài Pseudophilautus ocularis* [ếch](/wiki/B%E1%BB%99_Kh%C3%B4ng_%C4%91u%C3%B4i)trong họ [Rhacophoridae](/wiki/Rhacophoridae). Chúng là loài [đặc hữu](/wiki/%C4%90%E1%BA%B7c_h%E1%BB%AFu)của [Sri Lanka](/wiki/Sri_Lanka).
Các môi trường sống tự nhiên của chúng là các khu
[rừng](/wiki/R%E1%BB%ABng) ẩm ướt đất thấp nhiệt đới hoặc cận nhiệt đới, [rừng mây](/wiki/R%E1%BB%ABng_m%C3%A2y) ẩm nhiệt đới và cận nhiệt đới, các [đồn điền](/wiki/%C4%90%E1%BB%93n_%C4%91i%E1%BB%81n), và các khu rừng trước đây bị suy thoái nặng nề. Loài này đang bị đe dọa do mất môi trường sống.
## Nguồn[
[sửa](/w/index.php?title=Philautus_ocularis&veaction=edit&vesection=1) | [sửa mã nguồn](/w/index.php?title=Philautus_ocularis&action=edit§ion=1)]
- Manamendra-Arachchi, K. & Pethiyagoda, R. 2004.
[Philautus ocularis](http://www.iucnredlist.org/search/details.php/58881/all). [2006 IUCN Red List of Threatened Species.](http://www.iucnredlist.org)Truy cập 23 tháng 7 2007.
## Tham khảo[
[sửa](/w/index.php?title=Philautus_ocularis&veaction=edit&vesection=2) | [sửa mã nguồn](/w/index.php?title=Philautus_ocularis&action=edit§ion=2)]
## Liên kết ngoài[
[sửa](/w/index.php?title=Philautus_ocularis&veaction=edit&vesection=3) | [sửa mã nguồn](/w/index.php?title=Philautus_ocularis&action=edit§ion=3)]
Phương tiện liên quan tới
[Pseudophilautus ocularis](//commons.wikimedia.org/wiki/Category:Pseudophilautus_ocularis) tại [Wikimedia Commons](/wiki/Wikimedia_Commons)

X-Cache: cp1066 miss (0), cp1055 frontend miss (0)


markdown:
*Phleum*
Bách khoa toàn thư mở Wikipedia
|
|Phleum
|
|[Giới](/wiki/Gi%E1%BB%9Bi_(sinh_h%E1%BB%8Dc))( *regnum*) [Plantae](/wiki/Th%E1%BB%B1c_v%E1%BA%ADt) [Angiospermae](/wiki/Th%E1%BB%B1c_v%E1%BA%ADt_c%C3%B3_hoa) [Monocots](/wiki/Th%E1%BB%B1c_v%E1%BA%ADt_m%E1%BB%99t_l%C3%A1_m%E1%BA%A7m) [Commelinids](/wiki/Nh%C3%A1nh_Th%C3%A0i_l%C3%A0i) [Bộ](/wiki/B%E1%BB%99_(sinh_h%E1%BB%8Dc))( *ordo*) [Poales](/wiki/B%E1%BB%99_H%C3%B2a_th%E1%BA%A3o) [Họ](/wiki/H%E1%BB%8D_(sinh_h%E1%BB%8Dc))( *familia*) [Poaceae](/wiki/H%E1%BB%8D_H%C3%B2a_th%E1%BA%A3o) [Chi](/wiki/Chi_(sinh_h%E1%BB%8Dc))( *genus*) **Phleum** * là một chi Phleum* [thực vật có hoa](/wiki/Th%E1%BB%B1c_v%E1%BA%ADt_c%C3%B3_hoa)trong [họ Hòa thảo](/wiki/H%E1%BB%8D_H%C3%B2a_th%E1%BA%A3o)(Poaceae). [[1]](#cite_note-1)
## Loài[
[sửa](/w/index.php?title=Phleum&veaction=edit&vesection=1) | [sửa mã nguồn](/w/index.php?title=Phleum&action=edit§ion=1)]
Chi
*Phleum* gồm các loài:
## Chú thích[
[sửa](/w/index.php?title=Phleum&veaction=edit&vesection=2) | [sửa mã nguồn](/w/index.php?title=Phleum&action=edit§ion=2)]
## Liên kết ngoài[
[sửa](/w/index.php?title=Phleum&veaction=edit&vesection=3) | [sửa mã nguồn](/w/index.php?title=Phleum&action=edit§ion=3)]
Phương tiện liên quan tới
[Phleum](//commons.wikimedia.org/wiki/Category:Phleum)tại [Wikimedia Commons](/wiki/Wikimedia_Commons)
Dữ liệu liên quan tới
[Phleum](//species.wikimedia.org/wiki/Phleum)tại [Wikispecies](/wiki/Wikispecies)