Cây đỏ đen (red black tree) là cây nhị phân tìm kiếm được ràng buộc thêm bởi 1 số điều kiện (constraint) để đảm bảo cây luôn ở trạng thái tương đối cân bằng (độ dài giữa các nhánh cây không chênh lệch nhau quá lớn), nhằm tối đa hóa hiệu quả các thao tác tìm kiếm và lưu trữ trên cây.
B-Tree là cây tìm kiếm tự cân bằng và là dạng tổng quát của cây nhị phân tìm kiếm trong đó 1 node có thể có nhiều hơn 1 phần tử. Không như các cây tìm kiếm tự cân bằng khác như AVL tree hay Redblack tree được sử dụng chủ yếu trong bộ nhớ RAM, BTree được sinh ra do nhu cầu lưu trữ và tìm kiếm dữ liệu trên bộ nhớ cứng (hard disk).
Thuật toán Knuth Morris Pratt (KMP) là thuật toán hiệu quả tìm chuỗi con (chuỗi mẫu - pattern) bên trong chuỗi cha.
Cho 1 chuỗi mẫu pattern P độ dài m và đoạn text T độ dài n, tìm tất cả các lần mà chuỗi P xuất hiện bên trong đoạn text T. Ta có thể coi n > m.
Dùng 2 vòng lặp
Cấu trúc dữ liệu cây (tree) bao gồm 1 nút gốc (root) và các nút con (children), các nút con lại bao gồm nút con khác của nó, tạo thành cấu trúc dữ liệu dạng phân cấp (hierachy) bắt đầu từ gốc và phình ra ở dưới (bottom).