The tag has no usage guidance.

learn more… | top users | synonyms

4
votes
1answer
53 views

Perform crossover operation on AST in genetic programming

So in general when you perform a crossover in GA, you directly flip a random section in the "genome", with the corresponding section in the other parent, and mutate it based on the mutation rate. ...
-4
votes
1answer
71 views

BST to AVL in O(n)

I found in different places on the internet how to turn a Binary Search Tree into an AVL tree in O(nlog(n)). I was wondering how can this be done in O(n) (as the worst case limit). It kinda seems ...
2
votes
1answer
53 views

Matrix multiplication range queries

I have a huge list of matrix i.e A = {M0, M1, M2 .. Mn}. I have a task to find the product of all the matrices in a given range {x,y} i.e Mx * Mx+1 * Mx+2 ... * My. I would like to know if there is ...
1
vote
1answer
48 views

Keeping track of the number of nodes in the subtree in black and red trees

I was wondering, if I have a black and red tree and I want to keep track of the number of nodes in the subtree, what is the most effective way to do so? I mean how do I work with these values while ...
3
votes
2answers
215 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
78 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
76 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 ...
1
vote
1answer
177 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 ...
7
votes
3answers
356 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: ...
2
votes
1answer
134 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 ...
2
votes
1answer
120 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
53 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
108 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
71 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 ...
1
vote
1answer
92 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
91 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
82 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
88 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
215 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
313 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
82 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
79 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
196 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
179 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
112 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
132 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
158 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
78 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
144 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
139 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
334 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
219 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
99 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
329 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
122 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
41 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 ...
0
votes
1answer
136 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
184 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
295 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
124 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
264 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
206 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
162 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
871 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
169 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
209 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 ...
5
votes
4answers
1k 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
230 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
176 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
216 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 ...