Внедряване на структурата на данни Rope с помощта на двоични дървета за търсене (splay дървета)

В стандартна реализация на структура на данни Rope, използваща разпръснати дървета, възлите биха били подредени според статистика за ранг, измерваща позицията на всеки един от началото на низа, така че ключовете, които обикновено се намират в дървото за двоично търсене, биха били без значение, нали?

Питам, защото ключовете, показани на графиката по-долу (благодаря на Wikipedia!) са букви, които вероятно биха станали неуникални, след като броят на възлите надхвърли дължината на избраната азбука. Не би ли било по-добре да се използват цели числа или да се избягва използването на ключове?

Структура на данни за въжета

Отделно, може ли някой да ме насочи към добра реализация на логиката за преизчисляване на статистики за ранг след всяка операция?

Предполага се, че ако индексът за разделяне попада в подниза, прикачен към конкретен възел, да речем, между "Hel" и "llo_" на възел E по-горе, вие ще премахнете подниза от E, ще го разделите и ще го прикачите отново като две деца на E. Правилно?

И накрая, след известен брой такива операции, дървото може да се окаже с толкова листа, колкото и букви. Какъв би бил най-добрият начин да следите това и да подрязвате дървото (чрез комбиниране на поднизове), ако е необходимо?

Благодаря!


data-structures binary-search-tree splay-tree
person curlew77    schedule 23.05.2018    source източник
comment
Тези букви не са част от структурата на данните. Те са само там в графиката, за да идентифицират възлите, които се обсъждат в текста.   -  person Matt Timmermans    schedule 24.05.2018

Отговори (1)


arrow_upward
1
arrow_downward

Колкото и да си струва, можете да имплементирате въже с помощта на Splay Trees, като прикачите подниз към всеки възел на дървото за двоично търсене (не само към листовите възли, както е показано по-горе).

Рангът на всеки възел е неговият размер плюс размера на лявото му поддърво. Но когато преизчислявате ранговете по време на splay операции, трябва да запомните да вървите и по клона node.left.right.

Ако всеки възел записва препратка към подниза, който представлява (вж. самия действителен подниз), всичко работи по-бързо. По този начин, когато операция за разделяне попада в рамките на съществуващ възел, вие просто трябва да промените атрибутите на възела, за да отразяват дясната част на подниза, който искате да разделите, след това да добавите друг възел, който да представлява лявата част, и да го обедините с лявото поддърво.

Направено както по-горе, всеки възел записва (в допълнение своите леви, десни и родителски атрибути и т.н.) своя ранг, размер (в знаци) и местоположението на първия символ, който представлява в низа, който се опитвате да промените. По този начин вие всъщност никога не променяте първоначалния низ: вие просто извършвате операциите си върху части от дървото и възпроизвеждате крайния низ, когато сте готови, като го обхождате по ред.

person curlew77    schedule 11.06.2018