Search     or:     and:
 LINUX 
 Language 
 Kernel 
 Package 
 Book 
 Test 
 OS 
 Forum 
iakovlev.org

Алгоритмы - Структуры данных

При решении задач часто необходимо выполнять операции над данными . В общих чертах, их можно свести к трем разновидностям: добавление данных, удаление и проверка.
Например, нам нужно хранить набор имен так, чтобы в нем можно было быстро отыскать заданное имя. Эффективно решить эту проблему позволяет алгоритм бинарного поиска. Одно из решений задачи сводится к записи имен в упорядоченный массив и применению алгоритма бинарного поиска заданного имени. Упорядоченный массив совместно с алгоритмом бинарного поиска можно рассматривать в качестве абстрактного типа данных, позволяюш;его решить эту задачу.

Следующие операции являются частью абстрактного типа данных под названием список (list):
1. Создать пустой список.
2. Уничтожить список.
3. Определить, пуст ли список.
4. Определить количество элементов в списке.
5. Вставить элемент в указанную позицию списка.
6. Удалить элемент, находящийся в указанной позиции списка.
7. Просмотреть (извлечь) элемент, находящийся в указанной позиции списка.

При описании операций над типами данных необходимо задать совокупность математических правил , называе­мых аксиомами (axioms), которые точно определяют смысл каждой операции. Аксиома — это инвариант (истинное утверждение) операции. Например , известны аксиомы алгебраических операций; в частности, для операции умножения формулируются такие аксиомы:
(а * b) * с = а * (b * с)
а * b = b * а
а * 1 = а
а * 0 = 0

Аналогично можно задать совокупность аксиом, полностью описывающих свойства операций над списком - ниже рассмотрен список List и набор его встроенных методов: 
 
 List.createList().getLength() = 0
 List.insert(i,x).getLength() = List.getLength() + 1
 List.remove(i).getLength() = List.getLength() - 1
 List.createList().isEmpty() = true
 List.insert(i,item).isEmpty() = false
 List.createList().remove(i) = error
 List.insert(i,x).remove(i) = List
 List.createList().retrieve(i) = error
 List.insert(i,x).retrieve(i) = x
 List.retrieve(i) = List.insert(i, x).retrieve(i+1)
 List.retrieve(i+1) = aList.remove(i).retrieve(i)
Замену структуры данных в медленно работающей программе можно сравнить с пересадкой органа. Такие важные классы абстрактных типов данных, как контейнеры, словари и очереди с приоритетами, могут реализовываться посредством разных, но функционально эквивалентных структур данных. Замена структуры данных одного типа структурой данных другого типа не влияет на правильность программы, т. к. предполагается, что одна правильная реализация заменяется другой правильной реализацией. Но в реализации другого типа данных могут применяться операции с иными временными отношениями, в результате чего общая производительность программы может значительно повыситься.

В зависимости от реализации (посредством массивов или указателей) структуры данных можно четко разбить на два типа — смежные и связные.
♦ Смежные структуры данных реализованы в виде непрерывных блоков памяти. К ним относятся массивы, матрицы, кучи и хэш-таблицы.
♦ Связные структуры данных реализованы в отдельных блоках памяти, связанных вместе с помощью указателей. К этому виду структур данных относятся списки, деревья и списки смежных вершин графов.

Массив представляет собой основную структуру данных смежного типа. Записи данных в массивах имеют постоянный размер, что позволяет с легкостью найти любой элемент по его индексу (или адресу).
Перечислим достоинства массивов.
♦ Постоянное время доступа при условии наличия индекса. Так как индекс каждого элемента массива соответствует определенному адресу в памяти, то при наличии соответствующего индекса доступ к произвольному элементу массива осуществляется практически мгновенно.
♦ Эффективное использование памяти. Массивы содержат только данные, поэтому память не тратится на указатели и другую форматирующую информацию. Кроме этого, для элементов массива не требуется использовать метку конца записи, т. к. все элементы массива имеют одинаковый размер.
♦ Локальность в памяти. Одна из самых распространенных идиом программирования — обработка элементов структуры данных в цикле. Массивы хорошо подходят для операций такого типа, поскольку обладают отличной локальностью в памяти. В современных компьютерных архитектурах физическая непрерывность последовательных обращений к данным помогает воспользоваться высокоскоростной кэш-памятью.

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

Простой пример использования массива демонстрируется в следующей программе, которая распечатывает все простые числа, меньшие 1000. Используемый метод восходит к третьему столетию до нашей эры и называется решетом Эратосфена . Это типичный алгоритм, где используется возможность быстрого доступа к любому элементу массива по его индексу.
Начинаем с двойки, прибавляем в цикле два и отсеиваем все получившиеся числа. Затем берем 3, прибавляем 3, и отсеиваем все получившиеся числа. И т.д.
Решето Эратосфена - си: 
 
 #define N 1000
 
 int main() {
   int i, j, a[N];
 
   for (i = 2; i < N; ++i)
     a[i] = 1;
   for (i = 2; i < N; ++i)
     if (a[i])
       for (j = i; i*j < N; ++j)
 	a[i*j] = 0;
   for (i = 2; i < N; ++i)
     if (a[i])
       printf("%4d ", i);
   printf("\n");
 }
Решето Эратосфена - go: 
 
 func main() {
     primes := make([]int, 0)
     n := 1000
 	checked := make([]bool, n)
 	sqrt_n := int(math.Sqrt(float64(n)))
 
 	for i := 2; i <= sqrt_n; i++ {
 		if !checked[i] {
 			for j := i * i; j < n; j += i {
 				checked[j] = true
 			}
 		}
 	}
 
 	for i := 1; i < n; i++ {
 		if !checked[i] {
 			primes = append(primes, i)
 		}
 	}
 
 	fmt.Printf("%v \n", primes)
 	return
 }
Решето Эратосфена - python: 
 
 n = 1000
 a = []
 for i in range(n + 1):
     a.append(i)
 i = 2
 while i <= n:
     if a[i] != 0:
         j = i + i
         while j <= n:
             a[j] = 0
             j = j + i
     i += 1
 i = 0
 while i < len(a):
     if a[i] != 0:
         print i
     i += 1
Указатели позволяют удерживать воедино связные структуры. Указатель— это адрес ячейки памяти. Переменная, содержащая указатель на элемент данных, может предоставить большую гибкость вфаботе с этими данными, чем просто их копия.
Синтаксис и возможности указателей значительно различаются в разных языках программирования, в питоне вообще нет указателей, в гоу возможности указателей ограничены по сравнению с более низкоуровневым си. Например, в си переменная указателя р содержит адрес памяти, по которому находится определенный блок данных, и указатель здесь при объявлении получает тип, соответствующий типу данных, на которые этот указатель может ссылаться. Операция, обозначаемая *р, называется разыменованием указателя и возвращает значение элемента данных, расположенного по адресу, содержащемуся в переменной указателя р. А операция, обозначаемая &х, называется взятием адреса и возвращает адрес (т. е. указатель) данной переменной х. Специальное значение null применяется для обозначения неинициализированного указателя или указателя на последний элемент структуры данных.

Связные списки

Если главный интерес для нас представляет последовательный перебор набора элементов, одного за другим, их можно организовать в виде связного списка — базовой структуры данных, в которой каждый элемент содержит информацию, необходимую для получения следующего элемента. Основное преимущество связных списков перед массивами заключается в возможности эффективного изменения порядка следования элементов. Эта гибкость достигается ценой уменьшения скорости доступа к произвольному элементу списка, поскольку единственный способ получения доступа к элементу состоит в отслеживании связей от начала списка. Существуют несколько способов построения связных списков, все они берут начало со следующего определения:
Связный список — это набор элементов, причем каждый из них является частью узла (node), который также содержит ссылку (link) на некоторый другой узел.
Узлы определяются ссылками на узлы, поэтому связные списки иногда называют самоссылочыми (self-referent) структурами. Более того, хотя узел обычно ссылается на другой узел, возможна ссылка на самого себя, поэтому связные списки могут представлять собой циклические (cyclic) структуры.

Объявление типа связного списка на си: 
 
 struct node{
     int info;
     struct node *link;
 };
 struct node *start=NULL;
 struct node * createnode(){
   struct node *t;
   t=(struct node*)malloc(sizeof(struct node));
   return(t);
 }
Объявление типа связного списка на go: 
 
 type List struct {
     Length int
     Head   *Node
     Tail   *Node
 }
 func NewList() *List {
     l := new(List)
     l.Length = 0
     return l
 }
 type Node struct {
     Value interface{}
     Prev  *Node
     Next  *Node
 }
В питоне структур нет, вместо них используют классы: 
 
 class Node:
     def __init__(self, data):
         self.data = data 
         self.next = None 
     def __repr__(self):  
         return f"Node({self.data})"
 
 class LinkedList:
     def __init__(self):
         self.head = None 
 
     def insert_tail(self, data) -> None:
         pass
 
     def insert_head(self, data) -> None:
         pass
 
     def delete_head(self):  # delete from head
         pass
 
     def delete_tail(self):  # delete from tail
         pass
 
     def __getitem__(self, index):
         current = self.head
         ...
         return current
 
     def __setitem__(self, index, data):
         current = self.head
         ...
Односвязные списки поддерживают три основных операции: поиск (search), вставку (insert) и удаление (delete). В двунаправленных или двусвязных списках (doubly-linked list) каждый узел содержит указатель как на следующий, так и на предыдущий узел.

Поиск в связном списке

Рекурсивный поиск элемента в связном списке - си: 
 
 list *search_list(list *l, item_type x)
 {
     if (l == NULL) return(NULL);
     if (l->item == x)
         return(l); 
     else
         return( search_list(l->next, x) );
 }
Нерекурсивный поиск элемента в связном списке по индексу - go: 
 
 func (l *List) Get(index int) (*Node, error) {
 	if index > l.Len() {
 		return nil, errors.New("Index out of range")
 	}
 	node := l.Head
 	for i := 0; i < index; i++ {
 		node = node.Next
 	}
 	return node, nil
 }
Нерекурсивный поиск элемента в связном списке по значению - python: 
 
    def get_item(self, data):
         current = self.head
         while current:
             if data == current.data:
                 return current
             current = current.next
         return None

Вставка в связном списке

К сишному коду требуются небольшие пояснения Функция maiioc возвращает указатель на блок памяти достаточного размера, выделенный для нового узла, в котором будет храниться элемент х. Двойная звездочка (**l) означает, что переменная k является указателем на указатель на узел списка. Таким образом, строчка кода *l=р; копирует значение р в блок памяти, на который ссылается переменная l, которая является внешней переменной, обеспечивающей доступ к началу списка: 
 
 void insert_list(list **l, item_type х)
 {
     list *р;
     /* Временный указатель */
     р = malloc(sizeof(list) );
     p->item = х;
     p->next = *l;
     *l = р;
 }
Вставка - go: 
 
 func NewNode(value interface{}) *Node {
 	return &Node{Value: value}
 }
 
 func (l *List) Add(value interface{}, index int) error {
 	if index > l.Len() {
 		return errors.New("Index out of range")
 	}
 
 	node := NewNode(value)
 
 	if l.Len() == 0 || index == 0 {
 		l.Prepend(value)
 		return nil
 	}
 
 	if l.Len()-1 == index {
 		l.Append(value)
 		return nil
 	}
 
 	nextNode, _ := l.Get(index)
 	prevNode := nextNode.Prev
 
 	prevNode.Next = node
 	node.Prev = prevNode
 
 	nextNode.Prev = node
 	node.Next = nextNode
 
 	l.Length++
 
 	return nil
 }
Вставка - python: 
 
     def append(self, data):
         n = Node(data)
         if not self.head:
             self.head = n
             self.tail = n
         else:
             self.tail.next = n
             self.tail = self.tail.next

Удаление в связном списке

В сишном вариант используется рекурсивная вспомогательная функция remove_list. Сначала нам нужно найти указатель на элемент списка, предшествующий удаляемому элементу: 
 
 list *remove_list(list *1, item_type x)
 {
     if ((l == NULL) M (l->next == NULL)) {
         printf("Error: null list.\n"); return(NULL);
     }
     if ((l->next)->item == х)
         return(l);
     else
         return( remove_list(l->next, x));
 }
 
 delete_list(list **1, item_type х)
 {
     list *р;       /* Указатель на узел*/
     list *pred;    /* Указатель на предшествующий узел  */
     list *search_list(), *remove_list();
     р = search_list(*l,х);
     if (р ! = NULL) {
         pred = remove_list(*l,x);
         if (pred == NULL)    /* Соединяем список */
             *l = p->next;
         else
             pred->next = p->next;
             free(p);    /* Освобождение памяти узла */
     }
 }
Удаление - go: 
 
 func (l *List) Remove(value interface{}) error {
 	if l.Len() == 0 {
 		return errors.New("Empty list")
 	}
 
 	if l.Head.Value == value {
 		l.Head = l.Head.Next
 		l.Length--
 		return nil
 	}
 
 	found := 0
 	for n := l.Head; n != nil; n = n.Next {
 
 		if *n.Value.(*Node) == value && found == 0 {
 			n.Next.Prev, n.Prev.Next = n.Prev, n.Next
 			l.Length--
 			found++
 		}
 	}
 
 	if found == 0 {
 		return errors.New("Node not found")
 	}
 
 	return nil
 }
Удаление - python: 
 
     def delete(self, data):
         pre = None
         cur = self.head
         while(cur):
             if cur.data == data:
                 if pre:
                     pre.next = cur.next
                 else:
                     self.head = self.head.next
                 cur = None
                 break
             pre = cur
             cur = cur.next	
         self.curr = None


Стеки и очереди

Термин контейнер (container) обозначает структуру данных, позволяющую хранить и извлекать данные независимо от содержимого. В противоположность контейнерам, словари представляют собой абстрактные типы данных, которые извлекаются по клю­ чевому значению или содержимому.
Контейнеры различаются по поддерживаемому ими типу извлечения данных. В двух наиболее важных типах контейнеров порядок извлечения зависит от порядка помеще­ ния:
♦ Стеки. Извлечение данных осуществляется в порядке LIFO ("last in, first out", "по­ следним вошел — первым вышел"). Стеки легко реализуются и обладают высокой эффективностью. По этой причине стеки удобно применять в случаях, когда поря­ док извлечения данных не имеет никакого значений, например, при обработке па­ кетных заданий. Операции вставки и извлечения данных для стеков называются push (запись в стек) и pop (снятие со стека):
• push(x,s) — вставить элемент х на верх (в конец) стека s;
• pop(s) — извлечь (и удалить) верхний (последний) элемент из стека s.
♦ Очереди. Очереди поддерживают порядок извлечения FIFO ("first-in, first-out", "первым вошел — первым вышел"). Использование этого порядка определенно самый справедливый способ управления временем ожидания обслуживания. Компьютер обрабатывает задачи в порядке FIFO, чтобы минимизировать максимальное время ожидания.
Очереди реализовать несколько труднее, чем стеки, и поэтому их применение больше подходит для приложений, в которых порядок извлечения данных является важным, например, эмуляции определенных процессов. Применительно к очередям операции вставки и извлечения данных называются enqueue (поставить в очередь) и dequeue (вывести из очереди) соответственно:
• enqueue^,q) — вставить элемент х в конец очереди q;
• dequeue(q) — извлечь (и удалить) элемент в начале очереди q.
На практике стеки и очереди можно реализовать посредством массивов или связных списков.


Словари

Тип данных словарь позволяет доступ к данным по содержимому. Словари применяются для хранения данных, которые можно быстро найти в случае надобности. Далее приводится список основных операций, поддерживаемых в словарях:
♦ search(D,k) — возвращает указатель на элемент словаря D с ключом к, если такой элемент существует;
♦ insert(D,x) — добавляет элемент, на который указывает х, в словарь Д
♦ delete(D,x) — удаляет из словаря D элемент, на который указывает х.
Некоторые словари также поддерживают другие полезные операции:
♦ max(D) и min(D)— возвращает указатель на элемент множества Д имеющий наибольший или наименьший ключ. Это позволяет использовать словарь в качестве очереди с приоритетами.
♦ predecessor(D,k) и successor(D,к) — возвращает элемент из отсортированного массива D предшествующий элементу с ключом к или стоящий сразу после него сооответственно. Это позволяет обрабатывать в цикле все элементы этой структуры данных.
С помощью только что перечисленных словарных операций можно выполнять многие распространенные задачи обработки данных. Допустим, нам нужно удалить все повторяющиеся имена из списка рассылки, затем отсортировать и распечатать получившийся список. Для выполнения этой задачи инициализируем пустой словарь D для которого ключом поиска будет служить имя записи. Потом считываем записи из списка рэссылки и для каждой записи выполняем операцию search в словаре на предмет наличия в нем данного имени. Если имя отсутствует в словаре, то вставляем его с помощью операции insert. Обработав весь список, извлекаем результаты из словаря. Для этого, начиная с наименьшего элемента словаря (операция min(D)\ выполняем операцию successor, пока не дойдем до наибольшего элемента (операция max(D)) обойдя таким образом по порядку вс$ элементы словаря.

Ниже приведена сравнительная таблица для массивов разных типов и время выполнения основных операций:
Неотсортированный массив Отсортированный массив
search(L , k) O(n) O(log(n))
insert(L , x) O(1) O(n)
delete(L , x) O(1) O(n)
successor(L , x) O(n) O(1)
predecessor(L , x) O(n) O(1)


Ниже приведена сравнительная таблица для односвязных и двусвязных списков и время выполнения основных операций:
Односвязный неотсортированный список Двусвязный неотсортированный список Односвязный отсортированный список Двусвязный отсортированный список
search(L , k) O(n) O(n) O(n) O(n)
insert(L , x) O(1) O(n) O(n) O(n)
delete(L , x) O(n) O(1) O(n) O(1)
successor(L , x) O(n) O(n) O(1) O(1)
predecessor(L,x) O(n) O(n) O(n) O(1)
minimum(L) O(n) O(n) O(1) O(1)
maximum(L) O(n) O(n) O(1) O(1)



Двоичные деревья поиска (BST)

Вы также можете найти информацию о BST с кодом у меня на сайте по ссылке в 7-м разделе.

Все рассмотренные до сего момента структуры данных позволяют выполнять либо быстрый поиск, либо быстрое обновление, но не быстрый поиск и быстрое обновление одновременно.
Для двоичного поиска необходимо иметь быстрый доступ к двум элементам, а именно средним элементам верхней и нижней частей массива по отношению к данному элементу. Иными словами, нужен связный список, в котором каждый узел содержит два указателя. Так мы приходим к идее двоичных деревьев поиска.
Корневое двоичное дерево определяется рекурсивно либо как пустое, либо как состоящее из узла, называющегося корнем, из которого выходят два корневых двоичных дерева, называющиеся левым и правым поддеревом. В корневых деревьях порядок "родственных" узлов имеет значение, поэтому левое поддерево отличается от правого. На следующем рисунке показаны пять разных двоичных деревьев, которые можно создать из трех узлов:

Каждый узел двоичного дерева поиска помечается ключом х таким образом, что для любого такого узла ключи всех узлов в его левом поддереве меньше jc , а ключи всех узлов в его правом поддереве больше х. Это достаточно необычный способ постановки меток на деревьях поиска. Для любого двоичного дерева с количеством узлов п и любого множества из п ключей существует только один способ постановки меток, который делает его двоичным деревом поиска.
Кроме поля ключа каждый узел двоичного дерева имеет поля left, right и parent, которые содержат указатели на левый и правый дочерние узлы и на родительский узел соответственно. Единственным узлом, указатель parent которого равен null , является корневой узел всего дерева.

Обьявление типа для двоичного поискового дерева - си: 
 
 typedef struct tree {
     item_type item;
     struct tree *parent;
     struct tree *left;
     struct tree *right;
 } tree;
Обьявление типа для двоичного поискового дерева - go: 
 
 type Node struct {
     Value  int
     Parent *Node
     Left   *Node
     Right  *Node
 }
 type Tree struct {
     Head *Node
     Size int
 }
Обьявление типа для двоичного поискового дерева - python: 
 
 class BSTnode(object):
     def __init__(self, parent, t):
         self.key = t
         self.parent = parent
         self.left = None
         self.right = None
         self.size = 1
Двоичные поисковые деревья поддерживают следующие основные операции:
1. Поиск
2. Обход
3. Вставка
4. Удаление

Поиск в двоичных поисковых деревьях

Поиск начинается с корневого узла дерева. Если узел не содержит искомый ключ х, то в зависимости от того, меньше или больше значение искомого ключа значения ключа корневого узла, поиск продолжается в левом или правом дочернем !узле соответственно. Этот алгоритм основан на том, что как левое, так и правое поддерево двоичного дерева сами являются двоичными деревьями.
Рекурсивный алгоритм поиска в двоичном поисковом дереве - си: 
 
 tree *search_tг е е (tree *l, item_type х)
 {
     if (l == NULL) return (NULL);
     if (l->item == x) return(l);
     if (x < l->item)
         return( search_tree(l->left, x));
     else
         return(search_tree(l->right, x) );
 }
Нерекурсивный поиск в двоичном поисковом дереве - go: 
 
 
 func (n *Node) Compare(m *Node) int {
 	if n.Value < m.Value {
 		return -1
 	} else if n.Value > m.Value {
 		return 1
 	} else {
 		return 0
 	}
 }
 
 func (t *Tree) Search(i int) *Node {
 	h := t.Head
 	n := &Node{Value: i}
 
 	for h != nil {
 		switch h.Compare(n) {
 		case -1:
 			h = h.Right
 		case 1:
 			h = h.Left
 		case 0:
 			return h
 		default:
 			panic("Node not found")
 		}
 	}
 	panic("Node not found")
 }
Рекурсивный поиск в двоичном поисковом дереве - python: 
 
     def find(self, t):
         if t == self.key:
             return self
         elif t < self.key:
             if self.left is None:
                 return None
             else:
                 return self.left.find(t)
         else:
             if self.right is None:
                 return None
             else:
                 return self.right.find(t)

Поиск минимума в двоичных поисковых деревьях

Реализация операции поиска наименьшего элемента требует понимания, каким образом этот элемент размещается в дереве. Согласно определению двоичного дерева, наименьший ключ должен находиться в левом поддереве корневого узла, т. к. значения всех ключей в этом дереве меньше, чем значение ключа корневого узла. Поэтому наименьший элемент должен быть самым левым потомком корневого узла.
Минимум в двоичных поисковых деревьях - си: 
 
 tree *find_minimum(tree *t)
 {
     tree *min; /* Указатель на наименьший элемент    */
     if (t == NULL) return(NULL);
     min = t;
     while (min->left != NULL)
         min = min->left;
     return(min);
 }
Минимум в двоичных поисковых деревьях - go: 
 
 func (tree *BinaryTree) Min() interface{} {
 	if tree.node == nil || tree.left.node == nil {
 		return tree.node
 	}
 	return tree.left.Min()
 }
Минимум в двоичных поисковых деревьях - python: 
 
    def minimum(self):
          current = self
          while current.left is not None:
              current = current.left
          return current
Посещение всех узлов двоичного дерева является важной составляющей многих алгоритмов. Основным применением алгоритма обхода дерева является перечисление ключей всех узлов дерева. Природа двоичного дерева позволяет с легкостью перечислить ключи всех его узлов в отсортированном порядке. Согласно определению двоичного дерева, все ключи со значением меньшим, чем значение ключа корневого узла, должны находиться в левом поддереве корневого узла, а все ключи с большим значением — в правом. Таким образом, результатом рекурсивного посещения узлов согласно данному принципу является симметричный обход (in-order traversal) двоичного дерева: 
 
 void traverse_tree(tree *l)
 {
     if (l != NULL) {
         traverse_tree(l->left);
         proCess_item(l->item);
         traverse_tree(l->right) ;
     }
 }

Вставка в двоичных поисковых деревьях

В двоичном дереве Т имеется только одно место, в которое можно вставить новый элемент х, где его потом можно будет найти в случае необходимости. Для этого нужно заменить указателем на вставляемый элемент указатель null , возвращенный неуспешным запросом поиска ключа к в дереве. В следующей си-шной реализации этой операции этапы поиска и вставки узла совмещаются с помощью рекурсии.
Процедура insert_tree принимает три аргумента:
указатель l на указатель, связывающий поддерево с остальной частью дерева;
вставляемый ключ х;
указатель parent на родительский узел, содержащий l.
Вставляемому узлу выделяется память и он интегрируется в структуру дерева, когда алгоритм находит указатель со значением null . Обратите внимание, что во время поис­ ка соответствующему левому или правому указателю передается указатель, так что iоперация присваивания *l = р; интегрирует новый узел в структуру дерева. После выполнения поиска за время O(h) выделение памяти новому узлу и интегрирование его в структуру дерева выполняется за постоянное время:
Си:

Go:

Python:

Удаление в двоичных поисковых деревьях

Операция удаления элемента сложнее, чем вставка, т. к. удаление узла означает, что нужно должным образом связать получившиеся поддеревья с общим деревом. Существуют три типа удаления. Так как листовые узлы не имеют потомков, то их можно удалить, просто обнулив указатель на такой узел. Удаление узла с одним потомком также не вызывает проблем. Такой узел имеет один родительский и один дочерний узел, и последний можно связать непосредственно с родительским узлом, не нарушая при этом симметричную схему размещения ключей дерева. Но как удалить узел с двумя потомками? Нужно присвоить этому узлу ключ его непосредственного потомка в отсортированном порядке. Этот дочерний узел должен иметь наименьшее значение ключа в правом поддереве, а именно быть самым левым узлом в правом поддереве родительского дерева . Перемещение этого узла на место удаляемого узла дает в результате двоичное дерево с должным расположением ключей, а также сводит нашу задачу к физическому удалению узла с, самое большее, одним по­ томком.
Си:

Go:

Python:

Все три словарные операции, реализованные посредством двоичных деревьев поиска, исполняются за время O(h), где h — высота дерева. Дерево имеет самую меньшую высоту, на которую мы можем надеяться, когда оно полностью сбалансированно; тогда высота равна h = [log(n) ] . Это очень хорошо, но дерево должно быть идеально сбалансированным.
Наш алгоритм вставки помещает каждый новый элемент в лист дерева, в котором он должен находиться. Вследствие этого форма (и, что более важно, высота) дерева зависит от порядка вставки ключей.
К сожалению, при построении дерева методом вставок могут происходить неприятные события, т. к. структура данных не контролирует порядок вставок. Например, посмотрим, что случится, если вставлять ключи в отсортированном порядке. Здесь операции insert(a), insert(b), insert(c), insert(d) и т. д. дадут нам тонкое длинное дерево, в котором используются только правые узлы.
Таким образом, высота двоичных деревьев может лежать в диапазоне от lg(n) до n. Но какова средняя высота дерева? Что именно мы считаем средней высотой? Вопрос будет четко определен, если мы будем считать равновероятными каждое из п! возможных упорядочиваний вставки и возьмем среднее их значение. В таком случае нам по­ везло, т. к. с высокой вероятностью высота получившегося дерева будет O(log(n)).
Произвольные деревья поиска обычно дают хорошие результаты. Но если нам не повезет с порядком вставок, то в наихудшем случае мы может получить дерево линейной высоты. Мы не можем прямо контролировать этот наихудший случай, т. к. мы должны создавать дерево в ответ на запросы, исходящие от пользователя.
Но ситуацию можно улучшить с помощью процедуры вставки/удаления, которая после каждой вставки слегка корректирует дерево, удерживая его как можно более сбалансированным, так что максимальная высота дерева будет логарифмической. Существуют сложные структуры данных в виде сбалансированных двоичных деревьев поиска, которые гарантируют, что высота дерева всегда будет O(log(n)). Вследствие этого время исполнения любой из словарных операций (вставка, удаление, запрос) будет равняться O(log(n)). Реализация структур данных сделана в разновидностях сбалансированных деревьев , называемых красно-­черными.

Ниже приведена сравнительная таблица для массивов разных типов и BST и время выполнения основных операций:
Неотсортированный массив Отсортированный массив BST
insert O(1) O(n) O(log(n))
search O(1) O(1) O(1)
delete O(n) O(1) O(log(n))




Оставьте свой комментарий !

Ваше имя:
Комментарий:
Оба поля являются обязательными

 Автор  Комментарий к данной статье