7

It's fixed-parameter tractable in the natural parameter, the distance. So if two trees have distance $k$ you can find the distance in time polynomial + $f(k)$ for some function $f$. The proof is a kernelization that produces a kernel of size $O(k)$ so putting that together with the naive method of finding a shortest path in the flip graph gives time singly ...


7

Sleator-Tarjan '85 and Demaine et al '09 definitely belong on any such list. There is a lot of other recent work related to splay trees and dynamic optimality, for instance: Applications of forbidden 0-1 matrices to search tree and path compression-based data structures, Seth Pettie, SODA 2010 An O (log log n)-competitive binary search tree with optimal ...


5

Indeed, this graph has treewidth 2. It's a well-known result in phylogenetics where the leaves are labelled. See Bryant, David, and Jens Lagergren. "Compatibility of unrooted phylogenetic trees is FPT." Theoretical Computer Science 351.3 (2006): 296-302. The graph structure they use unifies leaves with the same label (rather than putting an edge between them)...


3

I think that the problem is not hard, because if I understood the problem statement correctly, it can be solved in $O(|V|^2)$ time as follows: We have two $0$-$1$-labeled rooted perfect full binary trees $(A, x)$ and $(B, y)$ with $2^k-1$ nodes. We compute the minimum number of mismatches in any isomorphism between the trees denoted by $F(A, B)$ recursively ...


3

I think the best way is to make a recursive algorithm. You could divide your input in half (approx), and keep out the central element. Then you recursively build a tree with the left subarray which will be the left child of the central element, and equivalently the tree resulting from the right subarray will be the right child. By induction you can prove ...


2

Although this is not exactly the question you asked, you can also build balanced trees from ordered data in an online manner. That is to say, you could walk your array from left-to-right building up partial results, and if some asked you to stop after k items you could finish building the tree in log k time (with the total time being O(k), and the extra ...


1

Extended comment of an idea or two toward a lower bound. Let $B = \Theta(\log n)$, say (though the best choice may be different), and let $\{v_1,\dots,v_n\} = \{\frac{1}{n}B, \dots, \frac{n-1}{n}B, B\}$. Consider drawing the input by picking a permutation of these values uniformly at random. The idea should be that if we fix the indices of all values except ...


1

You may need to look at this report: https://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf Each individual operation takes $O(\log n)$ but when you apply amortized analysis to a sequence of operations, you get something interesting. Directly from this report: "However, amortized analysis can be used to show that any sequence ...


1

If I understand your question correctly and the elements arrive in sorted order, I believe the usual bottom-up AVL tree insertion algorithm meets your criteria. In particular, insert-only AVL trees have $O(1)$ amortized (and $O(\lg n)$ worst-case) update time. Simply maintain a pointer to the last element of the tree and perform each insertion at that ...


Only top voted, non community-wiki answers of a minimum length are eligible