Jump to content

Draft:Golubev's tree (data structure)

From Wikipedia, the free encyclopedia

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. Such data structure is efficient for storing collections and dictionaries and is efficient for ordering elements (it requires only putting values into the tree and reading in either zero-first or one-first depth-first order them).

Without modifications such data structure is efficient for storing collections, if in links which potentially are terminal for a value to add flags whether the link is terminal for a value or not and space for a value then is efficient for storing dictionaries and is efficient for ordering elements (it requires only putting values into the tree and reading in either zero-first or one-first depth-first order them).

Arthur Golubev (Arthur Golubev 1985) first time published code with using the data structure which demonstrates idea of ordering using this data structure 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]