The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
2answers
58 views

Segregating interfaces/concerns to a tree [duplicate]

When working with a single object there are a number of ways to segregate interfaces to it. Breaking it into smaller components that can be treated independently. Breaking it into simpler ...
0
votes
4answers
233 views

What do you call a tree that grows in both directions? [closed]

What would be the technical term for a tree that grows in both the directions, starting from the root in the middle? The central idea being that new elements can be added to the tree (Now, I am not ...
1
vote
1answer
62 views

About AST construction in LL1 non recursive parser

I have implemented a LL1 parser in a non recursive approach with a explicit stack. The following algorithm is from the Dragon Book: set zp to point to the first symbol of w; set X to the top stack ...
0
votes
0answers
32 views

Looking for a Treemap tiling algorithm

I'm looking for an algorithm to convert a tree of data into a 2 dimensional treemap view. http://en.wikipedia.org/wiki/Treemapping I can do all the coloring in and drawing myself, but if there was ...
0
votes
1answer
33 views

What is the difference between a Splay Tree and an Optimal Binary Search Tree?

Both these trees try to keep the most frequently accessed element at the top. Is there any difference between these two trees?
2
votes
2answers
198 views

Is Pre-Order traversal same as Depth First Search?

It seems to me like pre-order traversal and DFS are same as in both the cases we traverse from root till the left branch and back to root and then to the right branch recursively. Could any please ...
5
votes
4answers
825 views

How do I traverse a tree without using recursion?

I have a very large in memory node tree and need to traverse the tree. Passing the returned values of each child node to their parent node. This has to be done until all the nodes have their data ...
0
votes
1answer
52 views

Verify 0 or 2+ sub sections in a section

There is a rule in writing: When you break a section into subsections, typically it should have more than one subsection. This goes back to the old high school composition rules: if you have an A. ...
4
votes
2answers
209 views

Is a tree with nodes that have reference to parent still a tree?

If we make reference to the parent for each node in a tree, do we still have a tree (by definition) anymore? Wikipedia definition is: In computer science, a tree is a widely used abstract data ...
4
votes
3answers
313 views

Optimal “if-else” tree algorithm to minimize duplicate code

I'm having trouble formulating this problem as an algorithm: I have a set of conditionals (combined with &&) and operations, for example: if (A && B) execute C else if (D ...
1
vote
1answer
76 views

Tree position terminology/naming

This is a naming things question. I am processing trees (XML documents), and there are often special rules applied to nodes based on structure. It's been very difficult coming up with concise naming ...
0
votes
0answers
53 views

Hierarchic (tree) access control

I am currently at the task to create an hierarchic user management system. The requirements for me are to have users with rights (roles), customers with rights and groups (containers for customers ...
3
votes
2answers
110 views

Reconstructing a tree from depth information

I have a data structure that describes a tree. Nodes are ordered, with "depth" information, and knowing the order and the depth the tree can be reconstructed. I'm not entirely sure how to describe it ...
0
votes
2answers
91 views

By the definition of a Tree(ADT), is it “wrong” for a node to add a sibling?

The title pretty much says it all. I'm just having a little computer science exercise and am building a Tree. I want a node to be able to add a sibling which requires one to first get a reference to ...
1
vote
1answer
113 views

Is there a name for this tree variant?

So I've created (and I'm sure someone else has come up with this before - I'm not claiming to have invented it) a data structure which consists of a binary search tree, only instead of each node ...
-1
votes
2answers
66 views

Store a tree with near next neighbours

I would to find an efficient structure (speed and volume) to store nodes and their neighbourhood. My input is build out of stings in the following format ./X/Y.log where X ∈ [0,359] and Y ...
4
votes
2answers
96 views

Placing elements in graph with a streaming/online algorthm

We have a stream of points with about 1000 points per second. For each point, we have a complex vector (hundreds of dimensions). Our goal, for each point is to link it to the 5 closest points that ...
4
votes
1answer
697 views

Homogeneous vs. heterogeneous AST representation

What are the reasons to choose a homogeneous vs. a heterogeneous AST representation for implementing a complex domain-specific programming language? Just to be very clear about what I'm asking, here ...
2
votes
3answers
523 views

How can you prove an acyclic graph has n-1 edges? [closed]

I'm not so hot on the maths for this but for what I understand... A graph g exists with v vertices and edges. g = (V,E); The spanning graph for this is an acyclic copy of this where all the vertices ...
13
votes
3answers
2k views

Implementing the Visitor Pattern for an Abstract Syntax Tree

I'm in the process of creating my own programming language, which I do for learning purposes. I already wrote the lexer and a recursive descent parser for a subset of my language (I currently support ...
2
votes
1answer
290 views

Finding subtree in a tree

I have a tree: a / \ b c / \ d f / \ g h And the pattern: x / \ y z / \ q p As output I would like to have: x: a y: b z: c q: d p: f and x: b y: f z: c q: ...
1
vote
1answer
278 views

Name for a tree where nodes hold a reference to their parent as well as their children

I am creating a tree where some nodes have a reference to their parent as well as their children. It feels like a tree version of a doubly linked list. Is there a name for this?
4
votes
1answer
104 views

Design pattern for isomorphic trees

I want to create a data structure to work with isomorphic tree. I don't search for a "algorithms" or methods to check if two or more trees are isomorphic each other. Just to create various trees with ...
1
vote
2answers
758 views

Tree vs Graphs in search

Could anyone give a clear and concise explanation for when you use graphs vs when to use trees for data structures?
5
votes
2answers
668 views

Patterns for a tree of persistent data with multiple storage options?

I have a real-world problem which I'll try to abstract into an illustrative example. So imagine I have data objects in a tree, where parent objects can access children, and children can access ...
0
votes
0answers
134 views

How to find optimal path visit every node with parallel workers complicated by dynamic edge costs?

Say you have an acyclic directed graph with weighted edges and create N workers. My goal is to calculate the optimal way those workers can traverse the entire graph in parralel. However, edge costs ...
6
votes
1answer
1k views

What is the usage of Splay Trees in the real world?

I decided to learn about balanced search trees, so I picked 2-3-4 and splay trees. What are the examples of splay trees usage in the real world? In this Cornell: ...
1
vote
2answers
469 views

Count function on tree structure (non-binary)

I am implementing a tree Data structure in c# based (largely on Dan Vanderboom's Generic implementation). I am now considering approach on handling a Count property which Dan does not implement. The ...
6
votes
2answers
306 views

Web Crawler for Learning Topics on Wikipedia

When I want to learn a vast topic on wikipedia, I don't know where to start. For instance say I want to learn about Binary Stars, I then have to know other things linked on that pages and linked pages ...
-1
votes
2answers
90 views

Figuring a max repetitive sub-tree in an object tree

I am trying to solve a problem of finding a max repetitive sub-tree in an object tree. By the object tree I mean a tree where each leaf and node has a name. Each leaf has a type and a value of that ...
12
votes
5answers
883 views

How should I create a mutable, varied jtree with arbitrary/generic category nodes?

Please note: I don't want coding help here, I'm on Programmers for a reason. I want to improve my program planning/writing skills not (just) my understanding of Java. I'm trying to figure out how to ...
2
votes
2answers
830 views

Design pattern for access to tree-like database in Java?

I'm developing a Roleplaying character viewer/manager programme for a locap LARP system. The Characters have access to skills that are layed out in a tree-like structure. There are a lot of skills, ...
1
vote
2answers
353 views

Efficient way to compare scene-graph trees

I'm designing a scene graph system, where it is required to compare two trees. The trees are populated with individual objects, each with varied number of children; and they have a root. Eg: Parent: ...
4
votes
1answer
277 views

Inexpensive generation of hierarchical unique IDs

My application is building a hierarchical structure like this: root = { 'id': 'root', 'children': [ { 'name': 'root_foo', 'children': [] }, { 'id': 'root_foo2', 'children': [ { ...
3
votes
3answers
340 views

What is the name of this tree?

It has a single root and each node has 0..N ordered sub-nodes . The keys represent a distinct set of paths. Two trees can only be merged if they share a common root. It needs to support, at minimum: ...
1
vote
2answers
545 views

In order traversal of M way Trees

If we have a 4 way tree such as the one shown below, and we do an in order traversal, what would the output of the in-order traversal be for an M-way tree? In which order would the nodes be visited? ...
0
votes
1answer
392 views

Why can't an AVL tree be recreated using pre-order traversal?

Given a binary search tree, I understand why I can use breadth-first and pre-order traversal to list the entries of the tree in such a way as to reconstruct the tree in the order in which its ...
6
votes
1answer
343 views

Is there a way you'd implement a fast tree traversal method that would support dated versioning?

I've got a catalog at work and I want to juke it up a bit because I'm tired of it being extremely slow. I'd like to support the modified preorder tree traversal storage method for the category tree of ...
10
votes
2answers
1k views

What's the simplest example out there to explain the difference between Parse Trees and Abstract Syntax Trees?

To my understanding, a parser creates a parse tree, and then discards it thereafter. However, it can also pop out an abstract syntax tree, which the compiler supposedly makes use of. I'm under the ...
0
votes
2answers
352 views

Adding ordered nodes to tree in arbitrary order

I have a database of nodes. Each node can have exactly one parent, but any number of children. Some nodes may be stored with no parent, but at run time, I can create a default "root" node to be the ...
5
votes
1answer
786 views

How to find Sub-trees in non-binary tree

I have a non-binary tree. I want to find all "sub-trees" that are connected to root. Sub-tree is a a link group of tree nodes. every group is colored in it's own color. What would be be the ...
3
votes
3answers
253 views

Are tree structures inherently bad for mark-and-sweep garbage collector performance?

I'm implementing a bounding volume hierarchy in F#. Since it would be for a game, I want the garbage collector to be as quick and infrequent as possible. It seems though that I may have to pull some ...
2
votes
1answer
317 views

Idea of an algorithm to detect a website's navigation structure?

Currently I am in the process of developing an importer of any existing, arbitrary (static) HTML website into the upcoming release of our CMS. While the downloading the files is solved successfully, ...
6
votes
5answers
378 views

Am I overusing trees as a model or are they just very common?

I'm working on a project and I've found that I've modeled the two largest components as trees. My main uses so far are: Generically model physical containers (and sub containers, sub sub containers ...