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)

Filter by
Sorted by
Tagged with
0 votes
0 answers
53 views

How to group together common allowed descendants of a vertex in a tree data data structure?

I created an abstract class to represent a vertex in a tree structure. Later, a requirement was introduced where certain types of vertices are not allowed as descendants of certain other vertices. So ...
Cave Johnson's user avatar
0 votes
4 answers
165 views

implementing an n-ary tree with a single link node

Assume I have a set of nodes of an n-ary tree, packed in a dense array in depth-first order. This tree (I'm showing links between each parent and its list of children): [A] | [B]--[E]--[F] | ...
fearless_fool's user avatar
0 votes
1 answer
156 views

Trie data for searches in time ranges

I am developing an API responsible for returning the distinct searches made on a service given a date prefix. Example data: 2015-08-01 00:00:18 %22http%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%...
alves's user avatar
  • 101
0 votes
0 answers
146 views

Is there a known algorithm for reducing a tree based on a list of its leaves?

For a given, tree-like data structure: - Alan - Barbara - Charlie - Cecil - Brian - Chris - Candice - Cohen - Boromir - Corcoran -...
StuperUser's user avatar
  • 6,123
-1 votes
1 answer
257 views

Building a function call tree at runtime

Edit #1 I believe that I misrepresented my intent when writing this question by focusing too much on the issues that have arisen from our misuse/misunderstanding of locks. I am making this edit to try ...
notphilphil's user avatar
4 votes
1 answer
2k views

Understanding usage of quadtree to store location data

I was reading this article, which talks about storing location-based information. The author says that while Latitude and Longitude info for the locations can be stored in a SQL database, retrieving ...
Ufder's user avatar
  • 209
2 votes
2 answers
246 views

What is the best practice for hierarchical container - item relationship in a SQL database?

I am in the process of designing a database organizing real world items in different storage locations. One main principle is that items can contain other items. So the relevant table is: An "...
gaugau's user avatar
  • 301
0 votes
0 answers
56 views

Sentinel nodes in a 2-3 tree

I want to implement a 2-3 tree in C# language, where every leaf has a unique key. The keys are from a given class that implements the IComparable interface (the specific class is unknown, and it's ...
Daniel's user avatar
  • 155
7 votes
2 answers
625 views

some misunderstanding in concept of Huffman algorithm

What is difference between Average length of codes and Average length of codewords in Huffman Algorithm? is both the same meaning? I get stuck in some facts: I see a fact that marked as False: for a ...
Emma Nic.'s user avatar
  • 183
0 votes
2 answers
551 views

Implementing C++ n-ary tree with Boost Graph Library

I would like to have a relatively small and simple tree in C++. Each node would contain an integer. The tree should be traversable both ways. I know it can be done with tree.hh by Kasper Peeters, but ...
Igor's user avatar
  • 1
-1 votes
1 answer
68 views

Efficiently keep different data structures synchronised - tree, list of objects

Problem description I have a pet project to translate TEI XML to standoff JSON and back: https://github.com/standoff-nlp/standoffconverter and I am currently thinking about a rewrite/restructuring. ...
Milla Well's user avatar
0 votes
1 answer
157 views

How to apply Graphs/Trees/BFS/DFS concepts to Lists

I have been doing problems on LeetCode recently, and keep getting stuck on some graph or tree problems. I understand the underlying concepts of Graphs, Trees, and different methods of traversal just ...
Brian C's user avatar
  • 137
-2 votes
1 answer
575 views

Optimal Data Structure for Searching though String

I am current developing a karaoke app in JavaFX, I need advise on the most optimal data structure storing a huge list of songs (library). I am inclined to use Binary Search Trees due to its Big O ...
Lavesh Deepak Panjwani's user avatar
0 votes
3 answers
283 views

How to implement a chain of events on a tree's CRUD operations?

I am working on a project in which I have a tree with 4 layers and the hierarchy is like this. Customer -> Site -> Location -> Guardroom In DB each entity has its own table and the child ...
Ricardo Duran's user avatar
2 votes
3 answers
169 views

In a tree, what's the standard term for predicate "ancestor of or identical to"?

In a tree structure, is there a standard term (in software engineering industry practice, Computer Science or Mathematics), for the predicate f(x, y) defined in human language as "x is an ancestor of ...
Will's user avatar
  • 712
0 votes
1 answer
247 views

Hashset vs Treeset

I've always loved trees, that nice O(n*log(n)) and the tidiness of them. However, every software engineer I've ever known has asked me pointedly why I would use a TreeSet. From a CS background, I don'...
César Justiniano 's user avatar
1 vote
1 answer
85 views

Converting binary tree into doubly linked circular list

I am a beginner in computer science and have been asked to write a program to convert a binary tree into a circular linked list (order of the nodes in list are in inorder traversal of the tree). I ...
bobthebuilder's user avatar
2 votes
2 answers
379 views

Tree data structure where children can only be added based on their type

I have a tree data structure where each node has a name, an id, a type and a number of children. Additionally each node has properties based on its type. Thereby each node with type A should only ...
Florian Winter's user avatar
0 votes
1 answer
69 views

Parsing tree with many node types

I have a tree data structure where each node describes how to use its child nodes, and this tree is stored in a standard data format - XML for now. However, there are a large number of different kinds ...
GraphicsMuncher's user avatar
0 votes
1 answer
240 views

Why do so few languages provide tree or graph types in their core? [closed]

The more CS I read the more I encounter trees, heaps and graphs. All languages seem to incorporate linear data types like lists and arrays and most have some compound data type like objects or structs ...
Roger Heathcote's user avatar
0 votes
1 answer
510 views

Which tree or graph structure to solve this problem?

I have the following interface, it defines a loadable resource that depends on other resources that should be loaded first so it can load itself: It does its job, the Find method allowing to search ...
aybe's user avatar
  • 765
0 votes
1 answer
85 views

How to associate tree nodes with other objects before they have unique identifiers

I've been thinking about a simple software design problem. Imagine I am writing a web application to edit a tree of objects. Each node of this tree has an ID property that is filled in when the node ...
Joshua Schroijen's user avatar
5 votes
1 answer
929 views

What do I not understand about Alpha-Beta-Pruning in Chess?

I'm trying to write a chess engine, Min-Maxing works. Now I wanted to implement Alpha-Beta-Pruning, but despite reading about it and watching videos, I must have a severe misunderstanding somewhere. ...
Robert Tausig's user avatar
7 votes
2 answers
2k 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 ...
mydoghasworms's user avatar
2 votes
1 answer
373 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 ...
user10869858's user avatar
1 vote
3 answers
679 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 ...
Anatoly's user avatar
  • 264
5 votes
2 answers
490 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 ...
Inertial Ignorance's user avatar
2 votes
1 answer
288 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 ...
Brannon's user avatar
  • 371
1 vote
0 answers
74 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 ...
Renjith's user avatar
  • 123
0 votes
3 answers
331 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 ...
abydal's user avatar
  • 119
0 votes
1 answer
676 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)...
Lance's user avatar
  • 2,587
2 votes
1 answer
351 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"...
Martin Ba's user avatar
  • 7,608
0 votes
1 answer
1k 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):...
Straivers's user avatar
  • 103
1 vote
1 answer
53 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): # ...
porton's user avatar
  • 762
4 votes
3 answers
3k 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 (...
Lance's user avatar
  • 2,587
4 votes
3 answers
2k 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 ...
Lance's user avatar
  • 2,587
1 vote
1 answer
72 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 ...
Kyle B.'s user avatar
  • 782
0 votes
0 answers
39 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 ...
Noah Goodrich's user avatar
3 votes
3 answers
552 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|...
Mikayil Abdullayev's user avatar
0 votes
2 answers
246 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 ...
porton's user avatar
  • 762
7 votes
2 answers
17k 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 ...
Vivek's user avatar
  • 189
0 votes
1 answer
284 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 ...
107MP's user avatar
  • 46
7 votes
6 answers
6k 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(...
Luigi Cortese's user avatar
1 vote
1 answer
269 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 ...
Qqwy's user avatar
  • 4,789
5 votes
1 answer
854 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 ...
AdamW's user avatar
  • 69
2 votes
1 answer
3k 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. ...
Herr Derb's user avatar
  • 429
0 votes
1 answer
54 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 = ...
Daniel Donnelly's user avatar
4 votes
3 answers
223 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 ...
Matias Faure's user avatar
1 vote
2 answers
451 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{...
overexchange's user avatar
  • 2,255
2 votes
1 answer
921 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 *...
overexchange's user avatar
  • 2,255