Introducing a tree from scratch

Question

I am trying to learn about trees by planting them from scratch. In this case, I would like to do this in C # Java or C ++. (without using built-in methods)

Thus, each node will store a symbol and there will be a maximum of 26 nodes per node.

What data structure would I use to contain pointers to each node?

I am basically trying to implement a base tree from scratch.

Thanks,

Answer 1

What you are describing is not really a base tree ... in a radix tree, you can have more than one character in a node, and there is no upper bound on the number of child nodes.

What you describe is more limited by the alphabet ... each node can be az, and it can be followed by another letter az, etc. The difference is critical to the data structure that you prefer to hold next-node.

In the tree you are describing, the simplest structure can be a simple array of pointers ... all you need to do is convert the character (for example, “A”) to its ascii value ('65') and subtract the initial offset (65) to determine which "next node" you want. Takes up more space, but very quick insertion and crawl.

In a true radix tree, you can have child nodes 3, 4, 78, or 0, and your "next node" will have the overhead of sorting, inserting, and deleting. Much slower.

I cannot speak with Java, but if I implemented my own base tree in C #, I would use one of the built-in .NET collections. Writing your own sorted list doesn't really help you learn tree concepts, and the built-in optimization of .NET collections is very complicated. Then your code is simple: look at your next node; if there is, grab it and leave; if not, add it to the next node collection.

Which collection you use depends on what you are implementing through the tree ... each type of tree includes trade-offs between insertion time, search time, etc. The choices you make depend on what is most important for the application, not the tree.

Make sense?

Answer 2

What data structure would I use to contain pointers to each node?

A node Each Node must have links to (up to) 26 other nodes in the tree. Inside Node, you can store them in an array of LinkedList, ArrayList, or just about any other collection you might think of.

Answer 3

It does not really matter. You can use a linked list, an array (but this will have a fixed size), or a list type from the standard library of your language.

Using a list / array will mean performing some operations on the index to move through the tree, so it’s easiest to use links to child elements in the parent.

Answer 4

Here, I recently found that it’s not a bad API for trees - although I need graphs, it was convenient to see how it was configured to separate the data structure for the data that it held, so you could have the equivalent of a tree to an iterator to move around the tree and etc.

https://jsfcompounds.dev.java.net/treeutils/site/apidocs/com/truchsess/util/package-summary.html

Answer 5

If you are actually more interested in speed than in space, and if each node represents exactly one letter (implied by your maximum of 26), I just use a simple array of 26 slots, each of which refers to "Node" (node ​​is object containing your array).

The good thing about a fixed-size array is that your look will be much faster. If you were looking for char "c", which is guaranteed to be a lowercase letter, the search would look as simple as:

nextNode=nodes[c-'a']; 

A recursive string search will be trivial.

Answer 6

Thanks for the quick answers.

Yes, the trotter was right. Basically, this is a 26-node (AZ) tree + bool isTerminator.

Each node has these values, and they are related to each other.

I haven't learned pointers yet, but today I'm trying to implement this from scratch using unsafe C # code, where it's useless.

Therefore, I would appreciate it if someone could provide me with a code to start working in C # using an internal tree class. As soon as I can get started, I can port the algorithms to other languages ​​and just change them to use pointers.

Thanks a lot michael

Answer 7

Check out this Simeon Pilgrim block, “ Camp Camp Code Overview . ” One solution uses Radix in C # and you can download the solution.