New answers tagged trees
1
You have to do three things:
Exhibit an algorithm.
Prove that it is correct (it outputs the right value).
Prove that its running time is $O(|V|)$.
@Steven describes one way to prove the running time.
One can probably prove correctness using structural induction as well.
2
You can prove that formally by using structural induction. The structure of the proof is as follows:
Observe that a preorder traversal of a tree with $1$ vertex requires constant time.
Then, assume that a preorder traversal of a tree with up to $i \ge 1$ vertices can be performed in time at most $c \cdot i$, for a suitable constant $c$, and show that the ...
0
Interesting question. For a better theoretical understanding of the whole theory I would suggest you to re-read "Introduction to Algorithms, Third Edition, Cormen" Chapter 12 (Trees) and Chapter 13 (Red-Black Trees). Since it is stated there that (page 311):
As an immediate consequence of this lemma, we can implement the
dynamic-set operations ...
2
A tree structure can be completely described by three functions:
a function that given a node $x$ returns the number of children of that node,
a function that given a node $x$ and index $i$ returns the $i$th child of that node, and
a function that given a node $x$ returns an associated value $v$ stored at that node.
0
The following paper considers your task in the general case:
Partial-Match Retrieval Algorithms. Ronald L. Rivest. SIAM Journal Computing, vol 5 no 1, March 1976.
It yields a data structure with a running time that is slightly better than enumerating all words in the dictionary and checking each to see if it meets the conditions.
1
If I've got nothing more than a check of whether an arbitrary string is an English word, I have to do 5^26 calculations. $5^{26}$ is of order $10^{18}$, while the actual number of English words is of order $10^5$. So, depending on your application, simply enumerating all words and checking whether they satisfy the constraints may already be sufficiently ...
1
What you can do is to add a counter $t$ to each node, initially 0, indicating how many of its children are terminal.
When $t = c$ where $c$ is the number of children of a node, the node itself becomes terminal and increments the $t$ counter of its parent. Note that with this definition leaf nodes are automatically terminal, as they have no children, giving $...
Top 50 recent answers are included
