Ротација стабла

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

Ротације стабла.

Не постоји конзистентност код различитих дефиниција смера ротација. Неки кажу да смер ротације зависи од стране ка којој су чворови померени, док други кажу да зависи од тога које дете заузима место корена (супротно од прошлог). Овај чланак прихвата приступ да смер зависи од стране на коју се помера.

Илустрација

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

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

Детаљна илустрација

Приказ како се ротације извршавају.

Када је подстабло ротирано, висина стране на коју је примењена ротација повећава се за 1, док се висина супротне стране смањује за 1. Због ове чињенице ротације су корисне за ребалансирање стабла.

Користи се терминологија Корен за родитеља подстабла које се ротира, Пивот за чвор који ће постати нови родитељ, СР за страну на коју је ротација примењена и СС за супротну страну. У дијаграму изнад за чвор Q, СР је C а СС је П. Псеудо код за ротацију је:

Pivot = Koren.SS
Koren.SS = Pivot.SR
Pivot.SR = Koren
Koren = Pivot

Ово је операција константног времена извршавања.

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

Инордер Инваријанта

Ротација ствара инордер обилазак инваријанте бинарног стабла. Ово подразумева да редослед елемената није промењен када је ротација примењена у било ком делу стабла. Инордер обилазак стабала која су приказана горе:

Levo stablo: ((A, P, B), Q, C)        Desno stablo: (A, P, (B, Q, C))

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

def desna_rotacija(koren):
  levo, Q, C = koren
  A, P, B = levo
  return (A, P, (B, Q, C))

Још један начин гледања на ово је:

Десна ротација чвора Q:

Neka je P levo dete od Q.
Namesti da levo dete od Q bude desno dete od P.
Nameti da desno dete od P bude Q.

Лева ротација чвора П:

Neka je Q desno dete od P.
Namesti da desno dete od P bude levo dete od Q.
Namesi da levo dete od Q bude P.

Остале гране су остале исте.

Такође постоје и дупле ротације које су комбинације леве и десне ротације. Дупла лева ротација у X може бити дефинисана као десна ротација десног детета од X праћена левом ротацијом X; слично, дупла десна ротација у X може бити дефинисана као лева ротација левог детете од X праћена десном ротацијом X.

Ротација стабла користи се у многим структурама података, као што су АВЛ стабла, црвено-црна стабла, сплаy стабла, и треап стабла. Захтевају константно време пошто су локалне трансформације: оперишу само на 5 чворова, и не морају да обилазе остатак стабла.

Ребалансирање помоћу ротација

Приказ како ротације доводе до ребалансирања АВЛ стабла.

Стабло може бити ребалансирано помоћу ротација. После ротације, висина стране на коју је примењена ротација повећава се за 1, док се висина друге стране смањује за 1. Стога, ротације могу бити стратешки примењене на чворове којима је разлика висина левог и десног детета већа од 1. Само-балансирајућа бинарна стабла примењују ову операцију аутоматски. Тип стабла које користи ову технику ребалансирања је АВЛ стабло.

Раздаљина ротације

Раздаљина ротације између два бинарна стабла са истим бројем чворова је минималан број ротација потребан да се једно стабло претвори у друго. Са овом раздаљином, низ стабала са н чворова постаје метрички простор: раздаљина је симетрична, позитивна за два различита стабла, и задовољава неједнакост троуглова.

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

Даниел Слеатор, Роберт Тарјан и Wиллиам Тхурстон показали су да је раздаљина ротације између два стабла са н чворова (за н ? 11) највише 2н − 6, и да је бесконачно много парова стабала на овој раздаљини.

Види још

• АВЛ стабла, црвено-црна стабла, и сплаy стабла, врсте бинарног стабла претраге структуре података која користи ротације да одржи баланс стабла.
• Ассоциативитy оф а бинарy оператион меанс тхат перформинг а трее ротатион он ит доес нот цханге тхе финал ресулт.
• Даy–Стоут–Wаррен алгоритам балансира неизбалансирано бинарно стабло претраге.
• Тамари латтице, посебно уређен сет у коме елементи могу бити дефинисани као бинарна стабла а редослед елемената дефинисан је ротацијама.

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

• Јава апплети који демонстрирају ротацију стабла
• Ротација АВЛ стабла - туториал Архивирано на сајту Wayback Machine (6. фебруар 2012) (РТФ) бy Јохн Харгрове