Cây 2-3 là cấu trúc dữ liệu cây, nơi mỗi nút nội bộ (internal node) có hoặc:
- 2 con (2-node) và 1 phần tử dữ liệu.
- 3 con (3-node) và 2 phần tử dữ liệu.
Định nghĩa
- 2-node: nút nội bộ có 1 phần tử dữ liệu, 2 con.
- 3-node: nút nội bộ có 2 phần tử dữ liệu, 3 con.
- T là cây 2-3 nếu thỏa mãn một trong:
- T rỗng.
- T là 2-node với phần tử a, con trái L, con phải R: L,R là cây 2-3 không rỗng cùng chiều cao; a lớn hơn mọi phần tử L; a ≤ mọi phần tử R.
- T là 3-node với phần tử a,b (a<b), con L,M,R: L,M,R là cây 2-3 không rỗng cùng chiều cao; a lớn hơn mọi phần tử L và ≤ mọi phần tử M; b lớn hơn mọi phần tử M và ≤ mọi phần tử R.
Đặc tính
- Mọi nút nội bộ là 2-node hoặc 3-node.
- Tất cả lá ở cùng cấp.
- Dữ liệu được giữ theo thứ tự sắp xếp.
Các phép toán
Tìm kiếm (Searching)
Tương tự tìm trong BST. Vì dữ liệu trong nút đã sắp xếp, hàm tìm kiếm sẽ đi đến đúng cây con và cuối cùng đúng nút chứa phần tử.
- Nếu T rỗng → không tìm thấy.
- Gốc r. Nếu r là lá: nếu d không trong r → không có trong T; ngược lại tìm thấy.
- Nếu r là 2-node (phần tử e, con L,R):
- d = e → tìm thấy.
- d < e → T = L, lặp lại.
- d > e → T = R, lặp lại.
- Nếu r là 3-node (phần tử a,b, a<b, con L,M,R):
- d = a hoặc b → tìm thấy.
- d < a → T = L.
- a < d < b → T = M.
- d > b → T = R.
Chèn (Insertion)
Tìm vị trí thích hợp thêm khóa. Nếu nút thành 4-node → tách thành hai 2-node, khóa giữa đẩy lên cha. Cha có thể thành 4-node → tách tiếp, lan truyền lên gốc. Nếu đến gốc → tạo gốc mới 2-node. Số phép toán tỷ lệ với chiều cao cây → O(log n) vì cây cân bằng hoàn hảo. Kết quả vẫn là cây 2-3 (tất cả lá cùng độ sâu).
Sơ đồ dưới minh họa 3 trường hợp chèn.
