Các thuật toán tái cân bằng có thể được thực hiện theo cách sau -
Thuật toán Day-Stout-Warren
Chúng ta có thể thực hiện phương pháp tái cân bằng thực sự bằng cách sử dụng Thuật toán Day-Stout-Warren. Nó tuyến tính về số lượng nút.
Sau đây là phần trình bày về Thuật toán DSW cơ bản trong mã giả.
- Một nút được cấp phát được gọi là "gốc giả" và làm cho gốc thực sự của cây là con bên phải của gốc giả.
- Gọi hàm tree-to-dấm để chuyển đổi cây thành danh sách liên kết được sắp xếp với gốc giả làm đối số của nó.
- Gọi hàm cây nho để chuyển đổi danh sách liên kết đã sắp xếp thành cây một lần nữa với gốc giả và kích thước (số phần tử) của cây làm đối số của nó.
- Gốc thực của cây bằng với con bên phải của rễ giả.
- Cuối cùng thì gốc giả cũng nên được xử lý.
Cây "Copy On write"
Nếu chúng ta có thể chịu được sự thiếu tuyến tính (nghĩa là chúng ta viết một giá trị nhưng khi chúng ta tìm kiếm nó ngay lập tức sau khi không tìm thấy nó; cuối cùng nó sẽ được tìm thấy, nhưng sau 100ms-10s), cây "copy on write" có thể được áp dụng:tất cả các lần ghi được thực hiện bởi một luồng (với sự cân bằng lại) và chúng tôi sao chép định kỳ cây thành bản sao chỉ đọc có thể được thực hiện bằng cách đọc các luồng mà không cần bất kỳ điều khiển đồng thời nào, chúng tôi yêu cầu xuất bản nó theo nguyên tử.
Danh sách bỏ qua đồng thời
Một tùy chọn khác là triển khai danh sách bỏ qua đồng thời:nó cung cấp thời gian tìm kiếm / xóa / chèn chữ hoa chữ thường logarit và dễ dàng song song hóa hơn. Có một triển khai không khóa tiêu chuẩn cho Java nếu bạn tình cờ triển khai nó. Chúng tôi có thể lấy thêm thông tin về danh sách bỏ qua đồng thời và cây tìm kiếm cân bằng tại đây. Đặc biệt, chúng ta có thể nhận được ở đó đề cập đến cây màu, được biểu thị là cây tìm kiếm nhị phân được tối ưu hóa để tái cân bằng đồng thời.