Xử lý các khóa trùng lặp trong một cây AVL

Question

Tôi muốn thực hiện các phím trùng lặp hỗ trợ avl-tree nhưng có vấn đề với hành vi mặc định của binary search tree với các bản sao có thể làm cho các nút có khóa bằng nhau ở bên trái và bên phải cha mẹ.

Ví dụ khi thêm ba nút tất cả với phím A sẽ gây ra cây để làm một vòng quay là một cái gì đó như thế này:

A 
/\ 
A A 

Vì vậy, nhận được tất cả các mục với phím đó sẽ là một vấn đề ... và tìm kiếm theo cả hai hướng là không tốt. Các giải pháp mà tôi đã nghĩ là làm cho mỗi cửa hàng lưu trữ một mảng các bản sao vì vậy khi thêm một mục mới đã tồn tại sẽ chỉ cần thêm một mục mới vào mảng, loại bỏ mục có khóa sẽ xóa toàn bộ trong khi tìm tất cả các mục có khóa sẽ trả về mảng đó.

Có bất kỳ phương pháp khác để xử lý các bản sao?

Mục chèn có một khóa và giá trị .. vì vậy tôi cần phải lưu trữ các giá trị inorder để trả về chúng bằng findAll với phương thức khóa nhất định.

Answer 1

Một cách tiếp cận chung khác là làm cho phần giá trị của khóa trong nội bộ trở nên không thực sự có khóa trùng lặp nữa. Bạn sẽ cần cả khóa và giá trị để xóa mục nhập khỏi cây cho phép trùng lặp.

Để tìm kiếm một chìa khóa mà không biết giá trị, sau đó bạn sẽ làm điều gì đó tương tự (pseudo-code):

searchResult = myTree.SearchGreaterOrEqual(Key); 
found = (searchResult != null) && (searchResult.Key == Key); 

Answer 2

Có mỗi nút chứa số lượng: việc cộng các bản sao sẽ tăng số lượng, việc xóa sẽ giảm số lượng trừ khi đó là 1, trong trường hợp đó toàn bộ nút sẽ bị xóa.