Стек

§1. Стек Пусть дано множество значений V . n }| { n Тогда V = V × V × . . . × V – множество кортежей длины n, составленных из элементов V . Пусть V ? = V 0 ∪ V 1 ∪ V 2 ∪ . . ., V + = V ? \ V 0. z Стек – это структура данных, представляющая кортеж s ∈ V ? с тремя операциями: 1. Push : V ? × V → V ? – добавление элемента x ∈ V в стек; 2. Pop : V + → V ? × V – удаление элемента из стека; 3. StackEmpty : V ? → 2 – проверка стека на пустоту. 1 Говорят, что стек реализует метод доступа к элементам LIFO («Last In – First Out», «последним пришёл – первым вышел»). Реализация стека через массив: стек s представляется структурой hs.data, s.cap, s.topi, где s.data – массив размера s.cap, s.top – размер стека: + * s.cap }| { z •, •, •, • , ◦, ◦, ◦, ◦ . s.data : •, | {z } s.top При добавлении элемента в стек s.top увеличивается на единицу, а при удалении – уменьшается на единицу. Если s.top = s.cap и нужно добавить элемент, то либо генерируют сообщение об ошибке, либо увеличивают размер массива (выделяют новый массив большего размера и копируют в него содержимое старого). Все операции над стеком работают за время O (1). 2 1 2 3 4 6 7 9 10 11 12 14 15 16 17 I n i t S t a c k ( out s , i n n ) s.data ←новый м а с с и в р а з м е р а n s.cap ← n s.top ← 0 S t a c k E m p t y ( i n s ) : empty empty ← s.top = 0 Push ( i n s , i n x ) i f s.top = s.cap : s.data[s.top] ← x s.top ← s.top + 1 e r r o r " переполнение " Pop ( i n s ) : x i f StackEmpty (s ) : s.top ← s.top − 1 x ← s.data[s.top] e r r o r " опустошение " 3 На одном массиве можно реализовать сразу два стека: один будет расти с младших индексов массива, а другой – со старших. В этом случае стек s представляется структурой hs.data, s.cap, s.top1, s.top2i: * z s.data : •, •, •, •, s.cap }| ◦ , ◦, ↑ s.top1 + ◦ , •, •, • . { ↑ s.top2 Все операции над двойным стеком работают за время O (1). Инициализация двойного стека и проверки на пустоту: 1 I n i t D o u b l e S t a c k ( out s , i n n) 2 s.data ←новый м а с с и в р а з м е р а n 3 s.cap ← n 4 s.top1 ← 0 5 s.top2 ← n − 1 6 S t a c k E m p t y 1 ( i n s ) : empty 7 empty ← s.top1 = 0 8 S t a c k E m p t y 2 ( i n s ) : empty 9 empty ← s.top2 = s.cap − 1 4 Добавление и удаление элементов: 1 2 3 4 6 7 8 9 11 12 13 14 16 17 18 19 Push1 ( i n s , i n x ) i f s.top2 < s.top1 : s.data[s.top1] ← x s.top1 ← s.top1 + 1 Push2 ( i n s , i n x ) i f s.top2 < s.top1 : s.data[s.top2] ← x s.top2 ← s.top2 − 1 e r r o r " переполнение " e r r o r " переполнение " Pop1 ( i n s ) : x i f StackEmpty1 (s ) : s.top1 ← s.top1 − 1 x ← s.data[s.top1] Pop2 ( i n s ) : x i f StackEmpty2 (s ) : s.top2 ← s.top2 + 1 x ← s.data[s.top2] e r r o r " опустошение " e r r o r " опустошение " 5 §2. Очередь Очередь – это структура данных, представляющая кортеж q ∈ V ? с тремя операциями: 1. Enqueue : V ? × V → V ? – добавление элемента x ∈ V в очередь; 2. Dequeue : V + → V ? × V – удаление элемента из очереди; 3. QueueEmpty : V ? → 2 – проверка очереди на пустоту. Говорят, что очередь реализует метод доступа к элементам FIFO («First In – First Out», «первым пришёл – первым вышел»). 6 Реализация очереди через массив (кольцевой буфер): очередь q представляется структурой hq.data, q.cap, q.count, q.head, q.taili, где: – q.data – массив размера q.cap, – q.count – количество элементов в очереди, – q.head – индекс в массиве, показывающий, откуда брать элемент для удаления; – q.tail – индекс в массиве, показывающий, куда класть элемент при добавлении. * z q.data : ◦, ◦, q.cap }| + • , •, •, •, ◦ , ◦, ◦, ◦ . { ↑ q.tail ↑ q.head При добавлении элемента индекс q.tail увеличивается на единицу, при удалении элемента индекс q.head увеличивается на единицу. Если индекс становится равным q.cap, он обнуляется. Поэтому возможна ситуация: q.cap }| * z q.data : •, •, ◦ ◦, ◦, ◦, ◦, ↑ q.tail + • , •, • . { ↑ q.head Все операции над очередью работают за время O (1). 7 1 2 3 5 6 8 9 10 11 12 13 15 16 17 18 19 20 I n i t Q u e u e ( out q , i n n ) q.data ←новый м а с с и в р а з м е р а n q.cap ← n , q.count ← 0 , q.head ← 0 , q.tail ← 0 QueueEmpty ( i n q ) : empty empty ← q.count = 0 Enqueue ( i n q , i n x) i f q.count = q.cap : e r r o r " п е р е п о л н е н и е " q.data[q.tail] ← x q.tail ← q.tail + 1 i f q.tail = q.cap : q.tail ← 0 q.count ← q.count + 1 Dequeue ( i n q ) : x i f QueueEmpty ( q ) : e r r o r " о п у с т о ш е н и е " x ← q.data[q.head] q.head ← q.head + 1 i f q.head = q.cap : q.head ← 0 q.count ← q.count − 1 8 Очередь можно реализовать через двойной стек: 1 2 4 5 7 8 10 11 12 13 14 I n i t Q u e u e O n S t a c k ( out s , i n n ) I n i t D o u b l e S t a c k (s , n) QueueEmpty ( i n s ) : empty empty ← S t a c k E m p t y 1 ( s ) and S t a c k E m p t y 2 ( s ) Enqueue ( i n s , i n x) Push1 ( s , x ) Dequeue ( i n s ) : x i f StackEmpty2 (s ) : w h i l e not S t a c k E m p t y 1 ( s ) : P u s h 2 ( s , Pop1 ( s ) ) x ←Pop2 ( s ) 9 §3. Очередь с приоритетами Пусть задано множеств значений V и множество ключей K. Назовём словарной парой элемент множества P = K × V . Пусть на множестве ключей определено отношение строгого порядка /. Очередь c приоритетами – это структура данных, представляющая кортеж q ∈ P ? с пятью операциями: 1. Insert : P ? × P → P ? – добавление пары x ∈ P в очередь; 2. Maximum : P + → P – поиск пары с максимальным ключом (если в q есть несколько пар с максимальным ключом, возвращается одна произвольно выбранная из них пара); 3. ExtractMax : P + → P ? × P – удаление пары с максимальным ключом; 10 4. IncreaseKey : P + × P × K → P + – замена ключа у пары, входящей в очередь, на больший ключ; 5. QueueEmpty : P ? → 2 – проверка очереди на пустоту. Реализация очереди через пирамиду: очередь q представляется структурой hq.heap, q./, q.cap, q.counti, где: • q.heap – массив размера q.cap, составленный из указателей на тройки hindex, k, vi, в которых index – индекс указателя на тройку в массиве q.heap; • q./ – отношение порядка на множестве ключей; • q.count – количество элементов в очереди. 11 Инициализация очереди: 1 2 3 I n i t P r i o r i t y Q u e u e ( out q , i n n , i n / ) q.heap ←новый м а с с и в р а з м е р а n q./ ← / , q.cap ← n , q.count ← 0 Поиск максимального элемента тривиален и выполняется за O (1): 1 2 3 Maximum ( i n q ) : ptr i f q.count = 0 : e r r o r " о ч е р е д ь ptr ← q.heap[0] пуста " Проверка на пустоту очереди: 1 2 QueueEmpty ( i n q ) : empty empty ← q.count = 0 12 Добавление элемента в очередь выполняется за O (lg n), потому что приходится поддерживать выполнение условий пирамиды: 1 2 3 4 5 6 7 8 9 10 I n s e r t ( i n q , i n ptr ) i ← q.count i f i = q.cap : e r r o r " п е р е п о л н е н и е " q.count ← i + 1 q.heap[i] ← ptr w h i l e i > 0 and q.heap[(i − 1)/2].k ( q./ ) q.heap[i].k : q.heap[(i − 1)/2] ↔ q.heap[i] q.heap[i].index ← i i ← (i − 1)/2 q.heap[i].index ← i 13 Удаление максимального элемента выполняется за O (lg n) из-за вызова процедуры Heapify: 1 2 3 4 5 6 7 8 E x t r a c t M a x ( i n q ) : ptr i f q.count = 0 : e r r o r " о ч е р е д ь п у с т а " ptr ← q.heap[0] q.count ← q.count − 1 i f q.count > 0 : q.heap[0] ← q.heap[q.count] q.heap[0].index ← 0 H e a p i f y ( q./ , 0 , q.count , q.heap ) Алгоритм Heapify должен быть слегка модифицирован с тем, чтобы при обмене двух элементов массива обновлять их индексы: P[i] ↔ P[j] P[i].index ← i P[j].index ← j 14 Увеличение ключа у одного из элементов очереди выполняется за O (lg n): 1 2 3 4 5 6 7 8 I n c r e a s e K e y ( i n q , i n ptr , i n k0 ) i ← ptr.index ptr.k ← k0 w h i l e i > 0 and q.heap[(i − 1)/2].k (q./) k0 : q.heap[(i − 1)/2] ↔ q.heap[i] q.heap[i].index ← i i ← (i − 1)/2 ptr.index ← i (Параметр i задаёт индекс элемента в массиве q.heap.) 15 §4. Связанный список Транзитивное замыкание отношения R – это минимальное транзитивное отношение, включающее R. Циклическая перестановка на множестве M – это биекция множества M на себя, транзитивное замыкание которой совпадает с M × M . 0 1 2 3 1 0 3 2 отношение {h0, 0i , h0, 1i , h1, 0i , h1, 1i , h2, 2i , h2, 3i , h3, 2i , h3, 3i}. Поэтому P – не циклическая перестановка. Пример. Транзитивное замыкание перестановки P = ! – это ! 0 1 2 – это 2 0 1 отношение {h0, 0i , h0, 1i , h0, 2i , h1, 0i , h1, 1i , h1, 2i , h2, 0i , h2, 1i , h2, 2i}. Поэтому P – циклическая перестановка. Пример. Транзитивное замыкание перестановки P = 16 Связанный список – это структура данных, представляющая тройку hM, nil, Linki, в которой: – M – конечное непустое множество элементов; – nil ∈ M – элемент, называемый ограничителем; – Link ⊆ M × M – циклическая перестановка. Пусть L – множество связанных списков, V – множество значений, подмножества которого являются множествами элементов списков. Для каждого элемента списка определены две операции: 1. Prev : L × V → V – получение предыдущего элемента списка; 2. Next : L × V → V – получение следующего элемента списка. 17 Мы будем называть Next (hM, nil, Linki , nil) головным элементом, а Prev (hM, nil, Linki , nil) – хвостовым элементом. Определим основные операции над списками: 1. ListEmpty : L → 2 – проверка списка на пустоту; 2. ListLength : L → N – вычисление длины списка (ограничитель не учитывается); 3. ListSearch : L × V → 2 – поиск элемента x; 4. InsertAfter : L × V × V → L – вставка нового элемента после уже существующего элемента; 5. InsertBefore : L × V × V → L – вставка нового элемента до уже существующего элемента; 18 6. InsertBeforeHead : L×V → L – вставка нового элемента перед головным элементом; 7. InsertAfterTail : L × V → L – вставка нового элемента после хвостового элемента. 8. Delete : L × V → L – удаление элемента; 9. DeleteAfter : L×V → L – удаление элемента, следующего за указанным элементов; 10. DeleteBefore : L × V → L – удаление элемента, расположенного перед указанным элементом; 11. DeleteHead : L → L – удаление головного элемента; 12. DeleteTail : L → L – удаление хвостового элемента. 19 §5. Двунаправленный кольцевой список с ограничителем Реализация двунаправленного кольцевого списка с ограничителем: – каждый элемент списка представляется структурой hv, prev, nexti, где v ∈ V , prev – указатель на предыдущий элемент, next – указатель на следующий элемент; – список представляет собой указатель на элемент-ограничитель h?, prev, nexti, где ? – произвольное значение из V (не используется). Инициализация списка, проверка на пустоту и вычисление длины: 1 I n i t D o u b l e L i n k e d L i s t ( out l ) 2 l ← у к а з а т е л ь на новый э л е м е н т 3 l.prev ← l , l.next ← l 4 L i s t E m p t y ( i n l ) : empty 5 empty ← l.next = l 6 L i s t L e n g t h ( i n l ) : len 7 len ← 0 , x ← l 8 w h i l e x.next 6= l : 9 len ← len + 1 10 x ← x.next 20 Поиск элемента с заданным значением возвращает указатель на найденный элемент или указатель на элемент-ограничитель, если ничего не найдено: 1 2 3 4 ListSearch ( in l , in v ): x x ← l.next w h i l e x 6= l and x.v 6= v : x ← x.next Вставка нового элемента y после уже существующего элемента x: 1 2 3 4 5 6 I n s e r t A f t e r ( in x , z ← x.next x.next ← y y.prev ← x y.next ← z z.prev ← y in y) InsertBefore, InsertBeforeHead и InsertAfterTail – аналогично. 21 Удаление элемента x: 1 2 3 4 5 6 7 8 D e l e t e ( i n x) y ← x.prev z ← x.next y.next ← z z.prev ← y −− Для порядка отсоединим x : x.prev ←NULL x.next ←NULL DeleteAfter, DeleteBefore, DeleteHead и DeleteTail – аналогично. Нетрудно сообразить, что операции ListLength и ListSearch работают за время O (n), где n – длина списка. Все остальные операции работают за константное время. Принципиальные отличия списка от массива – отсутствие возможности быстрого доступа к i-тому элементу, но зато размер списка не фиксирован, и, кроме того, вставка и удаление элементов выполняются за константное время. 22 §6. Однонаправленный список Реализация однонаправленного списка: – каждый элемент списка представляется структурой hv, nexti, где v ∈ V , next – указатель на следующий элемент; у хвостового элемента next = NULL. – список представляет собой указатель на первый элемент. Инициализация списка, проверка на пустоту и вычисление длины: 1 I n i t S i n g l e L i n k e d L i s t ( out l ) 2 l ←NULL 4 5 7 8 9 10 11 L i s t E m p t y ( i n l ) : empty empty ← l =NULL L i s t L e n g t h ( i n l ) : len len ← 0 , x ← l w h i l e x 6=NULL : len ← len + 1 x ← x.next 23 Поиск элемента с заданным значением возвращает указатель на найденный элемент или NULL, если ничего не найдено: 1 2 3 4 ListSearch ( in l , in v ): x x←l w h i l e x 6=NULL and x.v 6= v : x ← x.next Вставка нового элемента y после уже существующего элемента x: 1 2 3 4 I n s e r t A f t e r ( in x , z ← x.next x.next ← y y.next ← z in y) Вставка нового элемента y перед головным элементом: 1 2 3 I n s e r t B e f o r e H e a d ( i n / out l , y.next ← l l←y in y) Эффективные реализации InsertBefore и InsertAfterTail невозможны. 24 Удаление элемента, следующего за x (он должен существовать): 1 2 3 4 5 D e l e t e A f t e r ( i n x) y ← x.next x.next ← y.next −− Для порядка отсоединим y : y.next ←NULL Удаление головного элемента (он должен существовать): 1 2 3 4 5 D e l e t e H e a d ( i n / out l ) y←l l ← y.next −− Для порядка отсоединим y : y.next ←NULL Эффективные реализации Delete, DeleteBefore и DeleteTail невозможны. 25 Для однонаправленных списков актуально сочетание операций Search и Delete, позволяющее выполнять поиск и удаление найденного элемента: 1 2 3 4 5 6 7 8 9 10 11 12 S e a r c h A n d D e l e t e ( i n / out l , i n v ) : x y ←NULL x←l w h i l e x 6=NULL : i f x.v = v : i f y =NULL : DeleteHead (l) else : D e l e t e A f t e r (y) return y←x x ← x.next Операции ListLength, ListSearch и SearchAndDelete выполняются за время O (n), где n – длина списка. Операции ListEmpty, InserAfter, InsertBeforeHead, DeleteAfter и DeleteHead – за O (1). 26 §7. Ассоциативный массив Пусть K – множество ключей, на котором задано отношение строгого порядка /, а V – множество значений. Тогда P = K × V – множество словарных пар. Ассоциативный массив (словарь) – это структура данных, представляющая конечное множество M ⊆ P такое, что M : K → V – функция (т.е. каждая словарная пара из M имеет уникальный ключ). Пусть A – множество ассоциативных массивов. Для каждой словарной пары ассоциативного массива определены две операции: 1. Prec : A × P → P – получение предыдущей пары; 2. Succ : A × P → P – получение следующей пары. 27 Определим основные операции над ассоциативными массивами: 1. MapEmpty : A → 2 – проверка массива на пустоту. 2. MapSearch : A × K → 2 – поиск словарной пары с заданным ключом; 3. Lookup : A × K → V – получение значения словарной пары с заданным ключом; 4. Insert : A × P → A – добавление новой словарной пары; 5. Delete : A × K → A – удаление словарной пары с заданным ключом; 6. Reassign : A × P → A – замена значения, связанного с заданным ключом; 28 7. Minimum : A → P – поиск словарной пары с минимальным ключом; 8. Maximum : A → P – поиск словарной пары с максимальным ключом; 9. Sequence : A → P ? – получение отсортированной последовательности входящих в ассоциативный массив словарных пар. §8. Список с пропусками Список с пропусками – это реализация ассоциативного массива, основанная на следующей идее: – отсортированная в соответствии с отношением строгого порядка ≺ последовательность словарных пар представляется в виде m однонаправленных списков, пронумерованных от 0 до m − 1; – в список 0 входят абсолютно все словарные пары, в список 1 входит приблизительно каждая вторая словарная пара, в список 2 – приблизительно каждая четвёртая, и т.д.; – для поиска пары с заданным ключом мы сначала двигаемся по списку m − 1, затем «спускаемся» на уровень ниже и двигаемся по списку m − 2, и т.д. На каждом уровне «скорость» движения падает приблизительно в два раза. 2: 1: 0: ? 2 5 6 7 15 21 25 30 35 47 29 Замечание. Если словарная пара входит в список с номером i, то она обязана входить также во все списки с номерами от 0 до i − 1. Каждый элемент списка с пропусками представляется в виде структуры hk, v, nexti, где hk, vi – словарная пара, next – массив указателей размера m. Если next [i] = NULL, то элемент либо не входит в список с номером i, либо он – последний в списке с номером i. Сам список представляет собой указатель на дополнительный служебный элемент, который играет роль элемента-ограничителя в двунаправленном списке. 30 Инициализация списка с пропусками, проверка на пустоту: 1 2 3 4 5 6 7 9 10 I n i t S k i p L i s t ( i n m , out l ) l ←новый э л е м е н т l.next ←новый м а с с и в у к а з а т е л е й i←0 while i < m: l.next[i] ←NULL i←i+1 размера m MapEmpty ( i n l ) : empty empty ← l.next[0] =NULL Операция получения следующей словарной пары: 1 2 Succ ( i n x ) : y y ← x.next[0] Операция Prec допускает эффективную реализацию только на двунаправленных списках с пропусками. 31 Операция Skip используется при реализации других операций над списками с пропусками. Она формирует массив указателей p размера m такой, что p [i] – указатель на элемент в списке с номером i, после которого может располагаться элемент с ключом k. Элемент p [i] выбирается таким образом, что: – p [i] .k / k, либо p [i] = l; – ¬ (p[i].next[i].k / k), либо p [i] .next [i] = NULL. 1 2 3 4 5 6 7 8 S k i p ( i n l , i n m , i n / , i n k , i n / out p ) x←l i←m−1 while i ≥ 0: w h i l e x.next[i] 6=NULL and x.next[i].k / k : x ← x.next[i] p[i] ← x i←i−1 Можно показать, что алгоритм Skip в среднем работает за время O (lg n), если размер m > lg n. 32 Поиск в списке с пропусками: 1 2 3 4 5 7 8 9 10 11 12 13 M a p S e a r c h ( i n l , i n m , i n / , i n k ) : verdict p ←новый м а с с и в у к а з а т е л е й р а з м е р а m Skip (l , m , / , k , p) x ← S u c c ( p[0] ) verdict ← x 6=NULL and x.k = k Lo o k u p ( i n l , i n m , i n / , i n k ) : v p ←новый м а с с и в у к а з а т е л е й р а з м е р а m Skip (l , m , / , k , p) x ← S u c c ( p[0] ) i f x =NULL o r x.k 6= k : panic v ← x.v При вставке нового элемента в список с пропусками количество t списков, в которые будет входить новый элемент, определяется псевдослучайным образом. Если r – псевдослучайное целое число, то t = 1 + max {x | r = 0 (mod 2x) }. 33 1 2 3 4 5 7 8 9 10 11 12 13 14 15 16 17 18 I n s e r t ( in l , in m , in / , in k , in v) p ←новый м а с с и в у к а з а т е л е й р а з м е р а m Skip (l , m , / , k , p) i f p[0].next[0] 6=NULL and p[0].next[0].k = k : panic x ←новый э л е м е н т x.next ←новый м а с с и в у к а з а т е л е й р а з м е р а m r ← r a n d ( ) ∗ 2 −− чётное псевдослучайное целое число i←0 w h i l e i < m and r mod 2 = 0 : x.next[i] ← p[i].next[i] p[i].next[i] ← x i←i+1 r ← r/2 while i < m: x.next[i] ←NULL i←i+1 34 Удаление элемента с ключом k из списка с пропусками: 1 2 3 4 5 6 8 9 10 11 Delete ( in l , in m , in / , in k) p ←новый м а с с и в у к а з а т е л е й Skip (l , m , / , k , p) x ← S u c c ( p[0] ) i f x =NULL o r x.k 6= k : panic размера m i←0 w h i l e i < m and p[i].next[i] = x : p[i].next[i] ← x.next[i] i←i+1 35 Замена значения с заданным ключом, получение минимального элемента и формирование отсортированной последовательности элементов: 1 2 3 4 5 6 7 9 10 12 13 14 15 16 Reassign ( in l , in m , in / , in k , in v) p ←новый м а с с и в у к а з а т е л е й р а з м е р а m Skip (l , m , / , k , p) x ← S u c c ( p[0] ) i f x =NULL o r x.k 6= k : panic x.v ← v Minimum ( i n l ) : x x ←Succ (l) S e q u e n c e ( i n l , i n / out queue ) x ←Succ (l) w h i l e x 6=NULL : E n q u e u e ( queue , x ) x ←Succ (x) 36 §9. Бинарное дерево поиска Бинарное дерево поиска является ещё одной реализацией ассоциативного массива. Бинарное дерево состоит из вершин, соединённых направленными дугами. В каждой вершине хранится одна словарная пара. Из одной вершины может исходить не более двух дуг, поэтому у вершины не может быть более двух дочерних вершин. Вершины, из которых не исходит ни одной дуги, называются листьями. Единственная вершина дерева, в которую не входит ни одна дуга, называется корнем. Высота дерева – это максимальное количество дуг между корнем и листом дерева. 37 Для каждой вершины дерева одна дочерняя вершина, если она существует, является левой вершиной, а другая, если существует, является правой вершиной. Вершина по отношению к своим дочерним вершинам является родительской вершиной. Бинарное дерево поиска обладает важным свойством: если k – ключ некоторой вершины дерева, то ключи всех вершин в её левом поддереве предшествуют k, и, кроме того, k предшествует ключам всех вершин в её правом поддереве. 10 20 3 1 2 7 25 22 38 Вершину дерева представляют структурой hk, v, parent, lef t, righti, в которой: – hk, vi ∈ P – словарная пара; – parent – указатель на родительскую вершину; – lef t и right – указатели на левую и правую дочерние вершины. Если вершина x – корень, то x.parent = NULL. Если вершина x не имеет левой дочерней вершины, то x.lef t = NULL, а если не имеет правой дочерней вершины, то x.right = NULL. Само дерево представляется указателем на корень. В случае пустого дерева этот указатель равен NULL. Инициализация дерева и проверка на пустоту тривиальны: 1 2 4 5 I n i t B i n a r y S e a r c h T r e e ( out t ) t ←NULL MapEmpty ( i n t ) : empty empty ← t =NULL 39 Операция поиска словарной пары с минимальным ключом выполняется путём спуска от корня до листа по дугам, ведущим к левым дочерним вершинам. Для пустого дерева Minimum будет возвращать NULL. 1 2 3 4 5 6 7 Minimum ( i n t ) : x i f t =NULL : x ←NULL else : x←t w h i l e x.lef t 6=NULL : x ← x.lef t Операция Maximum реализуется аналогично. Время выполнения операций Minimum и Maximum – O (h), где h – высота дерева. Утверждение. Minimum всегда возвращает указатель на вершину, не имеющую левой дочерней вершины, а Maximum всегда возвращает указатель на вершину, не имеющую правой дочерней вершины. Справедливость утверждения прямо следует из алгоритма. 40 Операция получения следующей словарной пары работает за время O (h): 1 Succ ( i n x ) : y 2 i f x.right 6=NULL : 3 y ←Minimum ( x.right ) 4 else : 5 y ← x.parent 6 w h i l e y 6=NULL and x = y.right : 7 x←y 8 y ← y.parent Иллюстрация. (случай, когда x.right = NULL) y2 ··· y1 ··· x ··· Операция Prec реализуется аналогично. 41 Утверждение. Если вершина x в бинарном дереве поиска имеет правую дочернюю вершину, то вершина Succ(x) не имеет левой дочерней вершины. Действительно, рассмотрим вершину x, у которой x.right 6= NULL. Тогда, согласно алгоритму Succ, за вершиной x будет следовать вершина Minimum(x.right), у которой, как известно, нет левой дочерней вершины. Утверждение. Если вершина x в бинарном дереве поиска имеет левую дочернюю вершину, то вершина Prec(x) не имеет правой дочерней вершины. Доказывается аналогично. 42 Пример. (Вершина 10 имеет правую дочернюю вершину 20, значит вершина 12=Succ(10) не имеет левой дочерней вершины.) 10 ··· 20 ··· 18 ··· 15 12 ··· 14 43 Поиск в бинарном дереве работает за время O (h): 1 2 3 4 5 6 7 9 10 12 13 14 15 16 Descend ( i n t , i n / , i n k ) : x x←t w h i l e x 6=NULL and x.k = 6 k: i f k / x.k : x ← x.lef t else : x ← x.right M a p S e a r c h ( i n t , i n / , i n k ) : verdict verdict ← D e s c e n d ( t , / , k ) = 6 NULL Lookup ( i n t , i n / , i n k ) : v x ←Descend (t , / , k ) i f x =NULL : panic v ← x.v 44 Вставка новой словарной пары в бинарное дерево работает за время O (h): 1 I n s e r t ( i n / out t , in / , in k , in v) 2 y ← н о в а я вершина , y.k ← k , y.v ← v 3 y.parent ←NULL , y.lef t ←NULL , y.right ←NULL , 4 i f t =NULL : 5 t←y 6 else : 7 x←t 8 loop : 9 i f x.k = k : 10 panic 11 i f k / x.k : 12 i f x.lef t =NULL : 13 x.lef t ← y , y.parent ← x 14 break 15 x ← x.lef t 16 else : 17 i f x.right =NULL : 18 x.right ← y , y.parent ← x 19 break 20 x ← x.right 45 Вспомогательная операция ReplaceNode меняет в бинарном дереве вершину x (вместе с растущим из неё поддеревом) на вершину y (которая тоже может быть корнем поддерева). Операция допускает y = NULL: в этом случае происходит удаление поддерева с корнем в x. 1 2 3 4 5 6 7 8 9 10 11 12 R e p l a c e N o d e ( i n / out t , i n x , i n y ) if x = t: t←y i f y 6=NULL : y.parent ←NULL else : p ← x.parent i f y 6=NULL : y.parent ← p i f p.lef t = x : p.lef t ← y else : p.right ← y Нетрудно заметить, что операция ReplaceNode в общем случае не сохраняет свойство бинарного дерева поиска. 46 При удалении вершины x из бинарного дерева возможны три случая: 1. Вершина x – листовая. Для удаления достаточно обнулить указатель на неё у её родительской вершины: ReplaceNode(t,x,NULL). 2. У вершины x есть одна дочерняя вершина a. Для удаления достаточно заменить x на a: ReplaceNode(t,x,a). До (a – левая) p x До (a – правая) p x a ··· a ··· a ··· После p ··· ··· ··· 47 3. У вершины x есть две дочерние вершины a и b. Пусть y = Succ (x). Удалим вершину y из дерева, воспользовавшись схемой из случая 2 (у вершины y нет левой дочерней вершины). p p p x x a a b ··· ··· ··· ··· ··· ··· b ··· ··· c ··· d a b c y y d ··· ··· c ··· d ··· ··· ··· Присоединим вершины a и b вместе с растущими из них поддеревьями к вершине y. При этом a становится левой дочерней (a / x / y), а b – правой дочерней (y / b). Заменим в дереве x на y. 48 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 D e l e t e ( i n / out t , i n / , i n k ) x ←Descend (t , / , k ) i f x =NULL : panic i f x.lef t =NULL and x.right =NULL : R e p l a c e N o d e ( t , x , NULL ) e l s e i f x.lef t =NULL : R e p l a c e N o d e ( t , x , x.right ) e l s e i f x.right =NULL : R e p l a c e N o d e ( t , x , x.lef t ) else : y ←Succ (x) R e p l a c e N o d e ( t , y , y.right ) x.lef t.parent ← y y.lef t ← x.lef t i f x.right 6=NULL : x.right.parent ← y y.right ← x.right ReplaceNode (t , x , y) Удаление вершины выполняется за время O (h). 49 Замена значения с заданным ключом: 1 2 3 4 5 R e a s s i g n ( i n / out t , i n / , x ←Descend (t , / , k ) i f x =NULL : panic x.v ← v in k , in v) Рекурсивное формирование отсортированной последовательности вершин бинарного дерева: 1 2 3 4 5 S e q u e n c e ( i n t , i n / out queue ) i f t 6=NULL : S e q u e n c e ( t.lef t , queue ) E n q u e u e ( queue , t ) S e q u e n c e ( t.right , queue ) 50 Нерекурсивное формирование отсортированной последовательности вершин бинарного дерева: 1 2 3 4 5 6 7 8 9 10 11 12 S e q u e n c e ( i n t , i n / out queue ) I n i t S t a c k (s , . . . ) x←t loop : w h i l e x 6=NULL : Push ( s , x ) x ← x.lef t i f StackEmpty (s ) : break x ←Pop ( s ) E n q u e u e ( queue , x ) x ← x.right В этом алгоритме предполагается, что либо мы знаем общее количество вершин в дереве, либо стек умеет расти во время работы алгоритма. 51 Для реализации балансировки бинарного дерева нам потребуется операция поворота поддерева, растущего из некоторой вершины. Если x – вершина бинарного дерева, и y – её правая дочерняя вершина, то поворот поддерева с корнем x влево модифицирует дерево таким образом, что y становится родительской вершиной для x. До поворота p После поворота p x y a ··· y x c b c a b ··· ··· ··· ··· ··· 52 1 2 3 4 5 6 7 8 9 10 11 R o t a t e L e f t ( i n / out t , i n x ) y ← x.right i f y =NULL : panic ReplaceNode (t , x , y) b ← y.lef t i f b 6=NULL : b.parent ← x x.right ← b x.parent ← y y.lef t ← x Операция правого поворота RotateRight реализуется аналогично. 53 §10. АВЛ-дерево Г.М. Адельсон-Вельский, Е.М. Ландис: Бинарное дерево поиска называется сбалансированным, если высоты дочерних поддеревьев каждой из его вершин отличаются не более, чем на единицу. (Такие деревья ещё называют АВЛ-деревьями). Вершина АВЛ-дерева представляют как hk, v, balance, parent, lef t, righti, где balance – разность высот правого и левого поддеревьев. Пример. (в вершинах дерева изображены пары hk, balancei) h8, 1i h4, −1i h1, 0i h20, 1i h15, 0i h25, −1i h23, 0i 54 Пусть дерево с корнем x поворачивается влево. Посмотрим, как меняются балансы в вершинах дерева при повороте. До поворота x a ··· После поворота y y x c b c a b ··· ··· ··· ··· ··· Очевидно, что поддеревья с корнями a, b и c не меняются, и балансы всех входящих в них вершин сохраняются. 55 Сначала разберёмся с балансом вершины x. До поворота x a ··· После поворота y x y c b c a b ··· ··· ··· ··· ··· x.balance2 = height (b) − height (a). Если y.balance1 ≤ 0, то x.balance1 = (1 + height (b)) − height (a), x.balance2 = x.balance1 − 1. Если y.balance1 > 0, то x.balance1 = (1 + height (c)) − height (a), height (c) = height (b) + y.balance1, x.balance1 = (1 + height (b) + y.balance1) − height (a), x.balance2 = x.balance1 − 1 − y.balance1. 56 Теперь посчитаем новый баланс вершины y. До поворота x a ··· После поворота y y x c b c a b ··· ··· ··· ··· ··· y.balance1 = height (c) − height (b). Если x.balance2 ≥ 0, то y.balance2 = height (c) − (1 + height (b)) = y.balance1 − 1. Если x.balance2 < 0, то y.balance2 = height (c) − (1 + height (a)), height (a) = height (b) − x.balance2, y.balance2 = height (c)−(1 + height (b) − x.balance2) = y.balance1−1+x.balance2. 57 Таким образом, в алгоритм RotateLeft для АВЛ-дерева нужно дописать изменение балансов вершин x и y: 1 2 3 4 5 6 7 8 R o t a t e L e f t ( i n / out t , i n x ) ... x.balance ← x.balance − 1 i f y.balance > 0 : x.balance ← x.balance − y.balance y.balance ← y.balance − 1 i f x.balance < 0 : y.balance ← y.balance + x.balance 58 Если воспроизвести те же рассуждения для поворота вправо, мы получим следующее дополнение к алгоритму RotateRight: 1 2 3 4 5 6 7 8 R o t a t e R i g h t ( i n / out t , i n x ) ... x.balance ← x.balance + 1 i f y.balance < 0 : x.balance ← x.balance − y.balance y.balance ← y.balance + 1 i f x.balance > 0 : y.balance ← y.balance + x.balance Обратите внимание: алгоритмы RotateLeft и RotateRight работают несколько неправильно – они не изменяют балансы родительских вершин. В дальнейшем мы увидим, что это и не нужно. 59 При добавлении новой словарной пары к АВЛ-дереву оно может перестать быть сбалансированным. Однако, мы покажем, что такое дерево всегда можно сбалансировать за один или два поворота. Пример. (балансировка за один поворот) Исходное дерево После добавления вершины с ключом 1 h10, −1i h5, −1i h3, 0i h16, 0i h10, −2i h5, −2i h3, −1i h16, 0i После поворота поддерева, растущего из 5, вправо h10, −1i h3, 0i h1, 0i h16, 0i h5, 0i h1, 0i 60 Пример. (балансировка за два поворота) Исходное дерево h10, −1i h5, −1i h3, 0i h16, 0i После добавления вершины с ключом 4 h10, −2i h5, −2i h3, 1i h4, 0i После поворота поддерева, растущего из 3, влево После поворота поддерева, растущего из 5, вправо h10, −2i h16, 0i h5, −2i h4, −1i h16, 0i h10, −1i h4, 0i h3, 0i h16, 0i h5, 0i h3, 0i 61 Утверждение. Если после добавления новой вершины к АВЛ-дереву мы получаем несбалансированное дерево, то его можно сбалансировать за один или два поворота, причём высота дерева после балансировки будет совпадать с его высотой до добавления новой вершины. Докажем это утверждение индуктивно по высоте дерева, какой она была до добавления новой вершины. 1. Высота h = 0. Дерево состоит из единственной вершины. Добавление новой вершины не может сделать его несбалансированным, поэтому утверждение тривиально верно. 62 2. Высота h = 1. Случаи, когда после добавления вершины дерево оказалось несбалансированным и для балансировки требуется один поворот: Исходное дерево hx, −1i hy, 0i hx, 1i hy, 0i После добавления вершины z hx, −2i hy, −1i hz, 0i hx, 2i hy, 1i hz, 0i После поворота поддерева, растущего из x... ...вправо hy, 0i hz, 0i hx, 0i ...влево hy, 0i hx, 0i hz, 0i В итоге дерево сбалансировано и его высота не поменялась. ... 63 2. Высота h = 1. ... Случаи, когда после добавления вершины дерево оказалось несбалансированным и для балансировки требуется два поворота: Исходное После После поворота После поворота дерево добавления поддерева, поддерева, вершины z растущего из y... растущего из x... hx, −1i hx, −2i ...влево ...вправо hx, −2i hz, 0i hy, 0i hy, 1i hz, −1i hy, 0i hx, 0i hz, 0i hy, 0i hx, 1i hx, 2i ...вправо ...влево hx, 2i hz, 0i hy, 0i hy, −1i hz, 1i hx, 0i hy, 0i hz, 0i hy, 0i В итоге дерево сбалансировано и его высота не поменялась. (Обратите внимание: поворот вокруг y не влияет на баланс x.) 64 3. Предположим, что для деревьев высоты меньше h утверждение справедливо. Докажем, что оно справедливо и для деревьев высоты h. Пусть имеется дерево высоты h с корнем x. Так как дерево сбалансировано, и h > 1, то у вершины x есть две дочерние вершины a и b. Добавим в дерево новую вершину z. Рассмотрим случай, когда она оказывается в поддереве a. Случай, когда z оказывается в поддереве b, мы рассматривать не будем, потому что он во всём аналогичен. x Если поддерево a в результате добавления z станет несбалансированным, то, учитывая, что его высо- a b ...z ... ... та меньше h, его можно сбалансировать одним или двумя поворотами. При этом после балансировки оно станет прежней высоты, и баланс дерева x не изменится. 65 Поэтому будем считать, что поддерево a осталось сбалансированным, и балансировка нарушена только в вершине x. Обратим внимание на высоту деревьев a и b. Если бы высота дерева b превышала или хотя бы была равна высоте дерева a, то при добавлении в дерево a новой вершины z баланс в вершине x никак не мог бы быть нарушен. Тем самым, высота a больше высоты b. x:h+1 Так как до добавления вершины z дерево x было сбалансировано, а после добавления стало a:h b:h−2 ...z ... ... несбалансировано, то высота a была ровно на 1 больше высоты b. Итак, height1 (a) = h − 1, height (b) = h − 2. Соответственно, после добавления z высота a выросла на 1 и стала равна height2 (a) = h. (Если бы высота a не выросла, то баланс в x не был бы нарушен.) 66 Так как h > 1, то height1 (a) > 0. После добавления z дерево a осталось сбалансировано, и его высота выросла. Поэтому высоты левого и правого поддеревьев вершины a до добавления z были равны, и тем самым у вершины a есть две дочерние вершины c и d. В зависимости от того, в какое поддерево вершины a попадает новая вершина z, возможны два случая: x:h+1 x:h+1 a:h a:h b:h−2 c:h−1 d:h−2 ...z ... ... ... b:h−2 c:h−2 d:h−1 ... ...z ... ... В первом случае баланс вершины a равен −1, и, как мы увидим далее, для балансировки дерева x потребуется один поворот. Во втором случае баланс вершины a равен 1, и потребуется два поворота. 67 В первом случае балансировка выполняется путём правого поворота дерева x: До балансировки После поворота дерева x вправо a:h x:h+1 a:h x:h−1 c:h−1 d:h−2 ...z ... ... b:h−2 c:h−1 ... ...z ... d:h−2 b:h−2 ... ... В итоге дерево сбалансировано (баланс в корне равен 0), и его высота не поменялась. 68 Рассмотрим второй случай: x:h+1 a:h b:h−2 c:h−2 d:h−1 ... ...z ... ... После добавления вершины z дерево d осталось сбалансированным. Если бы это было не так, мы бы применили к нему процедуру балансировки (согласно гипотезе индукции), в результате которой его высота бы не изменилась, и баланс в вершине x остался бы прежним. Кроме того, высота дерева d после добавления z выросла, а это означает, что поддеревья дерева d до добавления z имели одинаковую высоту h − 3. (Да, при h = 2 их высота равна -1, то есть они просто-напросто пусты.) 69 Пусть d имеет два дочерних поддерева e и f , которые могут быть пусты. Отразим это на схеме: x:h+1 a:h b:h−2 ... d:h−1 c:h−2 ... e :≤ h − 2 f :≤ h − 2 z? z? Мы не знаем, в какое поддерево – e или f – попадёт вершина z. Для дальнейших рассуждений это неважно. Главное, что высота деревьев e и f после добавления z не превышает h − 2. 70 Выполним левый поворот дерева a. До балансировки После поворота дерева a влево x:h+1 x:h+1 d:h a:h b:h−2 b:h−2 d:h−1 ... a:h−1 ... f :≤ h − 2 c:h−2 ... e :≤ h − 2 f :≤ h − 2 z? z? c:h−2 e :≤ h − 2 ... z? z? Обратите внимание, что высота дерева a до поворота равна высоте дерева d после повортота. Значит поворот не влияет на баланс вершины x, и мы можем использовать RotateLeft. 71 Теперь выполним правый поворот дерева x. После первого поворота После поворота дерева x вправо x:h+1 d:h d:h a:h−1 b:h−2 ... a:h−1 c:h−2 e :≤ h − 2 ... z? x:h−1 f :≤ h − 2 c:h−2 e :≤ h − 2 f :≤ h − 2 b:h−2 z? ... z? z? ... В итоге дерево сбалансировано (баланс в корне равен 0), и его высота осталась прежней. Утверждение доказано. 72 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 I n s e r t A V L ( i n / out t , i n / , i n k , i n v ) a ← I n s e r t (t , / , k , v) a.balance ← 0 loop : x ← a.parent i f x =NULL : b r e a k i f a = x.lef t : x.balance ← x.balance − 1 i f x.balance = 0 : b r e a k i f x.balance = −2 : i f a.balance = 1 : R o t a t e L e f t ( t , a ) RotateRight (t , x) break else : x.balance ← x.balance + 1 i f x.balance = 0 : b r e a k i f x.balance = 2 : i f a.balance = −1 : R o t a t e R i g h t ( t , a ) R o t a t e L e f t (t , x) break a←x 73 §11. Таблица с прямой адресацией При малой мощности множества ключей допустим очень простой способ реализации ассоциативного массива в виде так называемой таблицы с прямой адресацией. Пусть M : K −→ V – ассоциативный массив, и задано взаимнооднозначное соответствие g : K −→ Nm, где m = |K|. При этом биекция g выбрана таким образом, что k1 / k2 ⇔ g (k1) < g (k2). Назовём таблицей с прямой адресацией массив T размера m такой, что ∀k ∈ K, T [g (k)] =  NULL, v, если @ hk, vi ∈ M ; если ∃ hk, vi ∈ M. Здесь NULL – специальное значение, которое обозначает, что в словаре отсутствует словарная пара с данным ключом. 74 Реализация операций над таблицей с прямой адресацией тривиальна: 1 I n i t D i r e c t A d d r e s s T a b l e ( i n m , out t ) 2 t ←новый м а с с и в у к а з а т е л е й р а з м е р а m 4 5 6 7 8 9 11 12 14 15 16 17 MapEmpty ( i n t , i n m ) : empty i←0 while i < m: i f t[i] 6=NULL : r e t u r n i←i+1 return true false M a p S e a r c h ( i n t , i n g , i n k ) : verdict verdict ← t[g(k)] 6=NULL Lookup ( i n t , i n g , v ← t[g(k)] i f v =NULL : panic in k ): v Операция MapEmpty выполняется за O (m), если не хранить количество занятых элементов. 75 Операции Succ и Minimum (а также Prec и Maximum, которые реализуются аналогично) выполняются за O (m). 1 2 3 4 5 6 7 9 10 11 12 13 14 15 S u c c ( i n t , i n m , i n g , i n k ) : k0 i ← g(k) + 1 w h i l e i < m and t[i] =NULL : i←i+1 if i = m: panic k0 ← g −1(i) Minimum ( i n t , i n m , i n g ) : k i←0 w h i l e i < m and t[i] =NULL : i←i+1 if i = m: panic k ← g −1(i) 76 Операции Insert, Delete и Reassign выполняются за константное время: 1 2 3 4 5 7 8 9 10 11 13 14 15 16 17 I n s e r t ( in t , in g , i ← g(k) i f t[i] 6=NULL : panic t[i] ← v in k , Delete ( in t , in g , i ← g(k) i f t[i] =NULL : panic t[i] ←NULL in k) Reassign ( in t , in g , i ← g(k) i f t[i] =NULL : panic t[i] ← v in v) in k , in v) 77 Операция Sequence выполняется за O (m): 1 2 3 4 5 6 S e q u e n c e ( i n t , i n m , i n g , i n / out queue ) i←0 while i < m: i f t[i] 6=NULL : E n q u e u e ( queue , hg −1(i), t[i]i ) i←i+1 78 §12. Хеш-таблица Основным отличием хеш-таблицы от таблицы с прямой адресацией является то, что в ней не существует взаимнооднозначного соответствия между ключами и индексами элементов массива, то есть несколько ключей могут отображаться в один и тот же элемент. Пусть K – множество ключей. Мы будем называть хеш-функцией отображение h : K −→ Nm, где m < |K|. При этом случай, когда k1 6= k2, но h (k1) = h (k2), называется коллизией. В силу возможности коллизий каждый элемент хеш-таблицы должен обеспечивать возможность хранения сразу нескольких словарных пар. Пусть M : K −→ V – ассоциативный массив, и задана хеш-функция h : K −→ Nm. Тогда хеш-таблица – это массив T размера m такой, что ∀i ∈ Nm : T [i] = {hk, vi | h (k) = i}. 79 Качественная хеш-функция должна равномерно распределять словарные пары по элементам хеш-таблицы. В этом случае время поиска в хештаблице равно O (1 + n/m), где n – количество словарных пар, хранящихся в таблице. При построении хеш-функции нужно руководствоваться следующими принципами: • функция не должна коррелировать с закономерностями, которым могут подчиняться существующие данные; • для вычисления функции должен использоваться весь ключ целиком. Естественно, что хеш-функция не сохраняет порядка на множестве ключей: k1 / k2 < h (k1) < h (k2). Поэтому операции Prec, Succ, Minimum, Maximum и Sequence не могут быть реализованы для хеш-таблицы. 80 Пример. Пусть множество ключей – это множество строк. Неудачные хеш-функции: 1. h (k) возвращает длину строки k (очевидно, что в общем случае длины строк не равновероятны; кроме того, для вычисления h (k) используется не вся информация, содержащаяся в ключе – игнорируются конкретные значения символов строки); 2. h (k) возвращает код первого символа строки k (недостаток: для вычисления хеш-функции не используются остальные символы строки); ! 3. h (k) = len(k)−1 P k [i] mod m, где m – количество элементов в хеш- i=0 таблице (недостаток: h (k) не зависит от перестановки символов в строке). Удачная хеш-функция: ! h (k) = len(k)−1 P pi+1 · k [i] i=0 mod m, где p – простое число. 81 Рассмотрим реализацию основных операций над хеш-таблицей: 1 I n i t H a s h T a b l e ( i n m , out t ) 2 t ←новый м а с с и в о д н о н а п р в л е н н ы х с п и с к о в р а з м е р а m 4 5 6 7 8 9 11 12 14 15 16 17 MapEmpty ( i n t , i n m ) : empty i←0 while i < m: i f not L i s t E m p t y ( t[i] ) : i←i+1 return true return false M a p S e a r c h ( i n t , i n h , i n k ) : verdict verdict ← L i s t S e a r c h ( t[h(k)] , k ) 6=NULL Lookup ( i n t , i n h , i n k ) : v p ← L i s t S e a r c h ( t[h(k)] , k ) i f p =NULL : p a n i c v ← p.v Здесь операция ListSearch выполняет поиск элемента списка словарных пар по ключу. 82 1 2 3 4 5 7 8 10 11 12 13 14 I n s e r t ( in t , in h , in k , in v) i ← h(k) i f L i s t S e a r c h ( t[i] , k ) 6=NULL : panic I n s e r t B e f o r e H e a d ( t[i] , hk, vi ) Delete ( in t , in h , in k) S e a r c h A n d D e l e t e ( t[h(k)] , k ) Reassign ( in t , in h , in k , in v) p ← L i s t S e a r c h ( t[h(k)] , k ) i f p =NULL : panic p.v ← v Здесь операция SearchAndDelete должна паниковать в случае, если элемент списка с заданным ключом не найден. 83 §13. Бор Пусть ключами ассоциативного массива являются строки, т.е. в общем случае конечные последовательности натуральных чисел из алфавита Nm. (В §§13–14 буква m будет обозначать размер алфавита.) Если отказаться от модели сравнений и разрешить операциям доступ к ключам, то такой ассоциативный массив можно реализовать в виде бора. Бор (trie) – это дерево, каждая дуга которого помечена символом из алфавита Nm. При этом метки всех дуг, исходящих из одной вершины, должны различаться. Каждая вершина бора соответствует некоторой строке, причём эта строка не хранится в вершине, а определяется последовательностью меток дуг, ведущих от корня бора к этой вершине. Очевидно, что корень бора соответствует пустой строке. 84 Пример. (Бор, содержащий словарные пары hant, 20i, hape, 5i, hapex, 30i, happle, 10i, haxe, 30i, hone, 25i.) t n p a 20 5 x 30 e p l e 10 x e o 30 n e 25 Вершину бора представляют структурой hv, parent, arcsi, в которой: – v – указатель на значение, привязанное к строке, соответствующей вершине (указатель v = NULL, если вершина является служебной); – parent – указатель на родительскую вершину; – arcs – массив указателей на дочерние вершины (если из вершины исходит дуга, помеченная символом x, то arcs [x] содержит указатель на вершину, в которую эта дуга входит; в противном случае arcs [x] = NULL). 85 Рассмотрим реализацию основных операций над бором. Инициализация бора заключается в создании корневой вершины, имеющей статус служебной (v = NULL): 1 I n i t T r i e ( out t ) 2 t ← н о в а я вершина Замечание. Запись «новая вершина» означает выделение памяти для структуры вершины и заполнение этой памяти нулями. Бор пуст тогда и только тогда, когда его корень – служебный, и из него не исходит ни одной дуги: 1 MapEmpty ( i n t ) : empty 2 i f t.v 6=NULL : r e t u r n f a l s e 3 i←0 4 while i < m: 5 i f t.arcs[i] 6=NULL : r e t u r n f a l s e 6 i←i+1 7 return true 86 Вспомогательная операция Descend выполняет спуск от корня бора до вершины x, соответствующей максимальному префиксу строки k, присутствующему в боре. Операция возвращает указатель на вершину x и длину соответствующего ей префикса строки k. 1 2 3 4 5 6 7 Descend ( i n t , i n k ) : x , i x←t, i←0 w h i l e i < len(k) : y ← x.arcs[k[i]] i f y =NULL : b r e a k x←y i←i+1 Операция Descend аналогична одноимённой операции бинарного дерева поиска, но работает за время O (len (k)). Тем самым, спуск по бору не зависит от количества словарных пар в нём. Отметим, что высота бора равна длине самого длинного ключа в нём, и бор не нуждается в балансировке. 87 Операции MapSearch и Lookup для бора используют в своей работе операцию Descend и, соответственно, тоже работают за время O (len (k)): 1 2 3 5 6 7 8 M a p S e a r c h ( i n t , i n k ) : verdict x, i ← D e s c e n d ( t , k ) verdict ← i = len(k) and x.v 6=NULL Lo o k u p ( i n t , i n k ) : v x, i ← D e s c e n d ( t , k ) i f i 6= len(k) o r x.v =NULL : v ← x.v panic Обратите внимание на то, что Descend по ключу k может вернуть указатель на служебную вершину, не соответствующую ни одной словарной паре. Поэтому приходится проверять, пусто ли поле v найденной вершины. 88 Операция Minimum возвращает указатель на вершину, ключ которой лексикографически наименьший. Для этого выполняется спуск от корня бора до первой неслужебной вершины по самым левым дугам: 1 2 3 4 5 6 7 8 9 Minimum ( i n t ) : x i f t.v 6=NULL : return t i←0 while i < m: i f t.arcs[i] 6=NULL : r e t u r n Minimum ( t.arcs[i] ) i←i+1 r e t u r n NULL Время работы операции Minimum – O (h), где h – высота бора. Отметим, что в операции Minimum используется хвостовая рекурсия, которая может быть элементарно превращена в цикл. 89 Операция Maximum возвращает указатель на вершину, ключ которой лексикографически наибольший. Для этого выполняется спуск от корня бора до листовой вершины по самым правым дугам: 1 2 3 4 5 6 7 8 9 Maximum ( i n t ) : x i←m−1 while i ≥ 0: i f t.arcs[i] 6=NULL : r e t u r n Maximum ( t.arcs[i] ) i←i−1 i f t.v =NULL : −− Может быть в корне пустого бора r e t u r n NULL return t Время работы операции Maximum – O (h), где h – высота бора. В операции Maximum также используется хвостовая рекурсия. 90 Операции Insert и Reassign выполняются за время O (len (k)): 1 2 3 4 5 6 7 8 9 10 11 13 14 15 16 17 I n s e r t ( in t , in k , in v ): x x, i ← D e s c e n d ( t , k ) i f i = len(k) and x.v 6=NULL : panic w h i l e i < len(k) : y ← н о в а я вершина x.arcs[k[i]] ← y y.parent ← x x←y i←i+1 x.v ← v Reassign ( in t , in k , in v) x, i ← D e s c e n d ( t , k ) i f i 6= len(k) o r x.v =NULL : panic x.v ← v 91 Операция Delete выполняется за время O (len (k)): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Delete ( in t , in k) x, i ← D e s c e n d ( t , k ) i f i 6= len(k) o r x.v =NULL : panic x.v ←NULL w h i l e x.parent 6=NULL and x.v =NULL : j←0 w h i l e j < m and x.arcs[j] =NULL : j ←j+1 i f j < m : break y ← x.parent i←i−1 y.arcs[k[i]] ←NULL о с в о б о д и т ь память , занимаемую вершиной x x←y Без строчек 6..15 алгоритм тоже работает, но не освобождается память, и могут появиться служебные листовые вершины, что «поломает» реализацию операций Minimum и Maximum. 92 Рекурсивное формирование лексикографически отсортированной последовательности словарных пар бора: 1 2 3 4 5 6 7 8 S e q u e n c e ( i n t , i n / out queue ) i f t 6=NULL : i f t.v 6=NULL : E n q u e u e ( queue , t ) i←0 while i < m: S e q u e n c e ( t.arcs[i] , queue ) i←i+1 Проверка в строчке 3 нужна для того, чтобы в последовательность не попадали служебные вершины. 93 §14. Сжатый бор Реализация бора требует O (qm) памяти, где q – суммарная длина всех ключей, а m – размер алфавита. Действительно, в худшем случае, когда все ключи начинаются с разных букв, количество вершин в боре будет равно q + 1. Сжатый бор (compact trie) – это дерево, каждая дуга которого помечена строкой. При этом первые буквы строк, которыми помечены дуги, исходящие из одной вершины, должны различаться. Кроме того, из нелистовой вершины сжатого бора исходит не менее двух дуг. Фактически, сжатый бор – это бор, в котором вершины, из которых исходит только одна дуга, объединены со своими дочерними вершинами. Сжатый бор позволяет сократить размер требуемой памяти до O (nm + q ), где n – количество ключей. 94 Ключи, содержащиеся в сжатом боре, не могут быть префиксами друг друга. Действительно, если ключ заканчивается в нелистовой вершине, и из этой вершины исходит только одна дуга, вершину придётся объединить с её дочерней вершиной, что лишит словарную пару места для хранения её значения. Поэтому мы будем добавлять в конец каждого ключа специальный символ $, который не может содержаться в другом месте ключа. Для обеспечения лексикографического порядка на множестве ключей будем считать, что символ $ предшествует всем символам алфавита (имеет нулевой код). Пример. (Сжатый бор, содержащий словарные пары hant$, 20i, hape$, 5i, hapex$, 30i, happle$, 10i, haxe$, 30i, hone$, 25i.) 20 $ nt$ e p a 30 10 one$ 25 x$ ple$ xe$ 5 30 95 Из того, что ключи в сжатом боре не могут быть префиксами друг друга, следует, что ключи оканчиваются в листовых вершинах, а служебные вершины всегда промежуточные. Пустой сжатый бор не может быть представлен единственной вершиной, которая одновременно является и корнем, и листом, потому что листовая вершина не может быть служебной. Поэтому пусть пустой сжатый бор вообще не содержит ни одной вершины. Сжатый бор с единственной словарной парой не содержит «развилок», а значит должен быть представлен единственной вершиной. Спрашивается, откуда в этом случае взять дугу, помеченную ключом этой словарной пары? Для решения этого вопроса разрешим существование дуги, входящей в корень бора. Пример. (Сжатый бор, содержащий единственную пару habc$, 10i.) abc$ 10 96 Вершину сжатого бора мы будем представлять структурой hv, label, parent, arcsi, в которой: – v – указатель на значение, привязанное к ключу, соответствующему вершине (указатель v = NULL, если вершина является служебной); – label – метка дуги, входящей в вершину; – parent – указатель на родительскую вершину (NULL в случае корня); – arcs – массив указателей на дочерние вершины (если из вершины исходит дуга, метка которой начинается с символа x, то arcs [x] содержит указатель на вершину, в которую эта дуга входит; в противном случае arcs [x] = NULL). Так как пустой сжатый бор не содержит вершин, операции инициализации и проверки сжатого бора на пустоту тривиальны: 1 2 4 5 I n i t C o m p a c t T r i e ( out t ) t ←NULL MapEmpty ( i n t ) : empty empty ← t =NULL 97 Для обозначения позиции, до которой мы доходим в сжатом боре в процессе спуска от корня, мы будем использовать структуру hx, ii, в которой x – указатель на вершину сжатого бора, i – расстояние (в символах), которое мы прошли по дуге, входящей в вершину x. Вспомогательная операция Descend в случае сжатого бора приобретает вид 1 2 3 4 5 6 7 8 9 10 11 D e s c e n d ( i n t , i n k ) : pos , i pos ← ht, 0i i←0 loop : l ← pos.x.label w h i l e i < len(k) and pos.i < len(l) and k[i] = l[pos.i] : i ← i + 1 , pos.i ← pos.i + 1 i f i = len(k) o r pos.i 6= len(l) : b r e a k y ← pos.x.arcs[k[i]] i f y =NULL : b r e a k pos ← hy, 0i 98 1 2 3 4 5 6 8 9 10 11 12 13 15 16 17 19 20 21 DescendToLeaf ( i n t , i n k ) : x i f t =NULL : p a n i c pos, i ← D e s c e n d ( t , k ) i f i 6= len(k) o r pos.i 6= len(pos.x.label) o r pos.x.v =NULL : panic x ← pos.x M a p S e a r c h ( i n t , i n k ) : verdict i f t =NULL : return fa lse pos, i ← D e s c e n d ( t , k ) verdict ← i = len(k) and pos.i = len(pos.x.label) and pos.x.v 6=NULL Lookup ( i n t , i n k ) : v x ←DescendToLeaf (t ,k ) v ← x.v Reassign ( in t , in k , in v) x ←DescendToLeaf (t ,k ) x.v ← v 99 1 2 3 4 5 6 7 8 Minimum ( i n t ) : x x←t i f x 6=NULL : w h i l e x.v =NULL : i←0 w h i l e x.arcs[i] =NULL : i←i+1 x ← x.arcs[i] Maximum – аналогично. 100 1 2 3 4 6 7 8 9 10 11 12 13 14 L i n k ( i n / out t , i n parent , i n child ) child.parent ← parent i f parent =NULL : t ← child e l s e : parent.arcs[child.label[0]] ← child S p l i t ( i n / out t , i n / out pos ) l ← pos.x.label i f pos.i < len(l) : y ← н о в а я вершина y.label ← l[0 : pos.i − 1] pos.x.label ← l[pos.i : len(l) − 1] L i n k ( i n / out t , pos.x.parent , y ) L i n k ( i n / out t , y , pos.x ) pos.x ← y 101 1 2 3 4 5 6 7 8 9 11 12 13 I n s e r t ( i n / out t , i n k , i n v ) : x x ← н о в а я вершина x.v ← v i f t =NULL : x.label ← k t←x else : pos, i ← D e s c e n d ( t , k ) i f i = len(k) : p a n i c S p l i t ( i n / out t , i n / out pos ) x.label ← k[i : len(k) − 1] L i n k ( i n / out t , pos.x , x ) 102 1 2 3 4 5 6 7 8 9 10 11 12 13 14 16 17 18 D e l e t e ( i n / out t , i n k ) x ←DescendToLeaf (t ,k ) l ← x.label y ← x.parent о с в о б о д и т ь память , занимаемую вершиной x i f y =NULL : t ←NULL else : y.arcs[l[0]] ←NULL z ←NULL , i ← 0 while i < m: i f y.arcs[i] 6=NULL : i f z 6=NULL : r e t u r n z ← y.arcs[i] i←i+1 z.label ← y.label + z.label L i n k ( i n / out t , y.parent , z ) о с в о б о д и т ь память , занимаемую вершиной y 103 §15. Система непересекающихся множеств Система непересекающихся множеств – это абстрактная структура данных, представляющая множество {σi}n−1 , элементами которого являются непустые конечные непересекающиеся множества. Чаще всего эта структура данных применяется для решения задачи разбиения некоторого конечного множества на классы эквивалентности. Представитель множества σi – это один из элементов σi, выбранный для обозначения всего множества. Мы будем считать, что представитель множества выбирается произвольно и обозначать его как repr (σi). Пусть G – универсальное множество, из элементов которого будут составлены наши непересекающиеся множества. Пусть S – множество систем непересекающихся множеств. 104 Будем рассматривать систему непересекающихся множеств {σi}n−1 как частичную функцию s : G → G такую, что (∀x ∈ σi) : s (x) = repr (σi). Определим три операции для системы непересекающихся множеств: 1. MakeSet : S × G → S – добавление в систему нового множества, состоящего из одного элемента. MakeSet (s, x) = s ∪ hx, xi. (Ограничение: x ∈ / dom s.) 2. Union : S ×G×G → S – объединение двух множеств, каждое их которых идентифицируется одним из своих элементов. Union (s, x, y ) = (s \ (w × s (y ))) ∪ (w × s (x)), где w = {z |s (z ) = s (y ) }. (Ограничение: x ∈ dom s, y ∈ dom s.) 3. Find : S × G → G – поиск представителя множества, которому принадлежит указанный элемент. Find (s, x) = s (x). (Ограничение: x ∈ dom s.) 105 §16. Лес непересекающихся множеств Лес непересекающихся множеств является одной из реализаций системы непересекающихся множеств. Основная идея данной реализации состоит в том, что каждое множество σi из системы {σi}n−1 представлено в виде дерева, вершинами которого являются элементы σi. Вершина дерева σi может иметь любое количество дочерних вершин. Более того, элементы множества σi могут как угодно располагаться в дереве. Единственное ограничение – представитель σi должен быть корнем. Каждая вершина дерева σi в памяти компьютера представляется в виде структуры hx, parenti, в которой x – элемент σi, а parent – указатель на родительскую вершину. Родительской вершиной для корня дерева является она сама. 106 Наивная реализация операций: 1 2 3 4 6 7 8 9 11 12 13 14 15 MakeSet ( i n x ) : t t ← н о в а я вершина t.x ← x t.parent ← t Union ( i n x , i n y) rootx ← F i n d ( x ) rooty ← F i n d ( y ) rootx.parent ← rooty F i n d ( i n x ) : root i f x.parent = x : root ← x else : root ← F i n d ( x.parent ) Замечание. Union работает, даже если x и y принадлежат одному дереву. 107 В наивной реализации MakeSet работает за O (1), а Union и Find – за O (n), где n – общее количество вершин в лесу. Действительно, в худшем случае все вершины дерева могут образовывать однонаправленный список (максимально несбалансированное дерево). Наивную реализацию операций можно оптимизировать, если при объединении двух деревьев делать корень менее глубокого дерева дочерней вершиной корня более глубокого дерева. Эта оптимизация называется эвристикой объединения по глубине. Для реализации этой эвристики понадобится добавить в каждую вершину поле depth, задающее глубину её поддерева. 108 Эвристика объединения по глубине требует переписывания кода операций MakeSet и Union: 1 2 3 5 6 7 8 9 10 11 12 13 MakeSet ( i n x ) : t t ← н о в а я вершина t.x ← x , t.depth ← 0 , t.parent ← t Union ( i n x , i n y) rootx ← F i n d ( x ) rooty ← F i n d ( y ) i f rootx.depth < rooty .depth : rootx.parent ← rooty else : rooty .parent ← rootx i f rootx.depth = rooty .depth and rootx 6= rooty : rootx.depth ← rootx.depth + 1 Можно показать, что операции Union и Find теперь работают за время O (lg n), где n – общее количество вершин в лесу. 109 Время работы операций можно существенно улучшить, если в операции Find делать все пройденные вершины дочерними вершинами корня дерева (эвристика сжатия пути). 1 2 3 4 5 F i n d ( i n x ) : root i f x.parent = x : root ← x else : root ← x.parent ← F i n d ( x.parent ) Замечание. Применение эвристики сжатия пути приводит к тому, что значение поля depth в вершине дерева может превышать реальную глубину растущего из этой вершины поддерева. Существует достаточно сложное доказательство того, что совместное применение эвристики объединения по глубине и эвристики сжатия пути приводит к тому, что операции Union и Find начинают работать за амортизированное время O (α (n)), где α – чрезвычайно медленно растущая функция такая, что α (n) < 5 для всех разумных значений n. 110 §17. Суффиксное дерево (черновик) Суффиксное дерево – это модификация сжатого бора, предназначенная для хранения всех суффиксов некоторой строки. Пример. (Суффиксное дерево для строки «cocoa».) 2 coa$ 4 co a$ $ 1 9 coa$ o a$ 3 5 6 a$ 8 7 В вершинах – просто их порядковые номера. Красные стрелки – суффиксные связи. 111 Суффиксная связь – дополнительная дуга, соединяющая вершину, соответствующую строке aX, с вершиной, соответствующей строке X. (Здесь a – буква, а X – строка.) Пример. (Суффиксное дерево для строки «dodo».) 2 do$ 4 3 $ do do$ 1 o 5 6 $ $ 8 7 Суффиксные связи играют вспомогательную роль при построении дерева. 112 Вершину суффиксного дерева мы будем представлять структурой hlabel, parent, suf, arcsi, в которой: – label – метка дуги, входящей в вершину; – parent – указатель на родительскую вершину; – suf – указатель на вершину, соответствующую самому длинному собственному суффиксу данной вершины (суффиксная связь); – arcs – массив указателей на дочерние вершины (если из вершины исходит дуга, метка которой начинается с символа x, то arcs [x] содержит указатель на вершину, в которую эта дуга входит; в противном случае arcs [x] = NULL). 113 Пустое суффиксное дерево будет представлено корневой вершиной и специальной вершиной-ограничителем, упрощающей запись алгоритмов. Все элементы массива arcs ограничителя должны содержать указатели на корень. При этом ограничитель является родителем корня, и в корень входит «псевдодуга» длиной в один символ, значение которого не важно. Кроме того, ограничитель будет являться суффиксом корня, а также суффиксом самого себя. stub * root Позиции в дереве, как и в случае сжатого бора, будут представляться парами hx, ii, в которых x – указатель на вершину дерева, i – расстояние (в символах), которое мы прошли по дуге, входящей в вершину x. 114 Инициализация суффиксного дерева в соответствии со схемой, приведённой на предыдущем слайде, выглядит следующим образом: 1 2 3 4 5 6 7 8 9 10 11 I n i t S u f f i x T r e e ( out root ) stub ← н о в а я вершина root ← н о в а я вершина stub.label ← п у с т а я с т р о к а stub.parent ←NULL stub.suf ← stub f o r each c ∈алфавит : stub.arcs[c] ← root root.label ← с т р о к а и з о д н о г о с и м в о л а root.parent ← stub root.suf ← stub Алгоритм InitSuffixTree возвращает указатель на корень пустого дерева. 115 Вспомогательная операция Descend для суффиксного дерева выполняет спуск из произвольной позиции start в соответствии со строкой k и возвращает самую глубокую позицию pos, до которой можно спуститься, а также количество i пройденных символов строки: 1 2 3 4 5 6 7 8 9 10 11 D e s c e n d ( i n start , i n k ) : pos , i pos ← start , i ← 0 loop : l ← pos.x.label w h i l e i < len(k) and pos.i < len(l) and k[i] = l[pos.i] : i ← i + 1 , pos.i ← pos.i + 1 i f i = len(k) o r pos.i 6= len(l) : b r e a k y ← pos.x.arcs[k[i]] i f y =NULL : b r e a k pos ← hy, 1i i←i+1 Операцию Descend можно запускать в том числе и из вершины-ограничителя. 116 Основной тип запросов к суффиксному дереву заключается в поиске некоторой подстроки в строке, на основании которой дерево построено. Очевидно, что если подстрока S входит в строку T , то какой-то суффикс строки T начинается с S. Поэтому, если для строки T построено суффиксное дерево с корнем root, то с позиции hroot, 1i в дереве начинается любая её подстрока. Тем самым, проверку вхождения подстроки S в T можно записать как 1 2 3 C o n t a i n s ( i n root , i n s ) : verdict pos, i ← D e s c e n d ( hroot, 1i , s ) verdict ← i = len(s) 117 Вспомогательная операция Link делает вершину child дочерней по отношению к вершине parent: 1 2 3 L i n k ( i n parent , i n child ) child.parent ← parent parent.arcs[child.label[0]] ← child Операция Split вставляет новую вершину в позиции pos, если эта позиция находится в середине дуги. Она возвращает булевское значение, показывающее, понадобилось ли создание новой вершины: 1 2 3 4 5 6 7 8 9 S p l i t ( i n / out pos ) : splitted splitted ← pos.i < len(pos.x.label) i f splitted : y ← н о в а я вершина y.label ← pos.x.label[0 : pos.i − 1] pos.x.label ← pos.x.label[pos.i : len(l) − 1] L i n k ( pos.x.parent , y ) L i n k ( y , pos.x ) pos.x ← y 118 1 2 3 4 5 6 7 8 9 10 11 12 13 I m S u f ( i n pos ) : suf P os l ← pos.x.label , x ← pos.x.parent.suf i f x = pos.x.parent : ; если pos показывает на корень suf P os ← hx, 0i ; вернуть ограничитель else : ; иначе быстро спускаться по дереву, ; руководствуясь только первыми символами дуг i←0 loop : x ← x.arcs[l[i]] i f pos.i − i ≤ len(x.label) : b r e a k i ← i + len(x.label) suf P os ← hx, pos.i − ii 119 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Append ( i n root , i n s ) pos ← hroot, 1i , top ← н о в а я вершина , prev ←NULL , i ← 0 loop : splitted ← S p l i t ( i n / out pos ) i f prev 6=NULL : prev.suf ← pos.x , prev ←NULL j←0 i f not splitted : pos, j ← D e s c e n d ( pos , s[i : len(s) − 1] ) i←i+j i f i = len(s) : top.suf ← pos.x , b r e a k if j = 0: top.suf ← н о в а я вершина top ← top.suf top.label ← s[i : len(s) − 1] L i n k ( pos.x , top ) prev ← pos.x pos ← I m S u f ( pos ) 120 §18. Дерево критических битов Размер сжатого бора в памяти можно уменьшить до O (n · lg m + q ), где n – количество словарных пар, q – суммарная длина всех ключей, а m – размер алфавита. Для этого достаточно представить каждый символ алфавита в двоичной системе счисления. Тем самым мы сократим алфавит до двух символов, в результате чего ключи превратятся в последовательности нулей и единиц, а сжатый бор станет бинарным (из нелистовых вершин будут исходить ровно две дуги). Существует большое количество реализацией бинарного сжатого бора. Первая реализация – PATRICIA trees (Дональд Моррисон, 1968). Наиболее компактной реализацией является так называемое дерево критических битов (Дэниэл Дж. Бернстайн, 2004). 121 Листовые и промежуточные вершины дерева критических бит представлены в памяти по-разному: листовая вершина содержит пару hk, vi, а промежуточная – тройку hpos, lef t, righti. Здесь: – k и v – ключ и значение словарной пары; – pos – длина в битах строки, соответствующей промежуточной вершине; – lef t и right – указатели на вершины, в которые входят дуги, метки которых начинаются на 0 и 1, соответственно. Для работы дерева критических бит важно по указателю на вершину уметь понять, листовая она или промежуточная. При записи алгоритмов мы будем использовать «волшебный» предикат is leaf(ptr), отвечающий на вопрос, указывает ли ptr на листовую вершину. Бернстайн рекомендует размещать вершины по чётным адресам, чтобы иметь возможность использовать младший бит указателя для индикации типа вершины, на которую этот указатель указывает. Тогда is leaf должен проверять, установлен ли младший бит указателя. 122