Search results

Create the page "Link-cut tree" on this wiki! See also the search results found.

• Depth-first search
  ==The DFS tree== ...cannot go any further, and, hence, produce relatively long paths. The DFS tree has a number of useful properties that allow efficient solutions to importa
  17 KB (2,930 words) - 00:28, 3 March 2012
• Heavy-light decomposition
  ...sing in Sleator and Tarjan's analysis of the performance of the [[link-cut tree]] data structure. ...-light decomposition'' of a tree <math>T=(V,E)</math> is a coloring of the tree's edges. Each edge is either ''heavy'' or ''light''. To determine which, co
  9 KB (1,665 words) - 12:40, 6 August 2015
• String
  ...habet is general, and we do the same, then the time taken to walk down the tree will be <math>O(N \log |\Sigma|)</math> again; but this is no longer bounde
  12 KB (1,959 words) - 23:56, 23 November 2011
• Linked list
  ...elements are both important, it is advisable to use a [[Binary search tree|tree]].
  5 KB (905 words) - 02:16, 30 December 2011
• Tree
  ...e eponymous tall, woody plants, as these are also connected and acyclic (a tree is in one piece, but its branches never form cycles). A collection of disjo ...aph, any two of these three statements, taken together, imply the third ([[Tree/Proof of properties of trees|proof]]):
  17 KB (2,906 words) - 03:22, 12 December 2011
• Data structure
  ...ces. There are many ways of implementing these, such as by [[binary search tree]]s, [[hash table]]s, or [[skip list]]s, but the language standard usually d ...rough. (This is the case, for example, with properly implemented immutable tree data structures in which the new version shares most of its nodes with the
  9 KB (1,544 words) - 02:06, 20 March 2011
• Lowest common ancestor
  ...'''least common ancestor''' (LCA) of a nonempty set of nodes in a rooted [[tree]] is the unique node of greatest depth that is an ancestor of every node in ...thermore, the <math>\operatorname{LCA}(u,v)</math> is the only node in the tree for which this is true.
  11 KB (2,023 words) - 23:03, 5 April 2016
• Ford–Fulkerson method
  ...time, which can be sped up to <math>O(V E \log V)</math> using [[link/cut tree]]s.
  3 KB (506 words) - 04:12, 9 September 2013