The tag has no wiki summary.

learn more… | top users | synonyms

-2
votes
0answers
36 views

Example cases for each data structure? [closed]

I've been looking all over the Internet for a page that lists cases for when to use each abstract data type. I expect that reading through a series of both surprising and obvious uses for each type ...
2
votes
3answers
109 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
80 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
38 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
115 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
71 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
84 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 ...
0
votes
0answers
54 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
218 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
279 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
90 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
120 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
116 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
241 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
120 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
51 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
50 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
554 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
2answers
305 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
351 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
82 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
88 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
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 ...
5
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
711 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
366 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
287 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
949 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
768 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
141 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
522 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
353 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
938 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
388 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
295 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
585 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
438 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
394 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 ...