Jump to content

Draft:Golubev's ordering

From Wikipedia, the free encyclopedia

Golubev's ordering is a way of ordering values in binary presentation. When ordering by this way Golubev's tree is used.

Golubev's tree is data structure of the following: every link contains two values which can be either pointers or naught values: if a link has a marking zero-value descender the first value points to the marking zero-value descender link and in another case is naught value, if a link has a marking one-value descender the second value points to that marking one-value descender and in another case is naught value and links are joined so that link-by-link paths link-by-link bit-by-bit represents bits presentation of values.

As a first step of Golubev's ordering values are to be put into Golubev's tree and then both link-by-link reading from the tree in zero-marking-descender-first depth-first order with hierarchically sharing prefixes among values automatically provides bit-by-bit presentations of values in increasing order and link-by-link reading from the tree in one-marking-descender-first depth-first order with hierarchically sharing prefixes among values automatically provides bit-by-bit presentations of values in decreasing order.

Arthur Golubev (Arthur Golubev 1985) first time published code which demonstrates idea of this ordering in 2025-02-26 in public repository services github.com (https://github.com/ArthurGolubev1985/FastOrderingIdeaDemo), codeberg.org (https://codeberg.org/ArthurGolubev1985/FastOrderingIdeaDemo) ang gitflic.ru (https://gitflic.ru/project/arturische/fastorderingideademo).

References

[edit]