Binary trees
20 views
Skip to first unread message
The Beez
Dec 28, 2016, 5:58:36 AM12/28/16
to 4tH-compiler
Hi 4tH-ers!
Binary trees are handy things. They allow you to store stuff randomly and under the hood they are broken down to a structure that allows to to retrieve them almost as fast as using a binary search. I had been looking for a compact but complete implementation (especially deletion is tricky) and finally I found it. Yes, I ported it to 4tH - but not exactly. I added a member - the value.
By adding a value to a binary tree, you can not only retrieve things quickly, you can also associate a value with it. Today I put that in practice by adding a new library member BINTRKV.4TH. It took me a few minutes to hack together. We already have loads of associative array implementations, but they all have a catch. This one takes a massive amount of code and (dynamic) memory by comparison, BUT is it virtually trouble free:
Just define a variable and initialize it:
include lib/bintrkv.4th
variable kv NULL kv !
And off you go!
15 5 kv put
100 6 kv put
5 kv get .
6 kv get . cr cr
25 s" alpha" kv put$
35 s" beta" kv put$
s" alpha" kv get$ .
s" beta" kv get$ . cr cr
Wow, ain't that cool?
Code in SVN.
Hans Bezemer
Binary trees are handy things. They allow you to store stuff randomly and under the hood they are broken down to a structure that allows to to retrieve them almost as fast as using a binary search. I had been looking for a compact but complete implementation (especially deletion is tricky) and finally I found it. Yes, I ported it to 4tH - but not exactly. I added a member - the value.
By adding a value to a binary tree, you can not only retrieve things quickly, you can also associate a value with it. Today I put that in practice by adding a new library member BINTRKV.4TH. It took me a few minutes to hack together. We already have loads of associative array implementations, but they all have a catch. This one takes a massive amount of code and (dynamic) memory by comparison, BUT is it virtually trouble free:
Just define a variable and initialize it:
include lib/bintrkv.4th
variable kv NULL kv !
And off you go!
15 5 kv put
100 6 kv put
5 kv get .
6 kv get . cr cr
25 s" alpha" kv put$
35 s" beta" kv put$
s" alpha" kv get$ .
s" beta" kv get$ . cr cr
Wow, ain't that cool?
Code in SVN.
Hans Bezemer
Reply all
Reply to author
Forward
0 new messages