The tag has no wiki summary.

learn more… | top users | synonyms

3
votes
0answers
49 views

Data structures and algorithms for a directed rooted tree with inherited properties?

I need to represent a directed rooted tree in memory. The caveat is, that nodes have properties. And those properties are inherited (but not 100%) by the child nodes, recursively. What would be a ...
2
votes
0answers
37 views

Which data structures and algorithms should I consider for a directed rooted tree that has high churn?

I need to represent a directed rooted tree in memory. What would be a good data structure and algorithms for performing main actions, given the particulars listed below? Size: ~40,000 nodes. But ...
0
votes
1answer
39 views

OpenLDAP as tree database [closed]

I have some data which is hierarchical in nature (actually a forest) and rather big in size, although not enormous, in the order of tens of GB, or billions of nodes. This data is not going to change, ...
2
votes
3answers
126 views

How exactly is an Abstract Syntax Tree created?

I think I understand the goal of an AST, and I've built a couple of tree structures before, but never an AST. I'm mostly confused because the nodes are text and not number, so I can't think of a nice ...
1
vote
1answer
95 views

Performing a Depth First Search iteratively using async/parallel processing?

Here is a method that does a DFS search and returns a list of all items given a top level item id. How could I modify this to take advantage of parallel processing? Currently, the call to get the sub ...
0
votes
0answers
39 views

Find common ancestor

Given X number of leaves (the ringed leaves in the picture) in an unbalanced tree with depth aroun 100-1000 and total number of nodes around 15 000 000. I'm looking for the first common ancestor for ...
1
vote
0answers
117 views

Menu building pattern

I'm having troubles getting my head around the active-state handling of a menu when the menu isn't used for routing. I come from Drupal where the menu system handles the routing as well. so setting ...
1
vote
3answers
73 views

Handling leaves in tree-based menus

Tl;Dr Given a language with no polymorphism how to you elegantly modify the behavior of a leaf in a tree data structure. Context I'm programming an application in C for a microcontroller and I'm ...
2
votes
2answers
99 views

Quadtree with duplicates

I'm implementing a quadtree. For those who don't know this data strucutre, I am including the following small description: A Quadtree is a data structure and is in the Euclidean plane what an ...
1
vote
0answers
62 views

Most efficient way to rebuild a tree structure from data

Have a question on recursively populating JsTree using the .NET wrapper available via NuGet. Any help would be greatly appreciated. the .NET class JsTree3Node has a property named Children which ...
0
votes
2answers
302 views

Exercise 3.6: Skiena Algorithm Design Manual

I am preparing for interview and try to solve the exercise problems of the book. 3-6. [5] Describe how to modify any balanced tree data structure such that search, insert, delete, minimum, and ...
0
votes
1answer
414 views

Tree View Children condition indicator on topmost un-expanded parent

I am using a tree view in c# and i am creating custom icons for the nodes. Let say this is my hierarchy with a node that satisfies a certain condition: Root1 |_Ax |_Bx1 |_Bx2 |_Cx1 ...
2
votes
1answer
97 views

Maze generation given intersection tree

Background Information: I'm building a 2D maze generator. I have tried Prim's algorithm, Wilson's algorithm, and a recursive backtracker algorithm for generating my maze, however was not satisfied ...
0
votes
1answer
148 views

What happens to equal elements when inserting into a binary search tree?

Most BST examples show a sample of a BST with unique values; mainly to demonstrate the order of values. e.g. values in the left subtree are smaller than the root, and values in the right subtree are ...
2
votes
2answers
121 views

Segregating interfaces/concerns to a tree

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
244 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
143 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
54 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
53 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?
1
vote
2answers
628 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 ...
6
votes
4answers
3k 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
53 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
3answers
366 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
355 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
87 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 ...
3
votes
2answers
120 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
92 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
115 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
75 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
97 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
1k 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
861 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
4k 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
393 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
288 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
111 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
1k 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?
4
votes
2answers
785 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
142 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
2k 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
542 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 ...
5
votes
2answers
358 views

Web Crawler for Learning Topics on Wikipedia [closed]

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
94 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
1k 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
972 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
396 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
300 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
358 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
591 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
450 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 ...