Cách tính con trỏ trong cây nhị phân với bố cục van Emde Boas

Question

Tôi muốn triển khai cây nhị phân không có bộ nhớ cache được lưu trữ trong một mảng bằng bố cục van Emde Boas, sử dụng con trỏ ẩn. Tất cả các mục trong cây là số nguyên 32 bit và cây sẽ nhận được khá lớn, do đó lưu trữ các con trỏ sẽ có nghĩa là ít nhất 3x nhiều dữ liệu hơn.

Vấn đề là tôi không thể nghĩ ra bất kỳ cách nào không lặp lại để tính toán con trỏ cho trẻ em trái và phải, được chỉ định một nút (tôi có thể theo dõi bất kỳ thông tin nào khi duyệt qua cây). Nhiều bài báo/bài giảng đề cập đến những cây như vậy với các con trỏ tiềm ẩn, nhưng tôi chưa thấy một thuật toán để tính toán con trỏ. Có cách nào hiệu quả để làm điều đó không?

Answer 1

Bob Copeland có triển khai rất tốt van Emde Boas trees at GitHub. Ông sử dụng con trỏ tiềm ẩn và tính toán các con trỏ bằng cách đầu tiên tính toán con trỏ đầu tiên rộng, sau đó con trỏ vEB là một điều kiện đơn giản.