Ancêtre commun le plus proche (LCA) dans un arbre
L'ancêtre commun le plus proche (LCA) de deux nœuds u et v dans un arbre enraciné est le nœud le plus profond qui est un ancêtre à la fois de u et de v. Par exemple, dans l'arbre ci-dessous, LCA(3,7) = 1 et LCA(3,4) = 2.
Il existe plusieurs méthodes pour calculer le LCA, classifiées en algorithmes hors ligne (toutes les requêtes sont connues à ...
Publié le 29 juin à 20h34