# Tag Info

## Hot answers tagged trees

20

The short answer is that you use stacks. This is a good example, but I'll apply it to an AST. FYI, this is Edsger Dijkstra's Shunting-Yard Algorithm. In this case, I will use an operator stack and an expression stack. Since numbers are considered expressions in most languages, I'll use the expression stack to store them. class ExprNode: char c ...

19

A parse tree is also known as a concrete syntax tree. Basically, the abstract tree has less information than the concrete tree. The concrete tree contains each element in the language, whereas the abstract tree has thrown away the uninteresting pieces. For example the expression: (2 + 5) * 8 The concrete looks like this ( 2 + 5 ) * 8 | \ | / | | |...

17

There's a couple simple categories you can fit graphs into that makes it easier to classify them. Directed: This is a graph wherein you have parent-child relations that are one way, that is the child may not directly reference the parent Undirected: This is a graph wherein you have node-node relations, they are not parent-child and may go either way ...

13

Here is a general purpose tree traversal implementation that doesn't use recursion: public static IEnumerable<T> Traverse<T>(T item, Func<T, IEnumerable<T>> childSelector) { var stack = new Stack<T>(); stack.Push(item); while (stack.Any()) { var next = stack.Pop(); yield return next; ...

11

A tree is a connected acyclic graph. In the case where we have "parent" links this would just be an undirected tree, but definitely still a tree. If you were to specify that the example is a directed graph it would not be considered a tree (but of course there's no way of telling from the code which was intended). Some computer science "trees" will include, ...

9

There is a significant difference between how an AST is typically depicted in test (a tree with numbers/variables at the leaf nodes and symbols at interior nodes) and how it is actually implemented. The typical implementation of an AST (in an OO language) makes heavy use of polymorphism. The nodes in the AST are typically implemented with a variety of ...

8

A tree is a special kind of graph. More specifically, it's "any connected graph without simple cycles". So, your graph is a tree. It doesn't matter if it grows or not. Yours is a directed graph so it doesn't really matter anyways. It's not a binary tree, if that's what you were asking =)

8

This heavily depends on definition of list and tree. Mathematically list doesn't mean anything and tree is just special subset of a graph. Inferring from your question, your teacher's definition of tree is nested lists. In which case, list of nesting depth of 0 is still a tree. So abc = [1, 2, 3, 4] Is a tree. In this case, the list is subset of tree. ...

7

The following algorithm should do almost what you've asked for. paths : List<String> ;; your list of paths tree : Folder = NEW Folder("") FOREACH path IN paths DO node : Folder = tree FOREACH component IN split(path, "/") DO next : Folder = node.getChild(component) IF next IS NULL THEN next := NEW Folder(...

6

If your trees are isomorphic on principle, there is no point at all in actually maintaining three parallel trees - that's just a waste of pointers and processor cycles. instead you should define a composite type that holds what ever items you want to maintain in parallel, and build one tree containing such composite nodes. Remember, how you access or present ...

6

Your solution seems to try to tackle average reading time of nodes and all paths from them. This will, of course, work, provided it's properly implemented. The problem with this approach is that the quantities you calculate are not reusable. The average reading time of a node depends on how you got to it. Hence the quadratic behaviour of your naive solution....

5

It's a legit approach when you have data that can be nested very deeply/recursively, such as physical containers or for hierarchical data (such as a corporate organization tree, or a filesystem). Your second example may or may not fit tree-models as nicely but I'm not sure since I don't know how different a sub sample is from a sample derivative. Shipments ...

5

By Wikipedia, it looks like your tree is specified by the two properties arborescence and ordered tree (scroll down to find the definition "ordered tree or plane tree.")

5

Trees are Graphs. They are specifically directed, acyclic graphs where all child nodes only have one parent. If you need more than one parent then you use a DAG. If you need cycles or the graph needs to be undirected you'd use some kind of graph implementation. Note that the time and space complexity increases dramatically once you move into full graphs.

5

Proof by induction: Every acyclic graph can be represented as a tree, if all the nodes are connected. So let's think about trees. You've got one root node. Let's look at the simplest, case, in which the tree only has one branch, and so it's a simple linked list. If there are two nodes, there's one edge between them. Add one node to the end of the ...

5

For me, the big advantage of the heterogeneous AST is that it forms a kind of forced, annotated switch statement (assuming a C-like language). For the homogeneous AST you usually end up with some kind of routine or class with a big switch statement. You need to keep track of which child node is what yourself. "First child is the conditional, second the true-...

5

I like to use the word Primary in situations where the word First isn't quite right, but is close. It indicates that it's special in some way, without actually depending on an ordered enumeration. First implies a Second, Third and so on, but Primary could be paired with everything else or Secondary, Tertiary, and only then everything else. Given an ...

5

I don't believe there is a special name for this, it's simply a tree. "Growing in both directions" is purely an artifact of how you drew the tree. Also, it's a little hard to tell from your ASCII art, but if the top and bottom are connected and you have cycles, then this is technically not a tree at all, but a graph (of which trees are a more specific case)....

5

Building the AST from the source text is "simply" parsing. How exactly it is done depends upon the parsed formal language and the implementation. You could use parser generators like menhir (for Ocaml), GNU bison with flex, or ANTLR etc etc. It is often done "manually" by coding some recursive descent parser (see this answer explaining why). The contextual ...

5

If you actually want to PRODUCE every list as different copies, you cannot hope to achieve better than n^2 space in the worst case. If you just need ACCESS to each list: I would perform an in-order traversal of the tree starting from the root: http://en.wikipedia.org/wiki/Tree_traversal Then for each node in the tree store the minimum in-order number and ...

5

Let's assume you have an additional method GetOrCreate(name) that returns a folder for a given name, or creates it if no such folder exist, and that you have a root folder that contains your whole hierarchy. Then given a list of strings path, we can easily implement an iterative solution: Folder current = root; for (name in path) current = current....

5

A first observation is that canonical GA is based on a fixed length representation (a fixed number of genes in specific loci on the chromosome). So crossovers GA operators are similar to biological sexual reproduction: the genetic material from both mother and father is combined in such a way that genes in the child are in (approximately) the same position ...

4

You need a recursive data structure. Something like this: public class TreeNode<T> { public T node { get; set; } public List<TreeNode<T>> descendants { get; set; } }

4

Unlike a plain binary tree, AVL trees are self-balancing. When an element is inserted into an AVL tree, the tree may need to perform node rotations in order to maintain a certain tree depth, which allows for logarithmic lookup time. So, if you try to build a second AVL tree using pre-order node traversal on an existing AVL tree, the resulting tree will not ...

4

The canonical design pattern used for tree-like data structures is the Visitor. You start at the root (or the current node) and visit each node in order (preorder, postorder, whatever order you need), performing the required task at each node. It's not clear from your description, but I get the impression that a Visitor that returned the information ...

4

It is important to note that hash tables only have average access time of O(1). This means a particular operation could be much worse. Additionally, there are several requirements for properly formed hash trees: Mostly empty - few hash algorithms perform well beyond 70% usage, and most recommend 50% usage. Collision handling is complex - either having to ...

4

Avoid nesting logic into inner blocks as much as possible. It makes code harder to read. if (!A) return if (B) execute C if (D) execute E Exit if not A. Otherwise B or D, but if you know D is already true when B is false. You could drop the if (D) and just execute E. In cases like this it's preferred to use a switch. if (!A) return switch ...

4

If you have an estimate for the depth of your tree beforehand, maybe it is sufficient for your case to adapt the stack size? In C# since version 2.0 this is possible whenever you start a new thread, see here: http://www.atalasoft.com/cs/blogs/rickm/archive/2008/04/22/increasing-the-size-of-your-stack-net-memory-management-part-3.aspx That way you can keep ...

4

pre order traversal is a traversal, it visits every node in a binary tree Depth First Search is a search, it goes around an arbitrary graph looking for a certain node (that it works best in a non cyclic graph (a.k.a. tree) is irrelevant) this alone is a large enough difference to call them difference names

4

The answer to this kind of question is always the same: if the language doesn't provide a useful abstraction, you must emulate it. (Whether doing this is worth the additional effort depends on the specific circumstances of your program, which you know better than we do, but for the purposes of this answer I'm assuming that it is.) Polymorphism is the ...

Only top voted, non community-wiki answers of a minimum length are eligible