data-structuresb-tree# How to delete a key from a B+ Tree such that this key exist in an internal node and has another copy from it in a leaf node?

All the online tutorials said that you shall delete the copy in the leaf node then make the other copy in the internal node = (the successor of that key) , my question is that what guarantees for us that this successor wasn't existing in an internal node before replacing our key copy in the internal node by it , because if such a thing happened we will have the value of that key (successor) existing more than one time in more than one internal node.

I found no answers for that in the online tutorials

Solution

Before getting to your question, it is a misconception to regard the keys of the internal nodes as actual *data* keys. They are merely index-keys, and don't really need to belong to the tree's data set, although it is common to have them updated to reflect the minimum key that is present in its corresponding subtree.

In comments you refer to this documentation and to the example of the deletion of the key 25:

But note that the update of the key in a parent node is not strictly necessary. The same documentation stated at the start:

- STEP 1 Find leaf L containing (key,pointer) entry to delete
- STEP 2 Remove entry from L
- STEP 2a If L meets the "half full" criteria, then we're done.

The case where key 25 is removed, fits the condition of step 2a, i.e. after it has been removed from the leaf node, "we're done". This is actually true. In this case the *update* of the key in ancestor node(s) is optional.

Now to your main question:

what guarantees for us that this successor wasn't existing in an internal node before replacing our key copy in the internal node by it

The keys that exist in internal nodes are always a lower bound for the keys in the next subtree below it. Unless that subtree will undergo shifts or merges due to the deletion, the least key in that subtree will become a key that previously was *not* the least key in that same subtree. In the example, 28 was not the least key in the subtree because that least key in that subtree was 25. So we can be sure 28 is not present in an internal node.

It is a different story if the leaf node happened to **only** have 25 as key, but then we get into a shift or merge operation, which will bring updates to multiple keys.

- JS - recursive function on multidimensional array to filter out only "checked" items (and its parents if a child is selected)
- Comparing two similar objects (holding same keys) and returning key value pairs that are different
- Linked List Replacement Function with Head, Tail, and Size Management
- Efficient Array Storage for Binary Tree
- How to render data and initialize an UI event handling upon this data after the data has been loaded by an asynchronous API call?
- Hackerrank Repeated String infinite loop problem
- Using asterisk and spaces print the letter R [ 21*20]
- Split a collection into `n` parts with LINQ?
- How can I enhance the time complexity of arranging bricks into stacks based on specific conditions?
- Octree implementation in Rust: why is the insert function duplicating insertions and how could I go about fixing this?
- how to traverse an NxN grid diagonally
- Name of binary data structures that contain fixed-length components?
- Insert after specific element in LinkedList java
- inserting in binary tree doesn't work using java
- Generate simple URL patterns from a list of examples
- Explain time complexity of permutations using the mathematical expression
- Why AddAfter() has constant time?
- 2D peak finding algorithm in O(n) worst case time?
- C# Multiway Linked List
- Find Elements occurring odd number of times in a list
- Difference between back tracking and dynamic programming
- How to build a trie for finding exact phonetic matches, sorted globally by weight, and paginated? (Building off this example)
- Is there an algorithm to find the closest element to X in an unsorted array in Ω(logN)?
- Difference between vertices and edges [Graphs, Algorithm and DS]
- How to find the time comlexity when comparing sublists?
- My quicksort algorithm is very slow so what can I do to make it faster?
- How are Linked Lists implemented in the Ready Queue before moving onto the scheduler during the PCB implementation?
- Convert a sorted array into a height-balanced binary search tree by picking middle element -- why does it work?
- Minimum number of coins needed for amount with infinite coins available. Understanding the optimization
- How is my algorithm for stock span problem incorrect?