Skip to content
New issue

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

Sign up for GitHub

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

Already on GitHub? Sign in to your account

Jump to bottom

Implement tree delete #5

Closed
declanvk opened this issue Apr 2, 2022 · 3 comments
Closed

Implement tree delete #5

declanvk opened this issue Apr 2, 2022 · 3 comments
Assignees
@declanvk
Labels
enhancement New feature or request

Comments

@declanvk
Copy link
Owner

declanvk commented Apr 2, 2022

Problem

  • Delete entries from a tree is a useful operation and is not currently implemented

Solution Sketch

  • Copy the implementation of insert and do the inverse
@declanvk declanvk added the enhancement New feature or request label Apr 2, 2022
@declanvk declanvk self-assigned this Apr 2, 2022
@declanvk
Copy link
Owner Author

declanvk commented Jun 7, 2022 •
edited
Loading

Examples of a delete with a node contraction.

Before

small_tree_with_prefix

After Deleting Different Nodes

After Deleting Node C

small_tree_with_prefix_delete_fixup_prefix

After Deleting Node D

small_tree_with_prefix_delete_pull_up_single_node

After Deleting Node B

small_tree_with_prefix_delete_pull_up_root

@declanvk
Copy link
Owner Author

declanvk commented Sep 2, 2022

Examples of delete with a larger node

Before

medium_tree

After

medium_tree_delete_without_merge

declanvk added a commit that referenced this issue Oct 4, 2022
@declanvk
Implement delete function
62dec88 
**Description**
 - Implement tree delete, which returns deleted node and new root
 - Extend existing fuzzer to use deletes in normal operation
 - Add unit tests for deleting
 - Add `convert_tree_to_dot_string` utility which converts any tree to
   the DOT format to visualize as a graph

**Motivation**
This change closes issue #5. This function is needed to round out the
basic requirements of a tree data structure.

**Testing Done**
 - Ran fuzzer for 8ish hours
 - `cargo test`
 - `cargo miri test`
 - `cargo clippy`
@declanvk
Copy link
Owner Author

declanvk commented Oct 4, 2022

Implemented in 62dec88

@declanvk declanvk closed this as completed Oct 4, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@declanvk declanvk

Labels
enhancement New feature or request
Projects
None yet
Milestone
No milestone
Development

When branches are created from issues, their pull requests are automatically linked.

impl-delete declanvk/blart
1 participant
@declanvk