Упорядоченное множество — различия между версиями

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

Версия 23:52, 19 марта 2012

Пример упорядоченного множества:

Сбалансированное дерево, т.е. то дерево, в котором высота его поддеревьев различается не более чем на 1.

Операции над упорядоченным множеством

Чтобы работать со множеством было проще - используют упорядоченное множество, где можно совершать следующие операции: Search(x) (поиск), Minimum (минимум), Maximum (максимум), Predecessor (предыдущий), Successor (следующий), Insert(x) (вставить), и Delete(x) (удалить).

Search

Функция поиска получает на вход искомый ключ [math]x[/math], и возвращает указатель на элемент множества или специальное значение [math]NIL[/math], если такого элемента нет.

Minimum

Функция Minimum возвращает указатель на минимальный элемент множества.

Maximum

Функция Maximum возвращает указатель на максимальный элемент множества.

Predecessor

Функция Predecessor возвращает указатель на предыдущий элемент множества.

Successor

Функция Successor возвращает указатель на следующий элемент множества.

Insert

Функция Insert(x) добавляет заданный элемент в подходящее место множества (сохраняя свойство упорядоченности).

Delete

Параметром функции Delete(x) удаления является указатель на удаляемый элемент, после чего удаляемый элемент множества удаляется (сохраняя свойство упорядоченности).

Литература

1. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Алгоритмы: построение и анализ = Introduction to Algorithms / — 1-е изд. — Пер. с англ под ред. А. Шеня. — М.: МЦНМО, 2002.—960 с. — ISBN 5-900916-37-5