[FONT=Times New Roman]I- Giới thiệu:

[FONT=Times New Roman]

[FONT=Times New Roman]Cây đỏ đen được ra giới thiệu bởi Rudolf Bayer trong quyển “Symmetric Binary B-Trees: Data Structure and maintenance Algorithms”, nhà xuất bản Acta Informatica, Tâp1, trang 290-306. Sau đó Leonidas J.Guibas và Robert Sedgewick đã thêm các đặc tính của cây đỏ đen và đặt tên cho nó ( Tham khảo: Guibas, L. and Sedgewick R. “ A dichromatic Framwork for Balanced Trees”, in Proc. 19th IEEE Symp. Foundations of Computer Science, trang 8-21, năm 1978).

[FONT=Times New Roman]

[FONT=Times New Roman]Ta đã biết cây tìm kiếm nhị phân thông thường có những thuận lợi lớn về mặt lưu trữ và truy xuất dữ liệu trong phép toán tìm kiếm thêm vào hay loại bỏ một phần tử. Do đó, cây tìm kiếm nhị phân xem ra là một cấu trúc lưu trữ dữ liệu tốt.

[FONT=Times New Roman]

[FONT=Times New Roman]Tuy nhiên trong một số trường hợp cây tìm kiếm nhị phân có một số hạn chế. Nó hoạt động tốt nếu dữ liệu được chèn vào cây theo thứ tự ngẫu nhiên. Tuy nhiên, nếu dữ liệu được chèn vào theo thứ tự đã đuợc sắp xếp sẽ không hiệu quả. Khi các trị số cần chèn đã đuợc sắp xếp thì cây nhị phân trở nên không cân bằng. Khi cây không cân bằng, nó mất đi khả năng tìm kiếm nhanh (hoặc chèn hoặc xóa) một phần tử đã cho.

[FONT=Times New Roman]Chúng ta khảo sát một cách giải quyết vấn đề của cây không cân bằng: đó là cây đỏ đen, là cây tìm kiếm nhị phân có thêm một vài đặc điểm .

[FONT=Times New Roman]Có nhiều cách tiếp cận khác để bảo đảm cho cây cân bằng: chẳng hạn cây 2-3-4. Tuy vậy, trong phần lớn trường hợp, cây đỏ đen là cây cân bằng hiệu quả nhất, ít ra thì khi dữ liệu được lưu trữ trong bộ nhớ chứ không phải trong những tập tin.

[FONT=Times New Roman]Trước khi khảo sát cây đỏ đen, hãy xem lại cây không cân bằng được tạo ra như thế nào.

[FONT=Times New Roman]file:///C:/Users/PC/AppData/Local/Temp/msohtml1/01/clip_image002.jpg

[FONT=Times New Roman]Hình 3.1. Các node được chèn theo thứ tự tăng dần

[FONT=Times New Roman]Những node này tự sắp xếp thành một đường không phân nhánh. Bởi vì mỗi node lớn hơn node đã được chèn vào trước đó, mỗi node là con phải. Khi ấy, cây bị mất cân bằng hoàn toàn. Nếu ta chèn những mục (item) theo thứ tự giảm dần, mỗi node sẽ là con trái của node cha của chúng - cây sẽ bị mất cân bằng về phía bên kia.

[FONT=Times New Roman]* Độ phức tạp:

[FONT=Times New Roman]Khi cây một nhánh, sẽ trở thành một danh sách liên kết, dữ liệu sẽ là một chiều thay vì hai chiều. Trong trường hợp này, thời gian truy xuất giảm về O(N), thay vì O(logN) đối với cây cân bằng.

[FONT=Times New Roman]Để bảo đảm thời gian truy xuất nhanh O(logN) của cây, chúng ta cần phải bảo đảm cây luôn luôn cân bằng (ít ra cũng là cây gần cân bằng). Điều này có nghĩa là mỗi node trên cây phải có xấp xỉ số node con bên phải bằng số node con bên trái.

[FONT=Times New Roman]Một cách tiếp cận giải quyết vấn đề cân bằng lại cây: đó là cây đỏ đen-là cây tìm kiếm nhị phân vì thế nó có các tính chất của cây tìm kiếm nhị phân ví dụ : node con trái nhỏ hơn node cha, node cha nhỏ hơn node con phải, bên cạnh đó cây đỏ đen còn được bổ sung một số đắc điểm.

[FONT=Times New Roman]Trong cây đỏ đen, việc cân bằng được thực thi trong khi chèn, xóa. Khi thêm một phần tử thì thủ tục chèn sẽ kiểm tra xem tính chất cân bằng của cây có bị vi phạm hay không. Nếu có, sẽ xây dựng lại cấu trúc cây. Bằng cách này, cây luôn luôn được giữ cân bằng.

[FONT=Times New Roman]Mục lục:

[FONT=Times New Roman][URL="/#_Toc106188652"]Lời nói đầu:. 2

[FONT=Times New Roman][URL="/#_Toc106188653"]Mục lục:. 3

[FONT=Times New Roman][URL="/#_Toc106188654"]I- Giới thiệu:. 3

[FONT=Times New Roman][URL="/#_Toc106188655"]II- Định nghĩa:. 5

[FONT=Times New Roman][URL="/#_Toc106188656"]III- Các thuật toán cơ bản của Black and Red Tree. 6

[FONT=Times New Roman][URL="/#_Toc106188657"]1- Thêm một Node mới 6

[FONT=Times New Roman][URL="/#_Toc106188658"]2- Xóa một node:. 14

[FONT=Times New Roman][URL="/#_Toc106188659"]IV- Thuật toán cài đặt:. 14

[FONT=Times New Roman][URL="/#_Toc106188660"]V- Nhận xét :. 31

[FONT=Times New Roman]