Skip to content
New issue

Have a question about this project? # for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “#”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? # to your account

Segment map is not self-balancing. #3

Open
RobertDurfee opened this issue Aug 12, 2020 · 0 comments
Open

Segment map is not self-balancing. #3

RobertDurfee opened this issue Aug 12, 2020 · 0 comments
Assignees
Labels
enhancement New feature or request

Comments

@RobertDurfee
Copy link
Owner

RobertDurfee commented Aug 12, 2020

Given the level of effort that it took just to get the segment map working without self-balancing, this hasn't been implemented yet. The plan is to use AVL-style self-balancing in the future. The current testing suite forcibly constructs trees in multiple ways so all tree arrangements should be correct no matter in what order operations are called.

Workarounds:

  • The correctness of the segment map is not dependent on whether it is self-balancing or not. However, without self-balancing, the performance of operations is not the desired O(log n). In fact, my observations suggest the tree is typically linear in practice.
@RobertDurfee RobertDurfee added the enhancement New feature or request label Aug 12, 2020
@RobertDurfee RobertDurfee self-assigned this Aug 12, 2020
# for free to join this conversation on GitHub. Already have an account? # to comment
Labels
enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

1 participant