LCA in Binärbäumen

• 
  
  lowest common ancestor
  • LCA
  • der LCA zweier Knoten u und v ist derjenige Knoten w
    • der gemeinsamer Vorfahre von u und v ist
    • und dabei die größte Entfernung zur Wurzel des Baumes hat
• typische Preprocessing-Aufgabe
  • "vorverarbeite" den Baum (parallel) so, dass bei Vorgabe des
    Paares (u,v) der LCA von (u,v) in O(1) seriell bestimmbar ist
    • Preprocessing soll in O(log n) erfolgen
  • zum Beispiel für Range Minima Problem
• Hinweis: Fehler im JáJá!
• einfache Fälle
  • 1
    • 
      
      Liste &@ spezieller Baum
    • hier ist Preprocessing = Bestimmung der Abstände vom Anfang der Liste
    • geht in O(log n) TIME parallel
  • 2
    • 
      
      vollständiger Binärbaum
      • 
        
        Preprocessing: INORDER-Nummerierung mit 0-1-Worten
      • Inorder-Traversierung
        • inorder(LTB)
          output(root)
          inorder(RTB)
    • dann:
      • Algorithmus von Ja'Ja
        • Nehmen der beiden Knoten u,v
        • übernehmen bis zur lenkesten abweichenden Stelle
        • Beispiel:
          • 
            
            
        • aber: stimmt nicht immer:
          • 
            
            falsch!
      • Algorithmus von Spillner
        • INPUT (u,v)
        • begin
        • if (u=v) then OUTPUT(u) else
        • bestimme k_u, k_v
          • 
            
            // rechteste "1" in u bzw. w
        • wende den Algorithmus von Ja'Ja auf (u,v) von links nach rechts an,
          bis entweder STOP mit Ja'Ja oder k_u bzw. k_v erreicht wurden
        • Output(u₁,...,u_ku,0, ..., 0) bzw. Output(v₁,...,v_ku,0,...,0)
        • end
        • Beispiel: u = 8 = 1000_bin, v = 15 = 1111_bin
          • Þ k_u = u[1], k_v = v[4]
          • Þ Output (u₁,...,u_ku,0,...,0) = (1,0,0,0)
• Lösung des LCA-Problems mit Eulertour-Technik
  • sei Eulertour "S" gegeben
  • unter dem zugehörigen Eulerarray verstehen wir die entsprechende Knotenfolge
  • 
    
    Baum
    • s(<1,2>) = <2,3>
    • s(<2,3>) = <3,2>
    • ...
    • Eulerarray: A=(1,2,3,2,4,5,4,6,4,7,4,2,1,8,1,9,1)
  • mit Eulertourtechnik bereits gezeigt:
    • Bestimmen von Level(v) " v geht in O(log n) Time
    • siehe
      • Eulertour-Technik
  • Sei nun
    • B: "v≠r: level(v)
    • l(v) = linkestes Vorkommen von v in A
    • r(v) = rechtestes Vorkommen von v in A
  • Þ
    Levelarray A=(1,2,3,2,4,5,4,6,4,7,4,2,1,8,1,9,1)
    B=(0,1,2,1,2,3,2,3,2,3,2,1,0,1,0,1,0)
  • Lemma:
    • sei
      • T(V,E) ein Wurzelbaum
      • seien A, level(v), r(v), l(v) bekannt
      • der INPUT ein Knotenpaar (u,v) mit u≠v
    • Þ1. (u ist Vorfahre von v) (l(u) < l(v) <r (u)) Þ LCA(u,v) := u
    • Þ2. (u, v sind nicht related) (r(u) < l(v)) oder (r(v) <l(u))
    • Þ2a. Wenn r(u)<l(v), dann ist LCA(u,v) die Ecke mit minimalem Level im Intervall [r(u), l(v)]
    • Þ2b. Wenn r(v)<l(u), dann ist LCA(u,v) die Ecke mit minimalem Level im Intervall [r(v), l(u)]
    • A=(1,2,3,2,4,5,4,6,4,7,4,2,1,8,1,9,1)
      LEVELARRAY B=(0,1,2,1,2,3,2,3,2,3,2,1,0,1,0,1,0)
      • unterstrichen: r(u) und l(v)
      • fett: min_Level([r[u], l[v]])
  • Folgerung: damit ist das LCA-Problem zurückgeführt auf das
    • Range-Minima-problem
  • Þ wenn Range-Minima-Problem gelöst Þ LCA-Problem gelöst
• → LCA ist O(log n) optimal lösbar