Autor Téma: Je daná hodnota v strome?  (Přečteno 79 krát)

Offline Stanislav Hruška

  • Padawan
  • ******
  • Příspěvků: 6671
  • Karma: 44
    • Verze Delphi: W10 + D11.1
Je daná hodnota v strome?
« kdy: 05-08-2022, 06:31:38 »

Mám dva VST (VirtualStringTree).
Zdroj - ťahám z neho 10 uzlov. Cieľ - má (napr.) 1 000 uzlov.
Potrebujem zistiť či hodnoty X1 - X10 sa nachádzajú v cieli = tento uzol už v nich je. Terajše riešenie:
Kód: Delphi [Vybrat]
  1. Node := Target.GetFirst;
  2. while Assignid(Nod) do
  3. begin
  4.   Result := False;
  5.   NodeData := Target.GetNodeData(Node);
  6. .  
  7.   if Xn = NodeData.Integers[0] then
  8.     Result := True;
  9. .    
  10.   Node := Target.GetNext(Target);
  11. end;
Pri neúspechu to je 10 prechodov cez strom a 10 000 porovnaní. Rád by som to oprimalizoval. Vzhľadom na moje vedomosti a schopnosti požadujem "hotové" riešenie. Moja predstava riešenia je:
Len v prípade potreby
  • vytvorím si zoznam hodnôt NodeData.Integers[0] (primárne kľúče DB tabuľky)
  • aký typ? Rieši niečo TDictionary?
  • zoznam zoradím
  • použijem nejakú jednoduchú/základnú metódu na vyhľadanie hodnoty Xn
  • vrátim si výsledok našiel/nenašiel
Ako realizovať samotné vyhľadávanie?
Ďakujem.
W10 64b, Delphi 11.1, FireBird 3.08
Expert na kladenie nejasne formulovaných otázok.

Offline pf1957

  • Padawan
  • ******
  • Příspěvků: 3433
  • Karma: 139
    • Verze Delphi: D2007, XE3, DX10
Re:Je daná hodnota v strome?
« Odpověď #1 kdy: 05-08-2022, 07:54:17 »
   
  • aký typ? Rieši niečo TDictionary?
Ano, TDictionary je k tomu primo predurcen, protoze pristup k hodnote pres klic ma slozitost O(1). Takze pokud mas klic integer, udelas si ke stromu index v podobe seznamu dvojic klic:uzel tj. TDictionary<Integer, PVirtualNode> a pak pouzijes metodu ContainsKey() na prosty test existence ev. TryGetValue() na ziskani uzlu.

Offline Stanislav Hruška

  • Padawan
  • ******
  • Příspěvků: 6671
  • Karma: 44
    • Verze Delphi: W10 + D11.1
Re:Je daná hodnota v strome?
« Odpověď #2 kdy: 05-08-2022, 10:23:43 »
Mne stačí iba zistiť, či tam ten prvý kľúč existuje. Druhý v tomto prípade nepotrebujem. Ak sa totiž kľúč nájde, tak nepridám do stromu uzol. Bol by dvakrát.
W10 64b, Delphi 11.1, FireBird 3.08
Expert na kladenie nejasne formulovaných otázok.