Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [trees]

A tree is a hierarchical data structure in which every node is accessed via a unique path that starts at a unique root node. Trees are often used for searching data and optimizing an ordered access to nodes. In the graph theory, a tree is a graph of connect nodes without cycles. Attention: use tag 'trie' for the tree like data structure aiming at string matching (prefix/suffix)

4
votes
2answers
119 views

How can one interpret an Abstract Syntax Tree without recursion?

I am busy building an interpreter for a Rebol-like language. I have previously built a Lisp interpreter where I used recursion, but now I just want to use a stack and not rely on the recursion ...
0
votes
1answer
35 views

How a Merkle tree can work with Graph data, or a better data structure

I am looking at blockchain and trying to see how Merkle trees (or perhaps Merkle DAGs) can fit to a graph data structure with circular references. For example, say I have this data model: var ...
1
vote
2answers
92 views

How to parse DSL file to HTML?

There's DSL format for creating and distributing dictionaries. Every dictionary article in such formats looks like this: algorithm [m0][b]al·go·rithm[/b] {{id=000001018}} [c rosybrown]\[[/c][c ...
4
votes
2answers
232 views

Game Playing AI - Strategy to overcome the transposition table taking up too much memory?

I've made an engine that plays Connect Four using the standard search algorithms (minimax, alpha-beta pruning, iterative deepening, etc). I've implemented a transposition table so that the engine can ...
2
votes
1answer
82 views

trie iteration should include root?

I'm working on a trie data structure. My simple, initial understanding: trie data structures require a fixed root node. This node cannot be deleted. When iterating through all nodes in a trie (in ...
0
votes
0answers
136 views

How to structure a bitwise trie to do a range query

I am wondering about how to perform a range query on a bitwise trie. So say I have a trie like this. ▲ Black (any shape) is 0. △ White (any shape) is 1. ■ Black square means there is no value ...
1
vote
0answers
55 views

Decision tree for storing subscription info

I have a system in which user creates an entity. Now this entity has attributes which are dependent on many external systems. We have all those pipelines in backend which updates these entities when ...
0
votes
3answers
98 views

Updating nested entities with constraints without getting spaghettimadness

I have an endpoint "import" that is supposed to accept an entity. This entity can contain several sub-entities with yet again some sub-entities. Since this is an "import" endpoint, some of the entites ...
0
votes
1answer
64 views

Limitations of Tries in Comparison to B-Trees for a Database

I am wondering about how range queries work, and the standard solution is to use B+trees. However, I am a fan of tries as a general data structure and would like to know if they (or variations of them)...
2
votes
1answer
82 views

Algorithm: Binary Search / Tree / Partitioning on unsortable data?

First, this question is not really about binary search as I neither have sorted data, nor any sortable data at all. :-) W.r.t the "unsortable" claim see below; but I think the title term "unsortable"...
0
votes
0answers
42 views

implementing data structure that consists of pair-diff(s,d)

i am having trouble and would really appreciate your help, especially with pair-diff(S,d) i am trying to implement a data structure S in given times: Insert(S,k) - inserting k into S O(logn) Delete(...
0
votes
1answer
234 views

AST design: Call is both expression and statement?

I'm designing the AST for a compiler and found that I don't actually know how to represent the Call node. Currently, the relevant part of the AST looks like this (where the arrows denote inheritance):...
1
vote
1answer
32 views

Modified graph traversal

This question is most easy to describe as a modification of that my question. Suppose that question is solved as the following Python class: class Traversal(object): # ... def next(self): # ...
3
votes
3answers
213 views

Optimal way of storing sorted tree in memory

Wondering what the general structure is for storing a tree in memory most efficiently (for access operation, and space). For the access operation, it should take advantage of contiguous memory (...
2
votes
1answer
330 views

Parallel processing a Tree on GPU

I have seen a few papers on parallel/GPU processing of trees, but after briefly looking through them I wasn't able to grasp what they did. The closest to a helpful explanation was found in ...
0
votes
1answer
69 views

Efficiently determining available options based on prior selections

I'm looking for a known design pattern or algorithm that can be used to effectively determine a set of available options to be presented to a user based on previous decisions. An extremely simple ...
0
votes
0answers
34 views

Can data in a rooted tree be processed in parallel?

I have data that is structured like the following: users: id | name | parent_id 1 | Bob | NULL 2 | Jan | 1 3 | Mat | 2 4 | Irene | 2 5 | Ellie | 2 6 | Laura | 5 7 | Uma | 6 ...
3
votes
3answers
155 views

What strategy should I follow to draw a forest of trees represented by an array

I have an array of integers representing connectivity of nodes.Consider the following states of the array after each time it's changed: 0|1|2|3|4|5|6|7|8|9 => Root of each node is itself 0|1|2|3|3|5|...
0
votes
2answers
129 views

Breadth-first traversal with some edges preferred

Let we have a (finite or infinite) directed graph and a start vertex. For each vertex we have the set of edges from this vertex totally ordered to specify the traversal order. Let we also have a set P ...
3
votes
2answers
3k views

Is there a tree data structure with multiple root nodes?

I've read this post Name of data structure that's tree-like with multiple root nodes. What I'm asking for is not a forest. I would give you a simple example that easily depicts my case. You ...
0
votes
0answers
191 views

Data structure to implement a fake filesystem with required complexity functions

I have to create a fake filesystem that basically stores the path of each element in the structure. This filesystem has to run on the primary memory so I do not have to write anything to the hard ...
0
votes
1answer
212 views

Designing syntax tree derived node classes

Let's say I have an abstract Node class and BinaryOperation class derived from Node and three classes IntegerConstant, RealConstant and CharacterConstant also derived from Node. The general design ...
6
votes
6answers
2k views

How to represent a long if-else tree in a concise manner

Long story short, I've inherited a Java piece of code made of methods like this one: @Override public Action decide() { if (equalz(in.a, "LOC")) {//10 if(( //20 equalz(...
0
votes
0answers
70 views

Monte Carlo Tree Search in connect 5 tree design

I'm trying to create a mcts AI for connect 5 algorithm. However, I'm confused on designing the tree. Here is a quick description of the algorithm: The initial state, S0 is the board state where the ...
1
vote
1answer
83 views

How to build an optimal tree given items costs and edge costs?

Given: a list of 'leaves' that each have a cost, the cost of creating an 'edge' The constraint that a constructed tree node can at most have two children. We now want to find the tree with the ...
4
votes
1answer
601 views

Visitor pattern. Operating on the nodes of a tree

I am working with jQuery like elements from the cheerio library to manipulate SVG images. These objects represent XML nodes and have a hierarchical internal structure. I am writing a function (in ...
1
vote
1answer
943 views

How do I represent a recursive process down a tree in a sequence diagramm?

I'm working on a sequence diagram for a layered system that has a tree hierarchy. Now I have a process that works itself recursively down the tree. Meaning calling the same function on a child object. ...
0
votes
1answer
50 views

When should an expression tree hold pointers and when should it hold values of subexpressions?

I was thinking it should hold pointers: struct Expr { string sym; Expr*[] sub; this(self, string sym) { this.sym = sym; } @property auto dup() const { auto e = ...
4
votes
3answers
179 views

How do I manage dependant values without running the same computation twice?

I am working on an application that is essentially a calculator, not the handheld calculator but more of a spreadsheet. It will take many inputs across different views and show the outputs all over ...
1
vote
2answers
305 views

Rooted tree - Representation & Performance

Representation 1 - Multi walk tree typedef struct multiWalkTreeNode{ struct multiWalkTreeNode * parent; void *item; struct multiWalkTreeNode **childPointer; }Node; typedef struct multiWalkTree{...
2
votes
1answer
466 views

Advantage of maintaining parent pointer - LCRS tree

In the below tree, typedef struct lcrsNode{ void *item; struct lcrsNode *parent; struct lcrsNode *firstChild; struct lcrsNode *nextSibling; }lcrsNode; typedef struct Tree{ lcrsNode *...
1
vote
0answers
53 views

Hierarchical data structure: pull requests + pull request reviews + pull request review comments

GitHub has: pull requests pull request reviews pull request review comments BitBucket has only: pull requests pull request comments So there are three kinds of objects. I write code ...
3
votes
4answers
188 views

Hierarchical structure that needs to enforce availability

The project I am working on has deep parent/child relationships that needs to enforce availability. Imagine we are a large Worldwide Electronic Seller (Best Buy) and selling mobile phones We have ...
2
votes
0answers
192 views

Algorithm for calculating tree layout with incremental updates

I am looking for an algorithm that calculates positions of nodes in a non-binary tree. The positions in that layout will be used for drawing the tree. I am using the tree in a mind map application. ...
0
votes
1answer
296 views

Why the search time for TreeSet is O(nlogn)?

In my naive opinion it should be O(n) in worst case since Tree could get spindly and unbalanced.
2
votes
3answers
194 views

Word to specify that a tree has arbitrary numbers of branches, as opposed to a binary tree

What do you call a tree where each node has an arbitrary number of children (i.e. not necessarily 2)? I'm trying to research some algorithms online, and Google keeps returning results for binary ...
-1
votes
1answer
66 views

How to fit k-length arrays to number of bigger arrays?

I have n number of one-dimensional arrays similar to: [0,0,0,0,0,1,1,1,0,0,1,1,...] 0's and 1's indicating occupation. And k number of smaller arrays similar to: [2,2,2], [2,2], [2], [2,2,2,2] ...
0
votes
1answer
431 views

Extract All Possible Paths from Expression-Tree and evaluate them to hold TRUE

This is a follow-up question of my previous one: https://stackoverflow.com/questions/38421950/better-class-structure-for-logical-expression-parsing-and-evaluation Brief introduction: rules as ...
6
votes
1answer
139 views

How to describe a set of paths in a graph with as few nodes as possible?

I have modeled a problem as a graph that consists of many trees. Some of the nodes in the graph may belong to more than one tree. I am trying to describe a subset of paths in the graph with as few ...
8
votes
1answer
495 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. ...
-6
votes
1answer
661 views

BST to AVL in O(n) [closed]

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
127 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 ...
2
votes
1answer
576 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 ...
4
votes
2answers
9k 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. ...
-1
votes
0answers
391 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
3answers
143 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
3k 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
413 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: ...
3
votes
1answer
542 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 ...
6
votes
1answer
2k 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 ...