Упорядоченное множество — различия между версиями
(Новая страница: «Чтобы работать со множеством было проще - используют '''упорядоченное множество''', где можн…») |
|||
| Строка 1: | Строка 1: | ||
| + | ===Пример сбалансированного множества:=== | ||
| + | '''Сбалансированное дерево''', т.е. то дерево, в котором высота его поддеревьев различается не более чем на 1цу. | ||
| + | |||
| + | ==Операции над упорядоченным множеством== | ||
Чтобы работать со множеством было проще - используют '''упорядоченное множество''', где можно совершать следующие операции: <tex>Search(x)</tex> (поиск), <tex>Minimum</tex> (минимум), <tex>Maximum</tex> (максимум), <tex>Predecessor</tex> (предыдущий), <tex>Successor</tex> (следующий), <tex>Insert(x)</tex> (вставить), и <tex>Delete(x)</tex> (удалить). | Чтобы работать со множеством было проще - используют '''упорядоченное множество''', где можно совершать следующие операции: <tex>Search(x)</tex> (поиск), <tex>Minimum</tex> (минимум), <tex>Maximum</tex> (максимум), <tex>Predecessor</tex> (предыдущий), <tex>Successor</tex> (следующий), <tex>Insert(x)</tex> (вставить), и <tex>Delete(x)</tex> (удалить). | ||
| − | == Search == | + | |
| + | === Search === | ||
Процедура поиска получает на вход искомый ключ <tex>x</tex>, и возвращает указатель на элемент множества или специальное значение <tex>NIL</tex>, если такого элемента нет. | Процедура поиска получает на вход искомый ключ <tex>x</tex>, и возвращает указатель на элемент множества или специальное значение <tex>NIL</tex>, если такого элемента нет. | ||
| − | == Minimum == | + | |
| + | === Minimum === | ||
Процедура <tex>Minimum</tex> возвращает указатель на минимальный элемент множества. | Процедура <tex>Minimum</tex> возвращает указатель на минимальный элемент множества. | ||
| − | == Maximum == | + | |
| + | === Maximum === | ||
Процедура <tex>Maximum</tex> возвращает указатель на максимальный элемент множества. | Процедура <tex>Maximum</tex> возвращает указатель на максимальный элемент множества. | ||
| − | == Predecessor == | + | |
| + | === Predecessor === | ||
Процедура <tex>Predecessor</tex> возвращает указатель на предыдущий элемент множества. | Процедура <tex>Predecessor</tex> возвращает указатель на предыдущий элемент множества. | ||
| − | == Successor == | + | |
| + | === Successor === | ||
Процедура <tex>Successor</tex> возвращает указатель на следующий элемент множества. | Процедура <tex>Successor</tex> возвращает указатель на следующий элемент множества. | ||
| − | == Insert == | + | |
| + | === Insert === | ||
Процедура <tex>Insert(x)</tex> добавляет заданный элемент в подходящее место множества (сохраняя свойство упорядоченности). | Процедура <tex>Insert(x)</tex> добавляет заданный элемент в подходящее место множества (сохраняя свойство упорядоченности). | ||
| − | == Delete == | + | |
| + | === Delete === | ||
Параметром процедуры <tex>Delete(x)</tex> удаления является указатель на удаляемый элемент, после чего удаляемый элемент множества удаляется (сохраняя свойство упорядоченности). | Параметром процедуры <tex>Delete(x)</tex> удаления является указатель на удаляемый элемент, после чего удаляемый элемент множества удаляется (сохраняя свойство упорядоченности). | ||
== Литература == | == Литература == | ||
1. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Алгоритмы: построение и анализ = Introduction to Algorithms / — 1-е изд. — Пер. с англ под ред. А. Шеня. — М.: МЦНМО, 2002.—960 с. — ISBN 5-900916-37-5 | 1. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Алгоритмы: построение и анализ = Introduction to Algorithms / — 1-е изд. — Пер. с англ под ред. А. Шеня. — М.: МЦНМО, 2002.—960 с. — ISBN 5-900916-37-5 | ||
Версия 07:43, 16 марта 2011
Содержание
Пример сбалансированного множества:
Сбалансированное дерево, т.е. то дерево, в котором высота его поддеревьев различается не более чем на 1цу.
Операции над упорядоченным множеством
Чтобы работать со множеством было проще - используют упорядоченное множество, где можно совершать следующие операции: (поиск), (минимум), (максимум), (предыдущий), (следующий), (вставить), и (удалить).
Search
Процедура поиска получает на вход искомый ключ , и возвращает указатель на элемент множества или специальное значение , если такого элемента нет.
Minimum
Процедура возвращает указатель на минимальный элемент множества.
Maximum
Процедура возвращает указатель на максимальный элемент множества.
Predecessor
Процедура возвращает указатель на предыдущий элемент множества.
Successor
Процедура возвращает указатель на следующий элемент множества.
Insert
Процедура добавляет заданный элемент в подходящее место множества (сохраняя свойство упорядоченности).
Delete
Параметром процедуры удаления является указатель на удаляемый элемент, после чего удаляемый элемент множества удаляется (сохраняя свойство упорядоченности).
Литература
1. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Алгоритмы: построение и анализ = Introduction to Algorithms / — 1-е изд. — Пер. с англ под ред. А. Шеня. — М.: МЦНМО, 2002.—960 с. — ISBN 5-900916-37-5
