Giới thiệu:

Cây tìm kiếm nhị phân (Binary Search Tree - BST) là một cấu trúc dữ liệu cơ bản nhưng cực kỳ quan trọng.

  • Các thao tác với BST (vd: search, max, min, insert, delete,..) có độ phức tạp thời gian là O(h) với h là độ cao của cây, trong trường hợp tổ chức tree tệ nhất (h = n), thao tác trên tree lúc này không khác gì trên linked-list.
  • Cây tìm kiếm nhị phân tự cân bằng (Self-balancing Binary Search Tree) ra đời để giải quyết vấn đề này. Red-Black tree là một cây tìm kiếm nhị phân tự cân bằng khác rất phổ biến hiện nay, mỗi node trong cây này có thêm 1 bit để lưu trữ màu sắc (red hoặc black). Các bit màu sắc này dùng để đảm bảo cây duy trì độ cân bằng tương đổi trong quá trình insert hoặc delete.

Tính chất:

Một Red-Black Tree phải thỏa các điều kiện sau:

  • Tất cả các node có một màu sắc: red hoặc black.
  • Root luôn luôn là black.
  • Nếu một node là red, con trực tiếp của node đó là black.
  • Tất cả các đường đi (path) từ một node đến lá (leaf) có cùng số lượng black node.

Người ta chứng minh được rằng một cây thỏa 4 điều kiện này sẽ có độ cân bằng tương đối, độ cao của cây n node luôn luôn nhỏ hơn 2log(n+1).

So sánh với AVL Tree:

  • Một cây tìm kiếm nhị phân tự cân bằng nổi tiếng khác là AVL Tree, AVL Tree quy định sự chênh lệch chiều cao của các subtree không lớn hơn 1 tại tất cả các node. Điều này giúp cho độ cao cây (h) luôn là tối ưu.
  • AVL Tree cân bằng hơn khi so sánh với Red-Black Tree, nhưng để duy trì độ cân bằng này, AVL Tree cần nhiều thời gian hơn khi insert hoặc delete node. Nếu ứng dụng của bạn thường xuyên insert/delete node, Red-Black Tree sẽ là sự lựa chọn hợp lý. Còn nếu thao tác search diễn ra thường xuyên hơn, AVL Tree sẽ tốt hơn.

Ứng dụng:

  • Trong Java, các cấu trúc TreeMap, TreeSet được xây dựng dựa trên Red-Black tree. Từ Java 8, HashMap bucket cũng được chuyển đổi từ linked-list sang Red-Black tree để cải thiện performance trong trường hợp đụng độ hash
  • C++ STL: map, multimap, multiset dùng Red-Black Tree
  • Red-Black tree được sử dụng rất nhiều trong Linux Kernel (Completely Fair Scheduler, CD/DVD driver, timer, ext3 filesystem, VMAs,...).
    Schedular là thành phần rất quan trọng trong Linux, nó đảm nhiệm vai trò phân bổ I/O resource đến các tiến trình.
    Từ phiên bản Linux 2.6.23, Completely Fair Scheduler (CFS) đã trở thành schedular mặc định.
    Ý tưởng bên dưới của CFS này là duy trì phân bổ cân bằng I/O cho các tiến trình, mỗi tiến trình sẽ có thông tin thời gian đã xử lý (execution time), thời gian xử lý tối đa (maximum execution time). Tiến trình với execution time nhỏ nhất sẽ được thực thi. Và để track các tiến trình này, các kỹ sư của Linux đã sử dụng cấu trúc Red-Black tree và có một chút optimized để đạt tốc độ cao hơn.

Reference:

http://r.grokking.org/forum-auckland-ac-nz-red-black-tree

http://r.grokking.org/forum-geeksforgeeks-red-black-tree-introduction
http://r.grokking.org/forum-ibm-linux-completely-fair-scheduler