Was ist die Komplexität der Verkettung ausgewogener Seile?
Ich habe mir verschiedene Papiere angesehen und hier sind die Informationen, die ich gesammelt habe:
SGI Implementierung undC Schnüre garantiert keine O (1) -Zeit-Verkettung für lange Seile und keine ~ log N-Tiefe für kürzere Seile. Verschiedene Quellen widersprechen sich. Wikipedia behauptet O (1) Verkettung.Diese Seit sagt, dass die Verkettung nur dann O (1) ist, wenn ein Operand klein ist, andernfalls O (log N).Also, was ist die zeitliche Komplexität der Verkettung? Wann wird genau ein Neuausgleich durchgeführt, um diese Verkettungskomplexität bei gleichzeitiger Aufrechterhaltung des Baumgleichgewichts sicherzustellen? Werden bestimmte Verwendungsmuster angenommen, wenn von dieser Komplexität gesprochen wird?