| dbo:abstract
|
- A számítógép-tudományban az AVL-fa alatt egy ön-kiegyensúlyozó bináris keresőfát értünk. Ez volt az első ilyen adatszerkezet. Egy AVL-fában bármely csúcspont két részfájának magassága közti különbség legfeljebb egy. Kiegyensúlyozott-magasságúnak is hívják az ilyen struktúrákat.A keresés, beillesztés és törlés egyaránt O(log n) nagyságrendű időt vesz igénybe, még a legrosszabb esetben is. Beillesztés és törlés esetén szükséges lehet forgatások alkalmazásával újra kiegyensúlyozni a fát. Az AVL-fa nevét két feltalálójáról -ről és -ról kapta, akik 1963-ban publikálták An algorithm for the organization of information (Egy algoritmus az információ szervezettségéhez) című cikkükben. Minden csúcsnak van egy ún. egyensúly-faktora, amit megkapunk, ha kivonjuk a bal részfa magasságát a jobb részfáéból. Egy csúcs kiegyensúlyozott, ha ez az érték 1, 0 vagy -1. Minden más esetben a csúcs kiegyensúlyozatlan és forgatásokat igényel. Az AVL-fákat gyakran hasonlítják össze a piros-fekete fákkal, mivel azonos műveleteket valósítanak meg és ezekre az O(log n) futásidő jellemző. Gyakori keresést igénylő alkalmazásokban az AVL-fa hatékonyabb (hu)
- A számítógép-tudományban az AVL-fa alatt egy ön-kiegyensúlyozó bináris keresőfát értünk. Ez volt az első ilyen adatszerkezet. Egy AVL-fában bármely csúcspont két részfájának magassága közti különbség legfeljebb egy. Kiegyensúlyozott-magasságúnak is hívják az ilyen struktúrákat.A keresés, beillesztés és törlés egyaránt O(log n) nagyságrendű időt vesz igénybe, még a legrosszabb esetben is. Beillesztés és törlés esetén szükséges lehet forgatások alkalmazásával újra kiegyensúlyozni a fát. Az AVL-fa nevét két feltalálójáról -ről és -ról kapta, akik 1963-ban publikálták An algorithm for the organization of information (Egy algoritmus az információ szervezettségéhez) című cikkükben. Minden csúcsnak van egy ún. egyensúly-faktora, amit megkapunk, ha kivonjuk a bal részfa magasságát a jobb részfáéból. Egy csúcs kiegyensúlyozott, ha ez az érték 1, 0 vagy -1. Minden más esetben a csúcs kiegyensúlyozatlan és forgatásokat igényel. Az AVL-fákat gyakran hasonlítják össze a piros-fekete fákkal, mivel azonos műveleteket valósítanak meg és ezekre az O(log n) futásidő jellemző. Gyakori keresést igénylő alkalmazásokban az AVL-fa hatékonyabb (hu)
|
