Nostr Web Client

trees can be scary to programmers: lots of pointers flying around everywhere to different parts of memory, lots of memory allocations, but fixed and balanced trees have a very simple representation that you can store and navigate in a straight line (programmers like straight lines, we call them arrays)

The numbers in this image are the index into an array. Given any position in the tree, you can find a parent or sibling element with a few arithmetic operations which result in another index.

No allocating complex data structures, no chasing pointers around, just a bit of math to jump around a tree flattened into a straight line. As a programmer finding elegant solutions like this is a pure dopamine hit. Code can be beautiful 🥹

#nerdstr #treestr

Reply to this note

Please Login to reply.

Discussion

d0708145... 1y ago

I thought they just converted Co2 to o2🤔??

சாரு-秋陽 1y ago

For some reason, when learning recursion the standard example is Fibonacci series, which didn't help the case much....

Then when learning trees & balancing , it all finally clicked into place. Trees are beautiful 💙

BTC_P2P 1y ago

Trees are scary when you’re on shrooms too

Phil 1y ago

If a tree falls in your code but no one’s around to hear it, does it make a sound?

Satstack 𓆀⚡︎ 1y ago

🫡

edo 1y ago

I agree with the elegance. This is how heaps are stored in arrays: https://en.m.wikipedia.org/wiki/Heap_(data_structure)

jb55 1y ago

Also the sibling calculation is super simple:

sibling = ind + ((ind & 1) ? 1 : -1)

Niall Young 1y ago

implementation detail 🤣

Leo Fernevak 1y ago

Nice, elegant tree. Although it is limited to a pair-structure.

In many cases I don't have an ordered tree structure. When I create a procedural dungeon I start with distributing rooms and then write a function that walks between the rooms, to establish which pathways and squares are most commonly accessed, without the hindrance of walls. Next I write a function that transforms the array of walking patterns into corridors connecting the rooms. Procedurally generated obstacles that prevent direct walking from point A to B can help making the dungeon less linear. This could represent areas of rock that was too hard to cut through. The testing functions are ad-hoc trees that explore the dungeon and branch when necessary, then pruned as the "explorers" hit a dead end.

jb55 1y ago

I haven’t needed this until now. I had a balanced merkle tree (bittorrent v2 infohashes with branching factor of 2 and 16KiB blocks) so its perfect for that.

tegila.js 1y ago

Most of the notes don’t have 1Kb. That said maybe isn’t need to think about complex torrent implementation for notes.

Torrents for #nostr is more about decentralization topology and reform of relays.

Relay becoming DHT, peer discovery and public stuff.

The content being ripped of the relays and going to p2p publishers.

Publishers sometimes are paid-relays with private contents. Sometimes it’s the user itself #p2p controlling who view his posts, storing likes and moderating replies.

User being in total control of the content is the game changer.

I call it “a better nostr” or reNostr.

jb55 1y ago

I am not planning on using BitTorrent v2 for replicating notes, but as a potential way to share files parallel to the protocol like we use lightning for money.

tegila.js 1y ago

I see. ***So the relay keep in control***. Hope soon Google run it’s relay so we can all move to the biggest server again.

Also the spammers started to attack #nostr threads and there’s nothing a relay can do to stop it.

Maybe Google can help to filter it with their AI and their agenda is back again. /s

It’s like an open Twitter now.

atyh 1y ago

🤡

magic 1y ago

getting all emotional over a heap

jb55 1y ago

🥹 right in the feels

MartianX 1y ago

Math is both useful and beautiful

Emanuel 1y ago

Kd-trees are a really beautiful variety of them.