Топ стабло

Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу.
Када завршите са провером, допишете да након |проверено=.

Топ стабло је структура података заснована на бинарном стаблу која се примењује на динамичком стаблу без корена за разне операције везане за путање. Дозвољава једноставне подели па владај алгоритме. Одржава динамички различите особине стабла, као што су пречник, центар и средишња линија.

Топ стабло $\Re$ је дефинисано као фундаментално стабло ${\mathcal {T}}$ и скуп $\partial {T}$ од највише два чвора која се називају спољашњи гранични чворови.

Алфабетска листа техничких термина

Гранични чворови

Видети #Гранична темена

Гранична темена

Теме у повезаном подстаблу је гранично теме ако је ивицом повезано са највишом тачком изван подстабла.

Спољашња гранична темена

Пар темена топ стабла могу да се називају спољашња гранична темена. Посматрају се као гранична темена јата која представљају цело топ стабло.

Јато

Јато је повезано подстабло са највише два гранична темена. Скуп од граничних темена датог јата ${\mathcal {C}}$ се означава као $\partial {C}.$ . Са сваким јатом ${\mathcal {C}}$ корисник може повезати неке мета информације $I({\mathcal {C}}),$ и користити методе како би га одржао под утицајем различитих унутршњих операција.

Јато путање

Ако $\pi ({\mathcal {C}})$ садржи бар једну ивицу, онда се ${\mathcal {C}}$ назива јато путање.

Јато тачке

Видети јато листа

Јато листа

Ако $\pi ({\mathcal {C}})$ не садржи ни једну ивицу или ${\mathcal {C}}$ има само једно гранично теме онда се ${\mathcal {C}}$ зове јато листа.

Јато ивице

Јато које садржи само једну ивицу се назива јато ивице.

Лист јата ивице

Лист у оригиналном јату који је је представљен јатом са само једним граничним теменом назива се лист јата ивице

Путања јата ивице

Ивица Јата са два гранична темена се зове путања јата ивице.

Унутрашњи чвор

Чвор у ${\mathcal {C}}$ \ $\partial {C}$ се назива унутрашњи чвор од ${\mathcal {C}}.$

Путања јата

Пут измедју граничних темена од ${\mathcal {C}}$ се назива путања јата од ${\mathcal {C}}$ и означава се са $\pi ({\mathcal {C}}).$

Спојива јата

Два јата ${\mathcal {A}}$ и ${\mathcal {B}}$ су спојива ако је ${\mathcal {A}}\cap {\mathcal {B}}$ једностран скуп(имају тачно један заједнички чвор) и ${\mathcal {A}}\cup {\mathcal {B}}$ је јато.

Увод

Топ Стабла се користе за одржавање динамичког скупа стабала под операцијама везивања и прекидања.

Основна идеја је одржавање балансираног бинарног стабла $\Re$ логаритамским растом броја чворова почетног стабла ${\mathcal {T}}$ у ${\mathcal {O}}(\log n)$ времену); Топ стабло у суштини представља рекурзивну поделу почетног стабла ${\mathcal {T}}$ у јата.

У принципу, стабло ${\mathcal {T}}$ може имати тежину на својим ивицама.

Постоји један на један кореспонденција са ивицама почетног стабла ${\mathcal {T}}$ и листовима чворова топ стабла $\Re$ и сваки унутрашњи чвор од $\Re$ представља јато које је формирано унијом јата његове деце.

Топ стабло може бити иницијализовано у ${\mathcal {O}}(n)$ времену. ${\mathcal {T}}$

Стога је топ стабло $\Re$ по ( ${\mathcal {T}},$ $\partial {T}$ ) бинарно стабло за које важи

Чворови од $\Re$ су јата од ( ${\mathcal {T}},$ $\partial {T}$ );
Листови од $\Re$ су ивице од ${\mathcal {T}};$
Јата родјаци су комшије у смислу да се секу у једном темену и да их спаја јато, које је њихов родитељ.
Корен од $\Re$ је стабло ${\mathcal {T}}$ само себи, са скупом од највише два спољашња гранична темена.

Стабло са само једним теменом има празно топ стабло, а стабло са само једном ивицом је само појединачан чвор.

Ова стабла се лако увећавају, омогућавајући кориснику широк спектар флексибилности и продуктивности без улажења у детаље функционисајна интерних структура података, што се често назива црна кутија.

Динамичке операције

Следеће три операције су доступне кориснику.

Повезивање(в, w): Где су $v$ и $w$ темена у различитим стаблима ${\mathcal {T}}$ ₁ и ${\mathcal {T}}$ ₂. Операција враћа једно топ стабло које представља $\Re$ _в $\cup$ $\Re$ _w $\cup {(v,w)}$

Пресецање(в, w): Одваја ивицу ${(v,w)}$ од стабла ${\mathcal {T}}$ са топ стаблом $\Re ,$ тиме га претворивши у два стабла ${\mathcal {T}}$ _в и ${\mathcal {T}}$ _w и враћа два топ стабла $\Re$ _в и $\Re$ _w.

Откривање(С): Зове се као подрутина за спровођење највише два упита на топ стаблу. $S$ садржи највише два темена. Првобитна спољашња темнена постају нормална темена, а темена од $S$ постају нова спољашња гранична темена топ стабла. Ако $S$ није празно, операција враћа нови корен јата ${\mathcal {C}}$ са $\partial {C}=S.$ Откривање({в,w}) је неуспешно ако су темена са различитих стабала.

Унутрашње операције

Ажурирање стабла се спроводи секвенцом од највише ${\mathcal {O}}(\log n)$ унутрашњих операција, секвенца која се рачуна у даљем ${\mathcal {O}}(\log n)$ времену. Може се десити да се у току ажурирања стабла јато листа промени у јато путање и обратно. Допуне на топ стаблу се искључиво врше овим унутрашњим операцијама.

$I({\mathcal {C}})$ се ажурира позивањем функције дефинисане од стране корисника, повезане са сваком унутрашњом операцијом.

Спајање $({\mathcal {A}},{\mathcal {B}}){:}$ Овде су ${\mathcal {A}}$ и ${\mathcal {B}}$ интегрисана јата, операција враћа ${\mathcal {C}}$ као родитељско јато од ${\mathcal {A}}$ и ${\mathcal {B}}$ са граничним теменима као граничним теменима од ${\mathcal {A}}\cup {\mathcal {B}}.$ рачуна $I({\mathcal {C}})$ користећи $I({\mathcal {A}})$ и $I({\mathcal {B}}).$

Раздвајање $({\mathcal {C}}){:}$ Овде је ${\mathcal {C}}$ јато корена ${\mathcal {A}}\cup {\mathcal {B}}.$ Допуњава $I({\mathcal {A}})$ и $I({\mathcal {B}})$ користећи $I({\mathcal {C}})$ и онда брише јато ${\mathcal {C}}$ из $\Re$ .

Раздвајање се обично спроводи коришћењем чистих $({\mathcal {C}})$ метода које позивају корисничке методе за ажурирање од $I({\mathcal {A}})$ и $I({\mathcal {B}})$ користећи $I({\mathcal {C}})$ и ажурирање $I({\mathcal {C}})$ тако да се зна да нема даље потребе за ажурирањем његове деце. Онда је ${\mathcal {C}}$ одбачено без позивања кориснички дефинисаних функција. Чист метод се често користи зе упите који не треба да се раздвајају. Ако раздвајање не користи подрутину чистог метода, а чист метод је потребан, његов ефекат би могао бити постигнут комбиновањем спајања и раздвајања.

Следеће две функције су аналогне двема претходнима и користе се за базна јата.

Направи $(v,w){:}$ прави јато ${\mathcal {C}}$ за ивицу $(v,w).$ поставља $\partial {C}=\partial$ $(v,w).$ $I({\mathcal {C}})$ се рачуна од нуле.

Искорени $({\mathcal {C}}){:}$ ${\mathcal {C}}$ је ивично јато $(v,w).$ Кориснички дефинисана функција се зове за обраду $I({\mathcal {C}})$ и онда је јато ${\mathcal {C}}$ обрисно из топ стабла.

Нелокална претрага

Корисник може да дефинише Изабери $({\mathcal {C}}){:}$ операције које за јато корена (без листова) бира јато једног његовог детета. Црна кутија топ стабла омогућава Тражи $({\mathcal {C}}){:}$ рутину, која организује изабери упите и реорганизује топ стабло(користећи унутрашње операције) тако да проналази једину ивицу у раскрсници свих одабраних јата. Понекад би претрага требала бити ограничена само на путању. Постоји варијанта нелокалне претраге за ову сврху. Ако постоје два спољашња гранична темена у јату корена ${\mathcal {C}}$ , ивица се тражи само на путањи $\pi ({\mathcal {C}})$ . Дозвољено је да се ураде следеће измене: Ако је само једно дете јата корена јато путање, бира се по дифолту без позива изабери операције.

Примери нелокалне претраге

Проналажење и-те ивице на дужем путу од $v$ до $w$ може да се постигне као ${\mathcal {C}}$ =Откривање({в,w}) праћено са Тражи( ${\mathcal {C}}$ ) и са одговарајућом операцијом изабери. За спровођење операције изабери користимо глобалну променљиву која представља $v$ и глобалну променљиву која представља $i.$ Операција изабери бира јато ${\mathcal {A}}$ са $v\in \partial {A}$ ако и само ако је дужина од $\pi ({\mathcal {A}})$ најмање $i$ . Како би подржала операцију дужина се мора одржавати у $I$ .

Сличан задатак може бити формулисан за граф са ивицама нејединичне дужине. У том случају даљина може да адресира ивицу или теме између две ивице. Могли би дефинисати операцију изабери тако да се ивица која води до темена враћа у другом случају. Ту би се могло дефинисати ажурирање које повећава дужину свих ивица дуж путањом константе. У том случају ажурирања су извршена у константном времену само у јату корена. Чист метод је потребан како би дистрибуирао одложено ажурирање деце. Чист метод би требао бити позван пре него што је функција тражи позвана. Одржавање дужине у $I$ би у том случају захтевало и одржавање јединичних дужина у $I$ .

Проналажење центра стабла које садржи теме $v$ могло би да се постигне било проналажењем бицентралне ивице, било ивице са центром као једном крајњом тачком. Ивица би могла бити нађена као ${\mathcal {C}}$ =Откривање({в}) праћено са Тражи( ${\mathcal {C}}$ ) и погодном операцијом изабери. Операција изабери бира између деце ${\mathcal {A}},$ ${\mathcal {B}}$ са $a\in \partial {A}\cap \partial {B}$ дете са већом максималном дистанцом $(a)$ . Како би подржала операцију максимална дистанца у подстаблу јата са граничним теменом треба да буде одржавана у $I$ . То такодје подразумева одржавање дужине путање јата.

Занимљиви резултати и апликације

Број занимљивих апликација првобитно спроведених другим методама су лако спроведене коришћењем интерфејса топ стабла. Неке од њих су

([СЛЕАТОР I ТАРЈАН 1983]). Можемо одржати динамичку колекцију отежаних стабала у ${\mathcal {O}}(\log n)$ времену по спајању и раздвајању, који подржавају упите о максималној тежини ивице између било која два темена у $O(\log n)$ времену.
- Доказ контуре: Укључује одржавање максималне тежине путање јата на сваком чвору, ако је јато тачке онда је макс_теж( ${\mathcal {C}}$ ) иницијализовано као $-\infty .$ Кад је јато унија два јата онда је то максимална вредност два спојена јата. Уколико морамо наћи макс_теж између $v$ и $w$ онда радимо ${\mathcal {C}}=$ Откривање $(v,w),$ и пријавимо макс_теж $({\mathcal {C}}).$

([СЛЕАТОР I ТАРЈАН 1983]). У случају горе наведене апликације такође можемо додати заједничку тежину $x$ свим ивицама на датој путањи $v$ · · · $w$ у ${\mathcal {O}}(\log n)$ времену.
- Доказ контуре: Уводимо тежину која се назива посебном( ${\mathcal {C}}$ ) како би била додана свим ивицама у $\pi ({\mathcal {C}}).$ Што се адекватно одржава ; раздвајање( ${\mathcal {C}}$ ) захтева да за свако дете путање ${\mathcal {A}}$ од ${\mathcal {C}},$ поставимо макс_теж(А) := макс_теж( ${\mathcal {A}}$ ) + посебна( ${\mathcal {C}}$ ) и посебна( ${\mathcal {A}}$ ) := посебна( ${\mathcal {A}}$ ) + посебна( ${\mathcal {C}}$ ). За ${\mathcal {C}}$ := придружити( ${\mathcal {A}},$ ${\mathcal {B}}$ ), поставимо макс_теж( ${\mathcal {C}}$ ) := макс {маx_wт( ${\mathcal {A}}$ ), макс_теж( ${\mathcal {B}}$ )} и посебна( ${\mathcal {C}}$ ) := 0. Коначно, да би нашли максималну тежину на путањи $v$ · · · $w,$ поставимо ${\mathcal {C}}$ := Откривање $(v,w)$ и враћамо макс_теж( ${\mathcal {C}}$ ).

([ГОЛДБЕРГ ЕТ АЛ. 1991]). Можемо тражити максималну тежину у фундаменталним стаблима која садрже дато теме $v$ у ${\mathcal {O}}(\log n)$ времену.
- Доказ контуре: Ово захтева одржавање додатне информације о максималној тежини негруписане путање ивице у јату под операцијама спајања и раздвајања.

Раздаљина између два темена $v$ и $w$ може бити пронађена у ${\mathcal {O}}(\log n)$ времену као дужина(Открити $(v,w)$ ).
- Доказ контуре: Одржаваћемо дужину ( ${\mathcal {C}}$ ) путање јата. Дужина се одржава као максимална тежина са тим да ако је ${\mathcal {C}}$ креирано спајањем, дужина( ${\mathcal {C}}$ ) је збир дужина чуван у путањама његове деце.

Упити везани за пречник стабла и одржавање његових следбеника захтевају ${\mathcal {O}}(\log n)$ време.

Центар и средишња линија могу да се одржавају под операцијама спајања и раздвајања и испитивани нелокалном претрагом у ${\mathcal {O}}(\log n)$ времену.

Граф би могао бити одржаван дозвољавајући ажурирање скупа ивица и постављање упита на ивице са две везе. Амортизована сложеност ажурирања је $O(\log ^{4}n)$ . Упити могу бити спроведени још брже. Алгоритам није тривијалан, $I({\mathcal {C}})$ користи $\Theta (\log ^{2}n)$ простора ([ХОЛМ, ЛИЦХТЕНБЕРГ, ТХОРУП 2000]).

Граф би могао бити одржаван дозвољавајући ажурирање скупа ивица и постављање упита на ивице са две везе. Амортизована сложеност ажурирања је $O(\log ^{5}n)$ . Упити могу бити спроведени још брже. Алгоритам није тривијалан, $I({\mathcal {C}})$ користи $\Theta (\log ^{2}n)$ простора ([ХОЛМ, ЛИЦХТЕНБЕРГ, ТХОРУП 2001]).

Имплементација

Топ стабло може бити имплементирано на много различитих начина. Неки од њих укључују имплементацију која користи такозвану "вишестепену поделу"(топ стабло и динамички алгоритми са графовима, Јаков Холм и Кристијан де Лихтенберг, технички извештај), или чак користе Слеатор-Тарјан с-т стабла (типично са амортизованим временским оквирима).

Амортизоване имплементације су једноставније, али са малим мултипликативним факторима у временској сложености. Насупрот томе, најгори случај омогућава убрзавање упита, искључивањем непотребних информација ажурирања током упита. Након што је одговорено на упит, изворно стање стабла се користи и верзија упита се одбацује.

Коришћење вишеспратне партиције

Свака подела јата стабла ${\mathcal {T}}$ може бити представљена као јато партиције стабла(ЈПС) $({\mathcal {T}}),$ заменом сваког јата у дрвету ${\mathcal {T}}$ са ивицом. Ако користимо стратегију П за партиционисање ${\mathcal {T}}$ , онда ће ЈПС бити ЈПС_П ${\mathcal {T}}.$ . Овај поступак се понавља рекурзивно све док не остане само једна ивица.

Можемо приметити да су сви чворови одговарајућег топ стабла $\Re$ јединствено мапирани у ивицама ове поделе на више нивоа. У овој подели могу постојати неке ивице које не одговарају ниједном чвору у топ стаблу, и то су ивице које представљају једино дете у нивоу испод. Само ивице које одговарају сложеним јатима одговарају чворовима у топ стаблу $\Re .$ .

Стратегија поделе је важна док делимо стабло ${\mathcal {T}}$ на јата. Само пажљива стратегија гарантује да ћемо завршити у једној ${\mathcal {O}}(\log n)$ висини нивоа вишестепеног партиционисања.

Број ивица у наредним нивоима треба смањити за константан фактор.
Уколико је нижи ниво измењен ажурирањем, онда би требало да буде у стању да ажурира одмах ниво изнад њега, користећи највећи константан број уметања и брисања.

Претходна стратегија патриционисања обезбедјује одрзавање Топ стабла у ${\mathcal {O}}(\log n)$ времену.

Референце

Алструп, Степхен; Холм, Јацоб; Лицхтенберг, Кристиан Де; Тхоруп, Миккел (2005). „Маинтаининг информатион ин фуллy дyнамиц треес wитх топ треес”. АЦМ Трансацтионс он Алгоритхмс. 1 (2): 243—264. С2ЦИД 1317. дои:10.1145/1103963.1103966.
Холм, Јацоб; Де Лицхтенберг, Кристиан; Тхоруп, Миккел (2001). „Полy-логаритхмиц детерминистиц фуллy-дyнамиц алгоритхмс фор цоннецтивитy, минимум спаннинг трее, 2-едге, анд бицоннецтивитy”. Јоурнал оф тхе АЦМ. 48 (4): 723—760. С2ЦИД 7273552. дои:10.1145/502090.502095.
Доналд Кнутх. Тхе Арт оф Цомпутер Программинг: Фундаментал Алгоритхмс, Тхирд Едитион. Аддисон-Wеслеy. . 1997. ИСБН 978-0-201-89683-1. Недостаје или је празан параметар |титле= (помоћ). Сецтион 2.3: Треес, пп. 308-423.
Тхомас Х. Цормен, Цхарлес Е. Леисерсон, Роналд L. Ривест, анд Цлиффорд Стеин. Интродуцтион то Алгоритхмс, Сецонд Едитион. МИТ Пресс анд МцГраw-Хилл. . 2001. ИСБН 978-0-262-03293-3. Недостаје или је празан параметар |титле= (помоћ). Сецтион 10.4: Репресентинг роотед треес, пп. 214-217. Цхаптерс 12-14 (Бинарy Сеарцх Треес, Ред-Блацк Треес, Аугментинг Дата Струцтурес), пп. 253-320.

Додатна литература

„Маинтаининг Информатион ин Фуллy Дyнамиц Треес wитх Топ Треес. Алструп ет ал”. арXив:абс/цс.ДС/0310065  Проверите вредност параметра |арxив= (помоћ).

Спољашње везе

Шаблон:ЦС-Стабла