Tag Info

Hot answers tagged

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 ...


15

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 | \ | / | | ...


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 =)


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 ...


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

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

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

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, ...


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 ...


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

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.


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 ...


3

Simple Mutable JTree Example Code (complied and tested with Java 7 to make above image): import java.awt.*; import javax.swing.*; import javax.swing.tree.*; public class SimpleTree extends JFrame { public static void main(String[] args) { new SimpleTree(); } public SimpleTree() { super("Mutable Varied JTree"); ...


3

If I would do it, I would crawl everything with Selenium, even if it is slow it works behind a browser so it will not be seen as a crawler, it has JavaScript, you can do logins, you can press buttons, you can use Xpath to select what you want, you can save the pages containing images, and many more. On the other hand if you just want an offline Wikipedia ...


3

if children are ordered, then you can use the following schema: empty string means the root 1.0.3 means the fourth child of the first child of the second child of the root. It is short, allows you to fetch a node from its ID, is unique, and is hierachical. It is a kind of prefix tree.


3

You seem to have answered you own question. Have each node hold the count of its descendents plus one (itself). Every time you remove a node you decrement each count on the path back to the root. When inserting you instead increment each count on that path. This way each node contains the total number of nodes in its sub-tree. This will work fine for n-ary ...


3

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 ...


3

The undesirable part of your approach comes from having the data objects themselves unfreezing (loading, deserialising) themselves. This is not a simple problem! Ideally you want your data objects being quite simple, and some external agent being responsible for deserialising and serialising them using data that lives on disk, or on the network, etc. One ...


3

I don't know if there is a official name for it. I would call it "tree with back pointer", or more specific "B-Tree with back pointer" ... I found also the names Doubly-Linked Lists and Tree Node List. According to it, you could call Doubly-Linked Tree


3

You work the visitor pattern around a recursive structure the same way you would do anything else with your recursive structure: by visiting the nodes in your structure recursively. public class OperationNode { public int SomeProperty { get; set; } public List<OperationNode> Children { get; set; } } public static void VisitNode(OperationNode ...


3

I have implemented the visitor pattern on a recursive tree before. My particular recursive data structure was extremely simple - just three node types: the generic node, an internal node that has children, and a leaf node that has data. This is much simpler than I expect your AST to be, but perhaps the ideas can scale. In my case I deliberately did not ...


3

Consider any minimum spanning tree. Choose some vertex as the root. Then each vertex has one parent, except the root.


3

The Boost library for C++ provides a data structure it calls multi_index_container which offers iteration and queries based on several keys. The name kind of works, as it's a set with multiple indexes, each accelerating a different kind of query. This is not too different from the typical RDBMS table which also has indexes to improve query and iteration ...


3

Well, you add a child to the parent. But consider that the root can't add a sibling. This means that sibling-adding isn't something that a node in general knows how to do. You can check whether the parent is null, but (assuming you're doing OO) purists would say to put "add sibling" somewhere outside of your node class. Often you have a wrapping "Tree" ...


3

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 ...


3

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


2

You have to do what works for you. If you think that you can better understand a project and demonstrate it to other people using your methods, there probably the right ones.



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