Cây 2-3 là cây tìm kiếm cân bằng, mỗi nút là nút-2 (1 khóa, 2 con) hoặc nút-3 (2 khóa, 3 con). Là trường hợp đặc biệt của B-tree bậc 3.
Đặc điểm
- Nút nội部 là nút-2 hoặc nút-3.
- Nút-2: 1 khóa, 2 con (trái < khóa < phải) hoặc lá.
- Nút-3: 2 khóa (khóa1 < khóa2), 3 con (trái < khóa1 < giữa < khóa2 < phải). Không bao giờ là lá.
- Tất cả lá cùng cấp độ.
- Cây luôn cân bằng chiều cao.
- Tìm kiếm nhanh, hiệu quả.
Nút-2 (2-Node)
- 2 con: trái (giá trị nhỏ hơn), phải (giá trị lớn hơn).
- Có thể là lá (không con).
Nút-3 (3-Node)
- 3 con, 2 khóa.
- Con trái < khóa1 < con giữa < khóa2 < con phải.
- Không bao giờ là lá.
Các thao tác
1. Tìm kiếm
- Tương tự BST do dữ liệu đã sắp xếp.
- Nếu rỗng → false. Nếu đến gốc không thấy → false.
- X < khóa trái → tìm cây con trái.
- Khóa trái < X < khóa phải → tìm cây con giữa.
- X > khóa phải → tìm cây con phải.
2. Chèn nút
- Rỗng → tạo gốc.
- Tìm vị trí lá phù hợp chèn.
- Lá 1 khóa → thành nút-2.
- Lá 2 khóa → chèn thành 3 khóa tạm, tách (split) đẩy khóa giữa lên cha.
Ví dụ chèn lần lượt: 10, 5, 8, 15, 23, 21 → hình thành cây 2-3 cân bằng.
3. Xóa nút
- Rỗng → false.
- Tìm X, xóa, điều chỉnh cây.
- X ở nút-3: xóa, điều chỉnh khóa trái/giữa và tổ tiên.
- X ở nút-2: điều chỉnh và tách cây đệ quy, giữ thứ tự.
Hình ảnh minh họa cây 2-3, nút-2, nút-3, quá trình chèn đã bị lược bỏ do định dạng text.