Ok,
I have an algorithm I believe is O(nlog*(n)), that's n log-star(n) (log-star n is constant for all practical purposes), but it's hard to prove and I suppose I could be wrong. The running time guess comes from assuming the path compression step takes amortized O(log*(n)) as it does in a union-find data structure, but I don't remember the proof of that so I don't really know for certain that it applies here. Nonetheless, I certainly can't generate any examples where the path-compression is generally slow and I can prove the other operations are amortized constant time.
Following Chao Xu's suggestion, I'll describe the "insert a new leaf" operation on the data structure.
Each vertex has to contain pointers to 4 other vertices in addition to remembering its depth.
Each vertex $v_i$ must remember:
$v_i$'s deepest descendant
$v_i$'s child on whose branch (1) is contained
$v_i$'s nearest ancestor $w_i$ for whom $w_i(2)$ is not an ancestor of $v_i$
Which child of $w_i$ is an ancestor of $v_i$
In fact for any given vertex (1), (3), and (4) may be outdated, but using path-compression we can bring it up to date in (hopefully) amortized O(log*n) running time using path-compression.
def get_deepest(v): # returns (1)
if v.deepest == v:
return v
v.deepest = get_deepest(v.deepest)
while True:
deep_ancest,_ = get_nearest_ignoring_ancestor(v.deepest)
if (not deep_ancest) or deep_ancest.depth <= v.depth:
break
v.deepest = get_deepest(deep_ancest)
return v.deepest
def get_nearest_ignoring_ancestor(v): # returns tuple containing (3) and (4)
if v.nia == None:
return (None, root)
elif v.nia.child_containing_deepest == v.nia_child_containing_self:
v.nia,v.nia_child_containing_self = get_nearest_ignoring_ancestor(v.nia)
return (v.nia, v.nia_child_containing_self)
Now when we add a new vertex $v$, we traverse upwards through each (3) updating the deepest vertex until we find one that doesn't update. If we encounter a vertex $w$ which is on the primary path (this is easy to check because $w$.deepest() will be the same as root.deepest()), then we check if the path between the newly inserted node and the current deepest is longer than the currently known longest path. Then that becomes the new diameter. This check can be done in constant time since we know the depths of the current deepest, the newly inserted node, and also the node $w$ at which the paths pointing to the two diverge. Then the length (number edges in) the new path is just $d(v)+d(deepest)-2 d(w)$
It's easy to see that this algorithm is correct because any diameter must have an endpoint at the deepest node from the root (This is generally true of trees. If you don't believe me you can verify it for yourself) and with every node we insert, we check that either
a) It's the deepest node (in which case, we've just increased the currently longest path by one)
OR
b) There exists an ancestor containing a deeper (or equal) node which is not on the deepest path (so the diameter can't have increased)
OR
c) We check the newly inserted node against the deepest node and compute the length of the new path to see if it's longer than the current longest.
To finish the Python pseudo-code for the algorithm:
#root is the root of the tree, it's parent is None
#cur_opp is the vertex currently farthest from get_deepest(root)
def add_node(v, parent):
v.deepest = v
v.child_containing_deepest = None
v.nia = parent
v.nia_child_containing_self = v
root_deepest = get_deepest(root)
while True:
v_ancest,_ = get_nearest_ignoring_ancestor(v)
if not v_ancest:
check_update_path(root_deepest)
break
old_deepest = deepest(v_ancest)
if v.depth > old_deepest.depth:
old_deepest.nia = v_ancest
old_deepest.nia_child_containing_self = v_ancest.child_containing_deepest
v_ancest.child_containing_deepest = v.nia_child_containing_self
v_ancest.deepest = v
update_next = True
else:
break
check_update_path(v)
def check_update_path(v):
cur_deepest = get_deepest(root)
if v == cur_deepest:
return
common = get_nearest_ignoring_ancestor(v)
if get_deepest(common) != cur_deepest:
return
max_len = len_path(cur_opp, cur_deepest)
new_len = len_path(v, cur_deepest)
if new_len > max_len:
cur_opp = v
def len_path(a,b):
a_ancest = get_nearest_ignoring_ancestor(a)
assert get_deepest(a_ancest) == b
return a.depth + b.depth - 2 * a_ancest.depth
The longest path is just the path from cur_opp to get_deepest(root)
Now to show that the number of deepest-branch changes is amortized constant with each add, just imagine that each time we compare two depths and get d(a) == d(b) (when we stop), we reserve one time unit for later. When a node changes deepest branches, the paths must have first been equal so we use up that time unit.
So now all that remains to prove is that the path-compression step is amortized fast and I unfortunately don't know how to do that.
Please note I haven't tested this code and it is almost certainly buggy. Also, I may have left out some edge cases such as how to insert the first node or what to do in certain situations if a node already is on the primary path. It shouldn't be too hard to account for these.
