3 ms·

Your new tree has the same nodes (with an additional root node), but I can't see how it records that `dog` is the parent of `ant` and `fly`.

by JadeNB 5y ago

kazinator 5y ago
"dog" being the parent of "ant" in the original string-based binary search tree is just an accident. Consider the characters. Is the "g" character in "dog" the parent of the "a" in "ant"? We can "explode" the original tree like this: [ L | R | S ] / \ [L | R | S ] [0] -> 'd' \ [1] -> 'o' "ant" [2] -> 'g' [3] -> 0 // null-terminated C string :) Now we have an anonymous node which is has two links to other nodes, and a link to a string. So it is the parent of the string and of the two nodes. What the binary search tree is doing is representing the sequence { "ant", "dog", "fly" }. It captures that this sequence has three elements, which are in that order. The fact that "dog" is a parent of "ant" is not relevant in a search tree; it's just an artifact of how the tree is balanced. In the following tree, it is a child of "ant", yet it is an equivalent search tree: ant \ dog \ fly The bitwise tree, a kind of radix tree, does the same thing: it stores "ant", "dog" and "fly", indicating their presence and order in the most detailed way possible: by switching left/right on their individual bits.
- Izkata 5y ago
  > The bitwise tree, a kind of radix tree I believe "trie tree" is the specific name for these un-compacted ones... So, a "bitwise trie" here.
  - co_pilates 5y ago
    It's just called a trie, and yes that's what the described structure is, just a trie on the binary representation of an ascii string. That's different from a search tree, which is used to order things. You can't serialize a trie into an ordered list as easily as a search tree, because that's what a search tree is for. A trie is better if you want to check if a key is already in the collection, because you only have to visit len(key) nodes. I think we just need to realize not every software developer or engineer is a computer scientist, and we should hire more people with the title of computer scientist to help the engineers understand the best algorithms and structures to use. The engineers should be thinking about the bigger picture and should specialize in networking or databases or whatever. We're trying to make every "Software Engineer" into an expert on all levels of the stack, and it's starting to cause issues. You don't see mechanical engineers working on both fasteners (bolts, etc.) and reinforced cement structures at the same time, then tomorrow they design a centrifugal pump, and the next week they're in charge of the new V8 engine project, but as a Software Engineer I do that kind of switching everyday.

Your new tree has the same nodes (with an additional root node), but I can't see how it records that `dog` is the parent of `ant` and `fly`.

by JadeNB 5y ago

Your new tree has the same nodes (with an additional root node), but I can't see how it records that `dog` is the parent of `ant` and `fly`.

kazinator 5y ago

"dog" being the parent of "ant" in the original string-based binary search tree is just an accident. Consider the characters. Is the "g" character in "dog" the parent of the "a" in "ant"? We can "explode" the original tree like this: [ L | R | S ] / \ [L | R | S ] [0] -> 'd' \ [1] -> 'o' "ant" [2] -> 'g' [3] -> 0 // null-terminated C string :) Now we have an anonymous node which is has two links to other nodes, and a link to a string. So it is the parent of the string and of the two nodes. What the binary search tree is doing is representing the sequence { "ant", "dog", "fly" }. It captures that this sequence has three elements, which are in that order. The fact that "dog" is a parent of "ant" is not relevant in a search tree; it's just an artifact of how the tree is balanced. In the following tree, it is a child of "ant", yet it is an equivalent search tree: ant \ dog \ fly The bitwise tree, a kind of radix tree, does the same thing: it stores "ant", "dog" and "fly", indicating their presence and order in the most detailed way possible: by switching left/right on their individual bits.

Izkata 5y ago
> The bitwise tree, a kind of radix tree I believe "trie tree" is the specific name for these un-compacted ones... So, a "bitwise trie" here.
- co_pilates 5y ago
  It's just called a trie, and yes that's what the described structure is, just a trie on the binary representation of an ascii string. That's different from a search tree, which is used to order things. You can't serialize a trie into an ordered list as easily as a search tree, because that's what a search tree is for. A trie is better if you want to check if a key is already in the collection, because you only have to visit len(key) nodes. I think we just need to realize not every software developer or engineer is a computer scientist, and we should hire more people with the title of computer scientist to help the engineers understand the best algorithms and structures to use. The engineers should be thinking about the bigger picture and should specialize in networking or databases or whatever. We're trying to make every "Software Engineer" into an expert on all levels of the stack, and it's starting to cause issues. You don't see mechanical engineers working on both fasteners (bolts, etc.) and reinforced cement structures at the same time, then tomorrow they design a centrifugal pump, and the next week they're in charge of the new V8 engine project, but as a Software Engineer I do that kind of switching everyday.