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 ...
- 7,154
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$ (...
- 1,005
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 ...
- 3,337
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 ...
- 7,154
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)...
- 33.1k
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 ...
- 269k
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.
- 3,337
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\...
- 33.1k
Top 50 recent answers are included