New answers tagged trees
1
vote
Find a string between two groups A,B that have an amount of smaller strings in A as it has larger strings in B
Your idea to use a trie is good. I think that what might do the trick is only to store additionnal information at each node: the number of strings of $A$ and of $B$ contained in the corresponding ...
0
votes
Inorder Traversal of the Ternary Tree
A tree is a finite set of one or more nodes such that there is one specially designated node called the root node of the tree, and the remaining nodes are partitioned into trees $T_1,\ldots,T_k$ (...
2
votes
I think I have discovered a new sorting algorithm using binary search tree
Nice work, but not useful because
trees are not really sorted (in the sense of a sorted array) as the nodes may be stored non-contiguously in memory, and you need to follow the links;
any BST is ...
2
votes
Accepted
Proving that the number of leaves in a tree >= number of unmatched vertices
Prove it by induction.
It is true for trees with |V|<=3.
Suppose that it is true for trees with |V|=n-1 and we want to prove it for a tree T with |V|=n.
If there exist a leaf v which is unmatched ...
5
votes
An α-good tree with n nodes has height O(log n)
First, note that if $T$ is an $\alpha$-good tree, then for any node $x$ with children $y$ and $z$, without loss of generality, $|y| \leqslant |z| <\frac{1+\alpha}2 |x|$.
Now consider $h_n$ the ...
6
votes
Accepted
An α-good tree with n nodes has height O(log n)
$$2|y| = (|y|-|z|) + (|y|+|z|)\le \alpha |x| + |x| - 1.$$
So, $|x| \ge \frac2{1+\alpha}|y|$.
Since $y$ is an arbitrary child of $x$, if node $x$ is of height $k$, $|x| \ge \left(\frac2{1+\alpha}\right)...
2
votes
Accepted
Decision tree for searching element in sorted-array
You haven't really defined your computation model, so here is a suggestion.
The input to the algorithm is a sorted array $A$ of length $n$ and an element $x$.
The output is either a position $i$ such ...
0
votes
Decision tree for searching element in sorted-array
The lower bound can be found as the minimum height of a binary tree holding $n$ leaves. A complete tree has this property and has a logarithmic height.
2
votes
Accepted
Find a path with given weight and the minimum number of edges on a tree
This answer explains an algorithm that finds the minimum number of edges in $O(n\log n)$ time. With more bookkeeping, the path of weight $k$ with that minimum number of edges can also be found in $O(n\...
Top 50 recent answers are included
Related Tags
trees × 783algorithms × 306
graphs × 235
data-structures × 211
binary-trees × 119
search-trees × 49
graph-traversal × 45
search-algorithms × 30
optimization × 26
time-complexity × 24
recursion × 24
combinatorics × 23
balanced-search-trees × 22
algorithm-analysis × 21
terminology × 21
dynamic-programming × 21
minimum-spanning-tree × 19
complexity-theory × 17
heaps × 17
shortest-path × 16
binary-search-trees × 16
spanning-trees × 15
discrete-mathematics × 14
reference-request × 10
strings × 10