search

Konard / LinksPlatform

Holistic system for storage and transformation of information based on associative model of data. Целостная система для хранения и обработки информации, основанная на ассоциативной модели данных.
https://linksplatform.github.io/Documentation/
GNU Lesser General Public License v3.0
57 stars 9 forks source link

Binary Search Tree optimization #98

Closed Konard closed 8 years ago

Konard commented 8 years ago

https://github.com/Konard/sbt

AVL: https://en.wikipedia.org/wiki/AVL_tree http://www.youtube.com/watch?v=5C8bLQBjcDI&feature=related https://ru.wikipedia.org/wiki/%D0%90%D0%92%D0%9B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE

Konard commented 8 years ago

Looks like it may be possible just to change balancing logic to be as fast as AVL. Original SBT balancing algorithm tends to be 100% balanced on every insert / deletion, and it is done using recursive balacing. AVL have different approach to balancing, so it is not so cost effective.

Konard commented 8 years ago

Threated tree implementation can speed up complex searching by speeding up travesal through tree.

Konard commented 8 years ago

https://www.youtube.com/watch?v=ww-1SCSMlr8 https://www.youtube.com/watch?v=k4j0s98kl2k https://www.youtube.com/watch?v=vGPUO8BYKSI https://www.youtube.com/watch?v=4FCPEOdzio0 https://www.youtube.com/watch?v=HzAyIzI6C7U https://www.youtube.com/watch?v=S-qrQuxxO_4 https://www.youtube.com/watch?v=bRELPJqH2Yo https://www.youtube.com/watch?v=lfHN-IjITu8

Konard commented 8 years ago

Done at https://github.com/Konard/LinksPlatform/commit/77c9988c619dc05e5b65478b6b4c355ba5d02db2 thanks to https://github.com/programmatom/TreeLib/issues/5 (TreeLib project)