Java – find the median in the B-tree

I need to implement a B - tree

I need to create the following methods:

>Insert (x) – 0 (log_t (x)). > Search – successful search – o (log_t (x)) Unsuccessful search – o (1) {high probability}

So I started to implement insert (x) – every time I have a complete leaf, I want to divide it into two separate leaves The key of one key is equal to or lower than the median key, and the second key will contain the key with a value higher than the median

How do I find this median without compromising runtime?

I thought:

>Each internal node and leaf is represented as a smaller B-tree, but the median is the root (or an element in the root) only when the tree is completely balanced. > Each internal node and leaf is represented as a bidirectional linked list And try to get the median key when inserting input, but the input does not apply to it. > Representing as an array may give me the middle, but when I split it, I need at least o (n / 2) to insert the key into the new array

What can I do?

Wise thinking about search: the difference between successful and unsuccessful search is to search in the leaves, but I still need to "run" through different keys in the tree to determine whether the key is in the tree How could it be o (1)?

Solution

In the B tree, all values are stored in leaves

Please note that you can add the pointer of each leaf to the next leaf. In addition to the standard B tree, you can also get an ordered list of links containing all elements

Now, note that suppose you know what the current median is in this linked list – at the time of insertion / deletion, you can cheaply calculate the new median (it can be the same node, next node or previous node, no other choice) Note that modifying this pointer is O (1) (although the insert / delete itself is O (logn)

Given this knowledge – you can cache the pointer to the median element and ensure that it is retained when deleting / inserting When you ask for a median – just take the median from the cache – o (1)

For unsuccessful searches - O (1) {high probability} - this is scream Bloom filters, which is a probability set implementation. There are never false negatives (it has never been said that something is not set), but there are some false positives (it is said that something is in the cache, but in fact it is not)