Các thuật toán cân bằng lại (rebalancing Algorithms) có thể thực hiện theo các cách sau:
Thuật toán Day-Stout-Warren
Chúng ta có thể thực sự cài đặt phương pháp rebalance (cân bằng lại) sử dụng thuật toán Day-Stout-Warren. Nó chạy trong thời gian tuyến tính theo số nút.
Dưới đây là trình bày thuật toán DSW cơ bản dưới dạng mã giả.
- Cấp phát một nút gọi là "giả gốc" (pseudo-root) và làm gốc thực của cây thành con phải của giả gốc.
- Gọi hàm tree-to-vine để chuyển cây thành danh sách liên kết đã sắp xếp với giả gốc làm đối số.
- Gọi hàm vine-to-tree để chuyển danh sách liên kết đã sắp xếp thành cây lại với giả gốc và kích thước (số phần tử) của cây làm đối số.
- Gốc thực của cây bằng con phải của giả gốc được thiết lập.
- Cuối cùng, giả gốc bị hủy bỏ (disposed).
Cây "Copy On Write" (Ghi khi sao chép)
Nếu chúng ta có thể chịu đựng thiếu tính tuyến tính (linearizability) (tức là ghi giá trị nhưng khi tìm ngay sau không thấy; cuối cùng sẽ thấy, nhưng sau 100ms-10s), một cây "copy on write" có thể áp dụng: tất cả ghi được thực hiện bởi một luồng (with rebalancing), và định kỳ sao chép cây thành bản sao chỉ đọc (read-only copy) có thể dùng bởi các luồng đọc (reading threads) không cần bất kỳ điều khiển đồng thời (concurrency control), cần xuất bản nó một cách nguyên tử (atomically).
Danh sách bỏ qua đồng thời (Concurrent Skip List)
Một lựa chọn khác là dùng danh sách bỏ qua đồng thời (concurrent skip list): nó cung cấp thời gian tìm kiếm/xóa/chèn trung bình logarit và dễ dàng song song hóa hơn. Có cài đặt lock-free chuẩn cho Java nếu bạn dùng nó. Chúng ta có thể tìm thêm thông tin về concurrent skip lists và cây tìm kiếm cân bằng ở đây. Đặc biệt, có đề cập đến cây chromatic (chromatic tree), được định nghĩa là cây tìm kiếm nhị phân được tối ưu cho cân bằng lại đồng thời (concurrent rebalancing).