The tag has no usage guidance.

learn more… | top users | synonyms

2
votes
2answers
102 views

Can a tree be used to create a stack?

I'm aware that linked lists, sets and arrays can be used to create stacks by themselves. The theory behind it is this linked-list: In some languages, a linked-list is substitutable for an array. ...
0
votes
0answers
54 views

Decision making algorithm

I'm currently solving an optimisation problem of my own design, just to experiment and learn a little something. Here's the concept: I have a user that starts at home. The objective of this user is ...
2
votes
2answers
70 views

Retrieving an incorrectly stored tree data structure

Way back in the hazy origins of our platform it was decided that we were going to need some hierarchical data structures stored in the RDBMS. The relationships between nodes were stored via a ...
2
votes
1answer
124 views

Algorithm to get all paths in a tree

I have a tree that has n-levels. For example here I have four levels: Each node has two children (except for the last one), however everyone except for the first and last node of each row has two ...
6
votes
3answers
342 views

What would be a good approach to generate a tree of folders?

Say I have an array of strings, like this: var folders = new[] { "Foo", "Bar", "Foo\Bar" "Foo\Bar\Baz" }; And that I have an object that represents a folder - something like this: ...
1
vote
1answer
101 views

Suggestions for structuring complex json structures?

I can't find many tips for how to design complex json structures beyond the obvious tips of not trying to nest too deeply, using defined data types, etc. For example, if I have a location that needs ...
3
votes
1answer
100 views

Is this Red-Black tree insertion pseudocode from Introduction to Algorithms (CLRS) correct?

For the Red-black tree insertion fixup the book distinguishes between 6 cases, 3 of which are symmetric. The cases are (z is the node being inserted): Case 1: z's uncle is red Case 2: z's uncle is ...
1
vote
1answer
51 views

Why do we have the “running” state in behavior trees?

I'm following the paper: Towards a Unified Behavior Trees Framework for Robot Control and attempting to implement my own behavior tree. I believe that I have the correct logic working for the main ...
3
votes
1answer
94 views

Finding xor sum in a tree

I was trying to solve this problem on hackerearth where you have a tree with values on each node and you have to answer queries that ask what is the xor sum between two nodes. Also, there are updates ...
-1
votes
2answers
63 views

Abstract Syntax Tree with parent or not? [closed]

My question is as simple as the title says -- should I implement AST with parent or not? Currently I implemented it with parent -- the benefit of that approach is, that whatever I use, I can go up or ...
2
votes
1answer
82 views

MInimum tree coverage

I would like to understand what would be the optimal method of finding minimum tree coverage of tree nodes. Let me explain. I have a self-referencing structure that represents a tree, with a limited ...
2
votes
1answer
89 views

What's the name of the algorithm to balance an acyclic graph?

Algorithms class was a such a long time ago and I can't remember the name of the algorithm to balance an acyclic graph. Let's start with a graph that looks like this: 1 | 2 ...
3
votes
2answers
79 views

How can I roll-back the execution of a constructor while building a complex data structure?

I'm building a complex tree of objects. There are a total of five types, A, B, C, D, and E. There is a single instance of A, which is the root node. A has one or more Bs as children, each B has one or ...
2
votes
1answer
76 views

Bus bunching simulation code [closed]

I'm having a peculiar issue to solve. What I am supposed to implement is a bus transit simulation in which there are passengers coming at some random generated time intervals and are added into a ...
2
votes
1answer
141 views

Does a tree node have an ancestor?

Below is a rooted tree, where any node C except root has one parent P Ancestors of a node C are the nodes on path from C to root, including P,P's parent,P's grandparent, .... till root. My ...
0
votes
1answer
242 views

Implementing a Forest Data Structure in Java

Name of data structure that's tree-like with multiple root nodes I stumbled upon someone's answer to a question regarding implementing a tree that has > 2 nodes above. I just wanted to get ...
1
vote
0answers
69 views

Finding Parent Node in Directed Acyclic Graph

I've implemented a structural sharing algorithm for creating Clojure style persistent trees, but it relies on the child node knowing its own parent. function fork return new Node children: ...
3
votes
1answer
76 views

Big-O for Immutable Trees

How would you calculate the time and space complexity for a tree algorithm that creates a copy of a tree, but reuses as much of the original tree as possible? For example, A /|\ B C G /|\ D ...
3
votes
2answers
191 views

How to find the closest right neighbour in a tree?

Given a class: public class Node { public List nodes[]; public Node right; //NULL for now } What's the best way to fill the "right" element of all tree nodes? N ...
4
votes
1answer
152 views

Detecting surface faces of a huge 3D mesh/grid

I've written a module in my application that creates a mesh from existing coordinate and face data. The number of vertices in the mesh could easily exceed 10 million and the same goes for the faces. ...
4
votes
1answer
88 views

What method should I use to populate a tree as I'm consuming data that is contained within the tree?

I have a tree that consists of 5 types of nodes - V, W, X, Y, and Z. V represents the root node, and a given tree has exactly one element of type V. A V contains one or more Ws, a W contains one or ...
2
votes
1answer
100 views

Efficient algorithm for hierarchical traversing? JSON hydration, for example

I'm writing a small library that helps you hydrate JSON data into objects. Given this JSON example: { "date": "1970-01-01 00:00:00", "foobar": "baz", "user": { "name": "foobar", ...
3
votes
1answer
146 views

What is the time complexity of this program?

An algorithm is given on GeeksForGeeks.com for constructing a Binary Search Tree from its preorder traversal. They say that the time complexity for the following code is O(n^2). But in my opinion it ...
0
votes
0answers
75 views

What is the most efficient trie for comple multi-ligual data usage

Background Efficient Trie implementation for unicode strings I'm writing an app that will likely be run on systems that don't have much space or memory like my pi. Ideally my Trie would be efficient ...
2
votes
2answers
126 views

Algorithm to go from infix notation to a tree

I've been trying to figure out an algorithm to go from an infix equation to a syntax tree, like so: (1+3)*4+5 + * 5 + 4 1 3 However, I don't just want it to handle operators, I ...
2
votes
4answers
122 views

Clean Abstract Syntax Tree

I'm writing a toy compiler for fun. Basically, my problem is that I don't want to clutter the AST with stuff like debug information (symbol tokens, locations of tokens, etc) as well as data that the ...
4
votes
2answers
328 views

Is this data model a list or tree?

Using python syntax with below environment diagram, teacher taught us that there are 11 trees(orange boundary) in this diagram, including leaf. It has been taught here, lists are represented as a ...
3
votes
1answer
200 views

Finding the optimal root

I am trying to solve a quora hackathon challenge question. The question descrpition is as follows : For the purposes of this problem, suppose Quora has N questions, and question i (1≤i≤N) takes ...
1
vote
0answers
80 views

Best way to traverse data and update nodes in Mongo DB

I am using Angular Tree View in my web app. Data coming from the server is build with https://www.npmjs.com/package/mongoose-materialized getArrayTree() function. What I need is, syncing the ...
2
votes
1answer
252 views

Expandable alternative to Visitor pattern for tree traversal?

I have a tree containing various subtypes of the my base node class. I now want to traverse this tree and do something with the nodes depending on their type. The most straightforward idea is to just ...
0
votes
1answer
99 views

Graphs and minimum spanning trees?

I am having a hard time finding information on how Graphs and spanning tree's work and how to construct/structure them. The reason is that I'm using a Delaunay Triangulation algorithm within the ...
0
votes
0answers
37 views

Advice on paging tree structured data

I'm in the process of building web based a commenting system, for which the comments are rendered in a reddit / disqus style tree structure. The MySQL schema uses a string of ancestor id's, and the ...
1
vote
1answer
127 views

Decision tree (?) reduction

I need to check certain conditions (of size n) on an object and perform one of several options available (size m) based on the result. Seems to me it fits a tree. Now. The tree is quite large and I ...
0
votes
0answers
166 views

Is there a better way to retrieve a ViewModel container starting from a Model?

I'm trying to figure out a more efficient method. To start, I have a viewmodel wrapping around a model. The model itself collectively becomes a tree. We'll call each model a Fragment: public class ...
1
vote
1answer
238 views

Difference between sibling lists, left-child right-sibling binary tree and doubly-chained tree

The Wikipedia page for suffix trees descibes sibling lists as Each node has a pointer to its first child, and to the next node in the child list it is a part of. Wikipedia describes left-child ...
0
votes
1answer
113 views

Any good data structure to perform efficient lookup and modification operations about what are the shapes containing the current cursor position

I think I'm facing a pretty common issue but cannot remember which solution is the most suitable one. Let's put it that way: I can, in a, certain, given, language get some events anytime the user is ...
1
vote
2answers
253 views

Non-fixed-size Fenwick Tree implementation

I'm planning to implement a non-fixed-size Fenwick tree. That is, a Fenwick tree that allows interleaving range queries with adding/removing elements. All implementations and samples I've seen so far ...
4
votes
1answer
187 views

Is this Wikipedia pseudocode for in-order generic tree traversal correct?

Wikipedia states that the following algorithm works for any tree (not necessarily binary trees) Perform pre-order operation For each i (with i = 1 to n) do: Visit i-th, if present ...
1
vote
1answer
159 views

component-based power system for a game [closed]

My issue is that I've been trying to implement a power/electrical system for a while now. I'm using Unreal Engine 4 with C++ but that's not really relevant. I'm trying to implement some sort of ...
0
votes
1answer
694 views

How to determine whether two trees (not necessarily binary) are isomorphic

Two ordered trees T' and T'' are said to be isomorphic if one of the following holds: ◦ both T' and T'' consist of a single node ◦ both T' and T'' have the same number k of subtrees, and the ith ...
0
votes
1answer
168 views

Injectable, Poppable Stack

Background A project involves converting a relational expression map (rxm) to an XML/SQL statement. The map resembles: root > people, # "root" keyword starts the document ...
2
votes
1answer
182 views

Why are heuristics a disadvantage for decidable problems?

I'm reading Introduction to Artificial Intelligence by Ertel. This line has me stumped from the textbook (page 102): For decidable problems such as the 8-puzzle this means that the whole search ...
6
votes
4answers
737 views

Most efficient way to generate all descendents of all nodes in a tree

I'm looking for the most efficient algorithm to take a tree (stored as either a list of edges; OR as a list of mappings from parent node to a list of child nodes); and produce, for EVERY node, a list ...
2
votes
1answer
211 views

How to randomly get or find a sub-tree (include root node) from a given tree that contains n leaf-nodes

I have a non-binary tree. I want to randomly find a "sub-trees" that are connected from root to leaf which must have at least n leaf-nodes (leaf-nodes of sub-tree must be leaf-nodes of given tree). ...
1
vote
1answer
154 views

Where to put data for tree structure which every node requires?

I have a quad-tree structure where each node has some of its own data, but there is also data which applies to the tree as a whole. I'll explain my current solution and I would appreciate feedback on ...
1
vote
0answers
201 views

Algorithm for sport tournament bracket tree

I would like to develop a library that: receive n players in input response with the tournaments brackets in output. I would ask you what kind of algorithm I have to use to choose the correct tree ...
3
votes
0answers
164 views

Walk Tree vs Zhang and Sasha Algorithms

I need some help understanding how two tree comparing algorithms differ. I am working with Microsoft's XmlDiffPatch (http://msdn.microsoft.com/en-us/library/aa302294.aspx) which compares two xmls. The ...
1
vote
1answer
477 views

how to traverse towards child node from parent node in n-ary tree? [closed]

In an n-ary tree... Given a reference to some child node And a reference to a distant parent of the referenced child node Is there a method that a parent node can use to figure out which of its ...
4
votes
1answer
363 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 ...
4
votes
1answer
100 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 ...