3 ms·
A binary search tree with string keys is just a compressed version of a binary tree with bit keys, which greatly reduces the number of nodes. E.g. this has thr
by kazinator 5y ago
A binary search tree with string keys is just a compressed version of a binary tree with bit keys, which greatly reduces the number of nodes.
E.g. this has three nodes:
dog
/ \
ant fly
But:
ant -> 61 6E 74 -> 011000010110111001110100
dog -> 64 6f 67 -> 011001000110111101100111
fly -> 66 6C 79 -> 011001100110110001111001
Thus
R
/
0
\
1
\
1
/
0
/
0
/ \
,---' `-------.
/ \
/ \
0 1
/ / \
/ ,-------' `---.
/ / \
0 0 1
\ / /
1 0 0
/ / /
0 0 0
\ \ \
1 1 1
\ \ \
1 1 1
/ / /
0 0 0
\ \ \
1 1 1
\ \ \
1 1 1
\ \ /
1 1 0
/ \ /
0 1 0
/ / /
0 0 0
\ \ \
1 1 1
\ \ \
1 1 1
\ / \
1 0 1
/ / \
0 0 1
\ \ /
1 1 0
/ \ /
0 1 0
/ \ \
0 1 1
(ant) (dog) (fly)
:)
- JadeNB 5y agoYour 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 agoIt'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.