Cây Đỏ Đen là Cây Tìm kiếm Nhị phân Tự cân bằng, trong đó mỗi nút của cây được tô màu Đỏ hoặc Đen. Có ba loại thao tác mà chúng ta có thể thực hiện trên Cây đỏ đen - Tìm kiếm, Chèn và Xóa.
Giả sử chúng ta phải chèn một phần tử vào Cây Đỏ Đen sau đây.
Để chèn một phần tử trong cây đỏ đen, ý tưởng rất đơn giản - chúng tôi thực hiện chèn giống như chúng tôi chèn trong cây nhị phân thông thường. Chúng tôi bắt đầu từ nút gốc bằng cách kiểm tra màu của nút và chèn nó vào một vị trí cụ thể. Tuy nhiên, trong cây đỏ-đen cần có một số thủ tục bổ sung để chèn một phần tử vào đó.
Tuy nhiên, chúng ta nên biết rằng một cây đỏ đen là cân bằng khi nó tuân theo các điều kiện -
-
Mọi Nút gốc phải có màu đen.
-
Mọi nút đều có màu Đỏ hoặc Đen.
-
Nếu một nút có màu đỏ, thì nút con của nó phải có màu đen.
-
Đường dẫn từ gốc đến cuối phải chứa một số lượng nút đen bằng nhau.
Nếu chúng ta muốn chèn một nút mới trong một cây đỏ đen, thì chúng ta có thể thực hiện bằng cách xem các bước chèn.
Các bước để Chèn một Phần tử vào Cây Đỏ đen -
-
Kiểm tra xem cây có trống hay không. Nếu cây trống, sau đó chèn một nút mới và tô màu nó là Đen. (Vì Root Node phải luôn có màu Đen) '
-
Ngược lại, nếu Cây không trống thì hãy chèn nút mới làm nút lá vào cuối và tô màu nó là Đỏ.
-
Nếu nút cha của nút mới là Đỏ và nút lân cận (của nút cha) cũng là Đỏ thì Lật màu của cả hàng xóm và Bố mẹ và Ông bà (Nếu không phải là Nút gốc Nếu không thì Lật chỉ màu của Nút gốc và hàng xóm) tức là , Màu đen.
-
Nếu nút cha của nút mới có màu Đỏ và nút lân cận (nút cha) của nó trống hoặc NULL, thì Xoay (xoay Trái-Trái hoặc Trái-Phải) nút và nút cha mới.
Có hai kiểu xoay sẽ được áp dụng - Xoay Trái Trái và Xoay Trái Phải. Xoay vòng sẽ chỉ áp dụng trong một số điều kiện. Các điều kiện là -
-
Nếu nút cha của nút mới có màu Đỏ và nút lân cận trống hoặc NULL, thì xoay trái hoặc xoay phải.
-
Trong Xoay Trái-Trái, lật màu của cha mẹ và ông bà. Làm cho cha mẹ trở thành cha mẹ và ông bà khi còn nhỏ.
Thuật toán
RBTreeInsertion (gốc, khóa)
//The color of the inserted new node is Red color[key] <- Red while(key≠root and color (p[key]=Red)) do if p[key]= left(p[p[key]]) Then y←right[p[p[key]] // If the parent of the new node is Red(if there is Grandparent instead root Node) Flip the color. if color[y]← Red then color(p[key])← Black color(p[p[key]])← Red key← p[p[key]] else if key← right[p[key]] then key← p[key] //When parent of new node has the red color and its sibling is NULL LeftRotate(root,key) color(p[key]) ← Black color(p[p[key]]) ← Red RotateRight(root,p[p[key]]) else exchange then left and right elements to make it balance. color(root)← Black