New answers tagged trees
0
In order to get the files in the desired order, simply follow the following rule: A node can be deleted iff all of its children have been deleted. This is the same as a postorder traversal of a tree.
Let's say you use a container $S$ for your search structure (stack for DFS or queue for BFS). Now, we create a stack $T$ which will in the end will be the ...
0
I'm not sure about the algorithm modification to directly call the callback function in a reverse order, but I found a way to do this without extra memory allocation.
My solution is to embed a doubly linked list node within the data structure storing rules. (It actually turns out there was already a linked list node in the data structure I used for other ...
1
The Natural Language Toolkit (NLTK) offers binarization: nltk.treetransforms.chomsky_normal_form(). The algorithm in NLTK implements the standard, straight-forward transformation into Chomsky normal form. It assumes the tree was generated via an underlying (context-free) grammar. This results in the deep trees in the bottom row (diagram in the question post)....
4
First note that $\text{increase-key}$ must be $O(\log n)$ if we wish for $\text{insert}$ and $\text{find-min}$ to stay $O(1)$ as they are in a Fibonacci heap.
If it weren't you'd be able to sort in $O(n)$ time by doing $n$ $\text{insert}$s, followed by repeatedly using $\text{find-min}$ to get the minimum and then $\text{increase-key}$ on the head by $\...
3
No, not all foldable data structures are recursive, although the in the non-recursive case what we have is really a degenerate version of a fold.
For example, we can view the function if : Bool -> a -> a -> a as a fold over the type Bool.
In general, when dealing with recursive or non-recursive types, the fold are called eliminators, since they ...
0
I think we can reduce uncolored graph isomorphism to this problem.
For connected rooted graphs $G$ and $H$, construct trees $G'$ and $H'$ in the following way:
Begin creating graph $G'$ with just a single vertex $0$. This vertex will be the root of the resulting tree (which will be just of depth 2).
For each vertex $v$ in $G$, create a vertex $v$. ...
Top 50 recent answers are included
