Questions tagged [trees]

Questions about a special kind of graphs, namely connected and cycle-free ones.

554 questions
62 views

Selecting a subtree in an array representation of a binary tree

Consider a zero-indexed array representation of a binary tree (as in a binary heap), where 0 is the root The left child of i is ...
14 views

How to determine R-Tree MBR Nodes?

I understand the concept of an R-Tree and how it is used to spatially index and store geometric objects such as polygons and points, but I am not sure how to construct it by choosing MBRs that group ...
330 views

Is there a name and efficient algorithm for this Tree Traversal method?

Consider a tree structured task list where intermediate nodes define sub-groupings of tasks but are not tasks themselves, and the leaves represent the actual tasks. I want to traverse this type of ...
33 views

Generate a random tree population

Given a unbalanced k-ary tree base (with internal nodes that represent operators and leafs representing values) from the space of all unbalanced k-ary trees ...
1k views

68 views

Splay trees: why are depths of nodes on the access path halved?

The original paper describing splay trees Self-Adjusting Binary Search Trees by Sleator and Tarjan claims that: Splaying not only moves x to the root, but roughly halves the depth of every node ...
70 views

What is a not-well-founded cotree?

I'm reading the paper "Dual of substitution is Redecoration". And I'm struggling with understanding the usage of the word "not-well-founded cotrees". what is a cotree compared to a tree ? I suspect ...
14 views

Name for number of branches of a tree

I'm working with trees in a project where I need to test various tree-making algorithms and their outcome. A frequent quantity I look for is the number of branches of a tree. Is there a commonly used ...
223 views

$O(n\log n)$- algorithm for finding tree root

All numbers from $1$ to $n = 2^k-1$ are written in unknown way in a full binary tree of height $k$. We say that a number $t$ lies between $i$ and $j$ if after removing $t$ from the tree we obtain ...
24 views

The optimal way to find leaves in a weighted full binary tree

Let T be a full binary weighted tree. For a node v in T, the cost of going right is a i.e w(v, v.right) = a while w(v, v.left) = b How do I find optimal paths to all leaves from the root. I don't ...
58 views

E-Unification: “Goal seeking” pattern matching between directed trees

Preamble Suppose we have some symbols x, y, ... and wildcards (ξ), ...
692 views

Optimal data structure for sorted list

Most of the resources on the web I have encountered say that "sorted arrays and other sorted data structures are implemented with binary search trees (BSTs)". Even though B-trees are a generalization ...
205 views

How does a Trie work?

Specifically, many say that to speed up an HTTP routing code going from regex to a Trie is the solution. Sometimes also a compressed Trie or Radix Tree. The problem though is that after reading ...
36 views

Choose minimum subset of edges in tree that connects all important nodes

Let's say we have given weighted tree of size $n$ and list of important nodes in the tree $k$. We want to choose subset of edges of the tree such that: For each two important nodes at least one edge ...
114 views

A way to convert a binary tree into a grid

Wondering if there is a way to convert a binary tree into a grid such as this: ...
88 views

Auto-generating a class hierarchy/inheritance tree from a data set of objects with properties

What is an algorithm that will take as an input a flat list of objects with a varying degree of overlapping properties: ...
389 views

How a range query works on a simple B+tree

Given a B+tree indexing scheme, wondering how a database actually goes and finds records matching a range query such as the following: ...
310 views

Infix search in millions of strings

Let's say we have millions of strings (each of them < 100 characters): alpha allo blah hello world orlando ... I know how a binary search tree or a trie can ...
107 views

Data structure for a single elimination tournament and its implementation

I want to implement a tournament managing software , something like challonge(https://challonge.com/) and am currently stuck at the data structure to be used. I read up on tournament trees and a ...
73 views

Transform 2D range query matrix into segment tree to make memory usage lower

Let's say we have given matrix $N\cdot N$, with zeros and ones only at $P$ position at it. We want to implement queries $q(x_1, y_1, x_2, y_2)$ which will return the number of ones in the sub-...
25 views

In what case would bi-directional BFS have the same asymptotic run time as a regular BFS?

I'm not quite sure when they would have the same asymptotic running time. Would it be if the graph was each node connected to one other node in a line? I know that for a bi-directional BFS to have a ...
129 views

Is there a name for this tree traversal?

This came when I was looking at block scoping in compiler design. { A { B } { C {D} {E} } } For the above pseudo code, the order in which the scope ...
34 views

Do we need visited flags when applying BFS on a tree?

Do we need visited boolean flags when applying BFS on a tree ? ...
79 views

Why does the ouput of an NC0 circuit depend on only a constant number of input bits?

I understand that NC0 circuits have a constant depth and bounded gate fan-in of two, but I'm struggling how to understand why the language is in NC0 iff there is a constant c such that for every n, ...
44 views

Finding a certain subset of a weighted tree

Given a rooted tree with $n$ weighted nodes and a number $1\leq k\leq n/2$, what is an efficient algorithm for finding a subset of the nodes having $k$ elements no node being an ancestor of another ...
288 views

How to read off the set represented by a van-Emde-Boas tree?

I'm reviewing my background in Algorithms and DS design. Specifically I never went through the van Emde Boas Tree. Though I can undestand the proto-vEB with related picture. I'm struggling to ...
105 views

Algorithm to find nodes with given a distance

We have a map of a branching river without any islands (tree of confluences, see picture), there are piers on the river bank ( not necessarily on the confluences). We are given the distances between ...
32 views

Minimum edge cover with a constraint

An edge cover of a graph is a set of edges such that every vertex of the graph is incident to at least one edge of the set. I am interested in finding the minimum edge cover of a tree such that each ...
19 views

Doubt regarding deletion from a B-tree

After deleting an element from a B-tree,I could rearrange the tree in several ways,that would still complies to the rules of B-trees.But,we are supposed to follow a certain set of rules for ...
99 views

Prefix Sums in Mutable 2D Array

Suppose I have a 2D array M[n][n] of integers (in fact, binary is fine, but I doubt it matters). I am interested in repeated queries of the form: given a coordinate ...
32 views

Cross link suggestion algorithm that distributes and spans all links as fast as possible without loops

I am implementing a topic suggestion system to a website. The aim is to add links to the left panel of each topic. For example, I opened the topic named "topic1", left of the page should show 5 ...
49 views

Prove that the number of full nodes plus one is qual to the number of leaves in a nonempty binary tree

I'm trying to write an induction statement to prove a full node in a tree but I have no idea how to do that. I've always been terrible when it comes to logic. Where do I even start with this? I know ...
55 views

Complexity for find pairs with sum - BST

I have written an algorithm for find all the pairs in a BST which have a given sum. ...
In trying to design an algorithm, I needed a datastructure to implement a restricted kind of set partition refinement, where the sets $X$ to split on are subtrees. Specifically, given an arbitrary ...
For given array $A$ of size $N$, note that the array is going to be permutation of the numbers from 1 to N, each number will be there exactly once, we want to obtain data structure being able to ...