Questions tagged [binary-trees]
a rooted tree in which each node has no more than two children
571 questions
0
votes
0
answers
33
views
What does two-shingle mean in binary trees?
I'm reading this paper (Tactic Learning and Proving for the Coq Proof Assistant written by Blaauwbroek et al). In section 3 (Proof Recording) it mentions one-shingles and two-shingles :
After ...
- 11
0
votes
1
answer
75
views
Counting Number of Complete Binary Trees with n Nodes
I know that the number of different complete binary tree structures (unlabeled) for n nodes is basically 1, because the structure is fixed.
Now I am trying to find the number of labeled complete ...
- 91
1
vote
1
answer
165
views
Space complexity of tournament tree method for second maximum element
Given an array of unique elements of size $n$, the goal is to find the second maximum element using tournament tree method. The model of computation is RAM model.
Algorithm: The idea to pair the ...
- 163
0
votes
1
answer
58
views
Can red-black tree augmentations depend on other augmentations and still be maintainable in O(logn)?
by "augmentation" i mean adding an additional field to each node.
All sources i found say something that falls into one of two categories:
"A field f in a red-black tree can be ...
- 3
0
votes
0
answers
29
views
Unordered Variant of "Minimum Cost Tree From Leaf Values"
This problem is based on https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/description/ :
Given an array arr of positive integers, consider all binary trees
such that:
Each node has ...
- 1
0
votes
0
answers
36
views
Is a doubly-ended array-based priority queue (DEAP) uniquely determined for a given data set?
I've been working with the doubly-ended array-based priority queue (DEAP) data structure and this problem has been giving me a pain in the neck. I want to know if the DEAP for a given data set is ...
- 11
1
vote
1
answer
113
views
Explain why the condition "NIL need to be black" exists in RED-BLACK tree definition
I know there's another question asking the same in this website, but answers to that question was not clear; it did not help me.
In this wikipedia page, the 2nd property says "All NIL nodes are ...
- 113
1
vote
1
answer
138
views
How can I construct a threaded binary tree with post-order threads?
I want to construct a threaded binary tree consisting of nine nodes A, B, C, D, E, F, G, H, and I with post-order threads. Each node has five fields, which are LeftThread (true or false), LeftChild (...
- 11
1
vote
0
answers
137
views
Prefix-free binary codes with costs
I came across the following problem:
We would like to generate n prefix-free binary codes such that we pay 4 units for each 1-...
- 119
0
votes
0
answers
66
views
Is there a definition for tree rotation?
I might be asking this question because I lack the basic knowledge of rotations. If that is the case, could you suggest any resources for learning it. But I don't think that I am. Every source that I ...
- 101
1
vote
3
answers
109
views
Is this a valid AVL tree?
node 5 is the root of the tree and its left child has height 2 while right child has height 1. the difference between its children is <= 1.
other than the difference between children, does a valid ...
- 101
1
vote
0
answers
65
views
How can a ball tree improve the efficiency of finding nearest neighbors when it involves finding least-near neighbors?
The motivation for k-d trees and ball trees is that k-nearest neighbors involves eliciting the distances between a particular data point and every other data point, which becomes inefficient as the ...
- 111
3
votes
2
answers
991
views
Number of leaves in complete binary tree
I got confused a bit about definitions and from reading in the different forums, does both complete binary tree (last level is not full) and perfect binary tree, number of leaves are ⌈n/2⌉ for a tree ...
- 31
2
votes
1
answer
126
views
A decision tree proof for the lower bounds worst case of an algorithm that k-nearly sorts an Array
Let says you want to k-sort an array A with a comparison based algorithm.
To be k-sorted, each individual item in the array A can be at most k positions away from it's actual correct position when ...
- 21
0
votes
0
answers
86
views
Can a binary tree be generated from Union-Find using union-by-rank?
I'm trying to determine if the following claims are true or false:
Claim 1
When disjoint Union-Find is implemented using up-trees and union-by-rank, and initially
there was a set of 5 single nodes. ...
- 341