Search     or:     and:
 LINUX 
 Language 
 Kernel 
 Package 
 Book 
 Test 
 OS 
 Forum 
 iakovlev.org 
 Languages
 С
 GNU С Library 
 Qt 
 STL 
 Threads 
 C++ 
 Samples 
 stanford.edu 
 ANSI C
 Libs
 LD
 Socket
 Pusher
 Pipes
 Encryption
 Plugin
 Inter-Process
 Errors
 Deep C Secrets
 C + UNIX
=> Linked Lists / Trees
 Asm
 Perl
 Python
 Shell
 Erlang
 Go
 Rust
NEWS
Последние статьи :
  Rust 07.11   
  Go 25.12   
  EXT4 10.11   
  FS benchmark 15.09   
  Сетунь 23.07   
  Trees 25.06   
  Apache 03.02   
  SQL 30.07   
  JFS 10.06   
  B-trees 01.06   
 
TOP 20
 Go Web ...603 
 Trees...344 
 Ethreal 4...279 
 Python...256 
 2.0-> Linux IP Networking...252 
 Secure Programming for Li...244 
 Steve Pate 3...242 
 Mike Perry...223 
 Rubni-Corbet -> Глав...212 
 TCP 3...211 
 Stewens -> IPC 7...202 
 Rubni-Corbet -> Глав...200 
 TCP 2...197 
 Rubni-Corbet -> Глав...193 
 Rodriguez 6...193 
 Stevens-> Глава 25...189 
 C++ Templates 4...185 
 William Gropp...180 
 Rubni-Corbet -> Глав...180 
 Стивенс 9...180 
 
  01.11.2017 : 2330974 посещений 

iakovlev.org

Linked Lists / Trees

Я написал цикл статей для сайта IBM, в которых рассмотрел реализацию базовых структур данных на примере связных списков, как одной из наиболее важных и фундаментальных структур. Вторая половина цикла посвящена не менее значимой структуре данных — деревьям.

Часть 1: Особенности реализации структур данных в различных языках
Часть 2: Связные списки
Часть 3: Классификация связных списков
Часть 4: Связные списки и сортировка
Часть 5: Деревья
Часть 6: Двоичные деревья
Часть 7: Бинарные поисковые деревья (BST)
Часть 8: Сбалансированные двоичные деревья (AVL-деревья)
Часть 9: Красно-черные деревья
Часть 10: B-деревья и TRIE-деревья

Часть 1

Особенности реализации структур данных в различных языках

Введение

В представленном цикле статей рассматриваются реализации базовых структур данных, созданные с использованием двух разных языков программирования - классического Си и более современного Python. Язык Си относится к компилируемым языкам программирования со строгой типизацией, в то время как Python представляет собой динамически интерпретируемый язык. Поэтому будет интересно сравнить, как одна и та же функциональность может быть реализована в разных языках, и определить сильные и слабые стороны каждого подхода.

В первой статье, открывающей серию, будут разбираться следующие вопросы:

  • структуры данных и указатели в языке Си;
  • структуры данных и ссылки в Python;
  • списки в Python;
  • ссылочная организация списков.

Структуры данных

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

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

Структуры данных имеют первостепенное значение, так как память компьютера может хранить и извлекать данные на основе их адресов. Эти адреса могут вычисляться статически (для массивов) или динамически (для связных списков).

Различные языки программирования сильно различаются в плане встроенной реализации базовых структур данных. Так, в языке Pascal есть встроенная поддержка многомерных массивов, а в Lisp имеется встроенная реализация связных списков. В средах Perl и Python реализованы хеш-таблицы. Но самое главное, что в различных языках используются различные реализации ссылок, записей и других объектов.

Запись (record или struct) - одна из самых «низкоуровневых» структур данных, состоит из нескольких значений или полей, которые последовательно располагаются в памяти. Все поля могут иметь различный размер, и программист может определить произвольную структуру с произвольным количеством полей. При этом для каждого поля в этой структуре необходимо задать 2 атрибута:

  • определенный тип;
  • идентификатор.

Также структура может включать в себя поля, на самом деле являющиеся функциями. Такие поля в языке Си имеют тип void *. Благодаря подобным полям можно реализовать объектно-ориентированное программирование. В общем случае, структура - это упорядоченный список элементов или объектов.

Cobol был первым языком, в котором реализовали тип record. Этот язык позволял создавать структуры с набором полей, имеющим символьный или численный тип произвольного размера и точности. Позднее такие же структуры появились в Fortran, Algol, Lisp и Pascal, а еще позже структуры были добавлены в Си, Ada, Modula.

С записями/структурами можно выполнять следующие операции:

  • объявить новый тип записи;
  • создать переменную, имеющую тип записи;
  • присвоить значение какому-то полю внутри записи;
  • выбрать поле из записи по его имени;
  • сравнить 2 записи;
  • вычислить хеш для записи.

Между двумя структурами одного типа можно выполнить операцию присваивания. При этом различные языки по-разному могут трактовать строгую типизацию: например, в некоторых языках значение поля типа short integer может быть присвоено полю типа long integer.

Как уже было сказано, поля структуры располагаются в памяти последовательно, в соответствии с их порядком записи. Некоторые компиляторы могут делать неявное выравнивание полей в памяти. Также языки могут реализовывать структуру как массив указателей на поля структуры.

Структуры в языке Си

В языке Си структура - это тип, представляющий из себя набор именованных объектов различного типа, как показано в листинге 1.


Листинг 1. Пример структуры из языка Си
 
 struct family {
    char *father;
    char *mother;
    int[2] ages;
 };
 
 

Для создания новой переменной этого типа используется следующая конструкция:

struct family f;
 

Используя созданный объект и оператор «точка» (.) можно получить доступ к полям структуры и изменить их значение, как показано ниже:

f.father = "john dow";
 

В листинге 2 приведен другой вариант объявления структуры и создания объектов на ее основе.


Листинг 2. Другой вариант объявления структуры
 
 typedef struct {
    int    a;
    int    b;
    int    c;   
 } rec;
 
 // создание объекта типа структуры
 rec r1 = {1,2,3};
 // создание второго объекта этого же типа
 rec r2;
 // выполнение присваивания между объектами
 r2 = r1;
 
 

Указатели в языке Си

Для работы со структурами могут использоваться указатели. Указатель - это переменная, применяющаяся для использования структуры по ее адресу. Преимущество указателя в том, что его можно передать в качестве параметра в другую функцию, внутри которой можно будет использовать эту структуру. Указатель можно переназначить на другой указатель с помощью оператора «звездочка» (*), а помощью другого оператора -> можно обращаться к полям структуры, как показано ниже:

 struct rec *r3 = &r1;
  r3->c=3;
 

Указатели отличаются от обычных переменных тем, что при создании указателя создается ссылка на объект, в то время как в обычной переменной хранится адрес объекта. При использовании указателей необходимо учитывать следующие правила:

  • Указатель может указывать как на конкретный объект, так и ни на что не указывать. В последнем случае имеется в виду, что указатель установлен в NULL.
  • Указатель может быть разыменован. Это значит, что указатель не связан жестко с конкретным объектом, и в любой момент можно заменить объект, на который он указывает.
  • Указатель может быть плохим, когда после создания он не был инициализирован, то есть привязан к объекту. В языке Java при создании указателя он по умолчанию всегда устанавливается в NULL.
  • Указатель может быть назначен. Например, если есть два указателя - a и b, то между ними возможна операция назначения:
    a = b
     

    После этого оба указателя указывают на одну и ту же область памяти. Такая память называется общей (shared).

Листинг 3. Пример использования указателя
 
 
 int *money = NULL
 int a = 5;
 money = &a;
 
 

В языке Си указатели могут использоваться для передачи параметров в функцию по ссылке, при этом значение переданного параметра будет изменяться, как показано в листинге 4.


Листинг 4. Передача параметров по ссылке
 
 void alter(int *n) {
 		*n = 120;
 }
 
 void not_alter(int n) {
 	n = 10;
 }
 
 int x = 24;
 alter(&x);
 not_alter(x);
 
 

После вызова функции alter() значение переменной x изменится и станет равно 120, а вызов функции not_alter() никак не скажется на значении переменной x. Следует отметить, что работать с указателями нужно аккуратно и следовать перечисленным выше правилам, иначе возникновение проблем неизбежно.

Если в качестве параметра использовать не обычную переменную, а указатель, тогда в языке Си используется термин «двойной указатель». Например, в листинге 5 определяется элемент связного списка и указатель на первый элемент списка:


Листинг 5. Использование «двойных указателей»
 
 struct element
 {
     struct element * next;
     int    value;
 };
  
 struct element *head = NULL;
 
 

Если потребуется передать указатель head в функцию в качестве параметра по ссылке, то необходимо будет использовать двойной указатель:

void insert(struct element **head, int item) { }
 

Для добавления элемента в пустой список используется вызов:

insert(&head, item);
 
 

После этого указатель head будет указывать на первый элемент только что созданного связного списка.

Структуры данных в Python

В языке Python нет стандартного объекта struct, как в языке Си. Но этот объект можно легко реализовать с помощью классов. В листинге 6 представлен вариант преобразования структуры Си в класс Python.


Листинг 6. Структура в языке Си и аналогичный класс в Python
 
 struct Employee {
 			char * name;
 			int salary;
 	}
 
 
 
 //объявление класса
 class Employee(object):
 	def __init__(self, name=None,  salary=2000):
 		self.name = name
 		self.salary = salary
 	
 //создание объекта
 john = Employee('John Johnson',  3000)	
 
 

В листинге 7 показано объявления класса, реализующего элемент в связном списке.


Листинг 7. Реализация связного списка в Python
 
 class Element:
     def __init__(self, value = None, next = None):
         self.value = value
         self.next = next
 
 

По синтаксису это очень похоже на вариант, используемый в языке Си. Однако для параметров конструктора не требуется указывать тип, что значительно облегчает типизацию и решает связанные с этим проблемы.

Ссылки в Python

В Python нет указателей в том смысле, в каком они используются в языке Си. Зато все переменные одновременно являются и ссылками. Эта особенность Python избавляет от необходимости создавать дополнительные объекты типа указателей. При создании переменной в Python автоматически создается и ссылка на этот объект.

Ниже приведен фрагмент кода на языке Си:

	int foo = 3;
 	int &bar = foo;
 

В нем создаются два объекта - переменная foo и ссылка bar. Оба объекта указывают на один и тот же адрес. Если изменить значение foo, то и значение bar автоматически изменится, и наоборот. Также ссылка bar не может быть переназначена на другой объект, так как ссылки в Си являются неизменяемыми (immutable).

В Python ссылка может быть переназначена, поскольку она одновременно является и переменной. В следующем примере создаются два списка:

>>> a1 = [1, 2, 3]
 >>> a2 = [11, 22, 33]
 

Затем создается новая ссылка на первый список и в этот список добавляется элемент:

>>> b = a1
 >>> a1.append(4)
 

Ссылка b по-прежнему ведет на первый список с уже измененными значениями:

>>> b
 [1, 2, 3, 4]
 

Также можно переназначить ссылку на другой объект:

>>> b = a2
 >>> b
 [11, 22, 33]
 

Python также отличается от Си тем, что все параметры, передаваемые в функцию, по умолчанию имеют ссылочный тип. Но если говорить точнее, то почти все, так как в Python есть несколько стандартных типов, на которые это правило не распространяется: например immutable типы: целые и вещественные типы и строки. В листинге 8 в функцию в качестве параметра передается список:


Листинг 8. Передача параметров по ссылке в Python
 
 
 def append(lst):
     lst.append(4)
 
 a = [1, 2, 3]
 append(a)
 print a
 
 

После вызова функции список, переданный в качестве параметра, изменится, так как по умолчанию в Python аргументы функции имеют ссылочный тип.

Python относится к динамическим языкам с поздним связыванием (late-binding), так как переменные не имеют типовой привязки к объектам. Поэтому преобразование типов в Python выполняется на лету. Сначала необходимо создать список и ссылку на него, как показано ниже:

>>>	a = [1,2]
 >>>	b = a    
 

Можно проверить, была ли создана новая копия объекта или просто ссылка:

>>>print id(a) 
 >>>print id(b) 
 134806220
 134806220
 

Одинаковые значения говорят, что обе переменные - это ссылки, указывающие на один и тот же объект. Теперь можно создать второй объект целочисленного типа на основе уже существующей ссылки и проверить, что получилось:

>>> a = 2    
 >>> print(a) 
 >>> print(b) 
 >>> print id(a) 
 >>> print id(b) 
 
 2
 [1, 2]
 134573404
 134806220
 

Разные значения говорят о том, что каждая ссылка указывает на разный объект, причем тип переменной a был неявно изменен.

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

В общепринятом смысле, список - это структура, состоящая из последовательности элементов, с которой можно выполнять следующие операции:

  • получить доступ к элементу по индексу;
  • вставить элемент в произвольную позицию списка;
  • удалить произвольный элемент;
  • объединить 2 списка в один;
  • сделать копию списка;
  • сортировать список;
  • найти элемент в списке и т.д.

Для операций вставки и удаления существуют специфические ситуации, связанные с обработкой элементов на первой и последней позициях в списке.

Стек (stack) - список, в котором операции вставки и удаления всегда выполняются над последним элементом. Стек еще называют LIFO-списком: last-in-first-out (последним пришел – первым ушел). В стеке есть верхняя позиция - top, куда всегда добавляется новый элемент, и нижняя позиция - bottom, которая извлекается из стека в последнюю очередь. Очередь (queue) - список, в котором операции вставки и удаления выполняются на разных концах списка. Очереди еще называют FIFO-списками: first-in-first-out (первым пришел – первым ушел).

В языке Python присутствует встроенный тип данных – «список», который можно определить с помощью квадратных скобок:

>>> list = [] 
 
 

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


Листинг 9. Работа со списками в Python
 //добавление элементов в конец списка
 >>> list.append(1)
 >>> list.append(2)
 
 //вставка элемента в начало списка
 >>> list.insert(0,4)
 
 //удаление элемента со значением 2
 >>> list.remove(2)
 
 //поиск позиции элемента в списке
 >>> list.index(3)
 
 //сортировка списка
 >>> list.sort()
 
 >>> list.reverse()
 
 //реализация стека на основе стандартного списка и методов append() и top()
 >>> stack = [3, 4, 5]
 >>> stack.append(6)
 >>> stack.append(7)
 >>> stack.pop()
 >>> stack.pop()
 
 //реализация очереди на основе встроенного класса
 from collections import deque
 >>> queue = deque([1,2,3,4,5])
 >>> queue.append(6)     
 >>> queue.append(7)     
 
 >>> queue.popleft()   
 

Организация списков на основе ссылок

В дальнейшем будут рассматриваться связные списки и деревья, построение которых немыслимо без ссылок. Под ссылкой понимается переменная, хранящая адрес объекта. На рисунке 1 показан список, построенный на основе ссылок.


Рисунок 1. Связанный список на основе ссылок
Рисунок 1. Связанный список на основе ссылок

Элемент FIRST - это переменная-ссылка, указывающая на первый элемент в списке. Такая организация списков, в отличие от традиционных массивов и стандартных списков, имеет следующие особенности, в которых есть как преимущества, так и недостатки.

Преимущества:

  1. Удаление элементов в таком списке более эффективно, нежели удаление элементов из стандартного списка Python, который рассматривался в предыдущем разделе. Так как этот элемент удаляется из середины стандартного списка, то время, необходимое на эту операцию, будет зависеть от нескольких факторов: размера списка, положения удаляемого элемента относительно конца. Чем больше размер списка, тем медленнее будет происходить данная операция. В данном случае со ссылочной организацией списка удаление будет происходить одинаково быстро, независимо от размера списка и относительного положения элемента, так как потребуется всего лишь перевести ссылку в предыдущем элементе на следующий за удаляемым элемент.
  2. То же самое можно сказать и про вставку элементов - она выполняется так же эффективно, как и удаление.
  3. Объединение или разбиение 2-х списков будет выполняться быстрее, нежели в стандартном варианте.
  4. Преимуществом связных списков является и то, что элемент такого списка может иметь произвольную структуру, и включать не одну, а сразу несколько ссылок, что является отличительной особенностью деревьев.

Недостатки:

  1. Требуется выделять дополнительную память на ссылки, которые сами по себе не несут никакой полезной информации.
  2. Доступ к произвольному элементу для стандартного массива в Си и для стандартного списка в Python есть величина постоянная и не зависящая от величины массива. В случае со ссылочными списками время доступа будет зависеть от величины списка, так как потребуется выполнить итерацию по всему списку.

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

Часть 2

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

Массивы и связные списки

Связные списки используются, когда требуется структура данных, размер которой заранее неизвестен. В такие списки можно добавлять и удалять элементы уже после создания самого списка. Однако такой список требует дополнительных усилий для поддержания целостности при динамических операциях, так как при удалении элемента из списка обрывается связь между элементами, находящимися до и после него, и эти элементы необходимо снова связать между собой.

Списки широко используются в реальных проектах - операционных системах, базах данных, но для работы с ними требуется знать, как устроена арифметика указателей. В листинге 1 представлен массив из 100 элементов и инициализируются его первые 3 значения.


Листинг 1. Инициализация массива
 
 
 int my_array[100];
 my_array[0]=1;
 my_array[1]=20;
 my_array[2]=100;
 
 

Физически все 100 элементов располагаются в памяти последовательно, и индекс элемента - это смещение в блоке памяти от его начала, поэтому извлечение элемента по индексу выполняется крайне быстро. Это и есть адресная арифметика, но так как память для стандартного массива выделяется на этапе компиляции, то и модифицировать его впоследствии уже нельзя.

Для выделения памяти для связного списка используется иной механизм, когда память выделяется динамически, во время работы программы. Данный тип памяти называется «куча» (heap) и добавляемые элементы физически могут располагаться в такой куче без всякого упорядочивания.

Создание связного списка на языке Си

Элемент (узел) - это область памяти, в которой хранится ячейка связного списка. Узел односвязного списка состоит из 2-х полей: в первом хранятся данные (это поле также называется ключом), а во втором - указатель на следующий узел. Существует специальный указатель head, указывающий на первый узел списка. Указатель head – это отдельная переменная, не принадлежащая списку. Последний узел в списке указывает на NULL, и для него тоже создается специальная переменная - указатель tail. Если первый элемент указывает на NULL, то это будет пустой список. В листинге 2 приведена структура для определения элемента списка:


Листинг 2. Структура для элемента списка
 
 
 struct node 
 {
    int          data;
    struct node* next;
 };
 
 

Указатель next имеет тот же тип, что и сам элемент, и указывает на следующий элемент списка. В листинге 3 приведен пример создания списка из трех элементов.


Листинг 3. Создание списка из трех элементов
 
 
 
 // объявить три указателя на элементы списка
 // указатель head ведет на первый элемент списка
 	struct node* head = NULL;
 	struct node* second = NULL;
 	struct node* third = NULL;
 
 // выделить память под элементы
 //	метод sizeof вычисляет размер элемента
 //	метод malloc выделяет требуемое количество памяти
 // установить указатели на выделенные фрагменты памяти
 	head   = malloc(sizeof(struct node));
 	second = malloc(sizeof(struct node));
 	third  = malloc(sizeof(struct node));
 
 // инициализировать элементы списка и связать их между собой
 	head->data = 1;
 	head->next = second;
 	second->data = 2;
 	second->next = third;
 	third->data = 3;
 	third->next = NULL;
 
 

Создание связного списка в Python

В Python существует стандартная реализация списка, но ее не рекомендуется использовать из-за проблем с производительностью при выполнении динамических операций, о чем говорилось в прошлой статье. В листинге 4 представлен класс Node для определения элемента списка.


Листинг 4. Объявление элемента списка в Python
 
 
 class Node:
     def __init__(self, value = None, next = None):
         self.value = value
         self.next = next
 
 

Для определения связного списка потребуется еще один класс – LinkedList, в конструкторе которого будут определяться первый и последний элементы списка и его длина. Также в классе будут использоваться встроенный метод str для распечатки содержимого списка и метод clear для очистки списка.


Листинг 5. Исходный код класса Linked List
 
 
 import copy
 import random 
 
 class LinkedList:
     def __init__(self):
         self.first = None
         self.last = None
         self.length = 0
 
     def __str__(self):
         if self.first != None:
             current = self.first
             out = 'LinkedList [\n' +str(current.value) +'\n'
             while current.next != None:
                 current = current.next
                 out += str(current.value) + '\n'
             return out + ']'
         return 'LinkedList []'
 
     def clear(self):
         self.__init__()
 
 //создание связного списка из 3-х элементов
 L = LinkedList()
 L.add(1)
 L.add(2)
 L.add(3)
 
 

Определение длины списка

Чтобы определить размер связного списка, необходимо пройти по списку и посчитать количество узлов. В листинге 6 приведена функция для подсчета числа узлов.


Листинг 6. Функция на языке Си для определения длины списка
 
 
 	int Length(struct node* head) 
 	{
 		struct node* current = head;
 		int count = 0;
 		while (current != NULL) 
 		{
 				count++;
 				current = current->next;
 		}
 		return count;
 	}
 
 

В этой функции создается дополнительный указатель current, с помощью которого выполняется ИТЕРАЦИЯ связного списка:

	current = current->next;
 

При этой операции со списком ничего не происходит, но указателю НАЗНАЧАЕТСЯ новое значение. Если вызвать эту функцию для пустого списка, у которого вершина равна NULL, то функция вернет ноль. Для определения длины списка в Python используется функция Len (см. листинг 7), которая вначале проверяет, не является ли список пустым, а затем выполняет итерацию по элементам списка.


Листинг 7. Функция на языке Python для определения длины списка
 
 
     def Len(self):
         self.length =0
         if self.first != None:
             self.length +=1
             current = self.first
             while current.next != None:
                 current = current.next
                 self.length +=1
         return self.length
 
 

Добавление элемента в начало списка

В листинге 8 приведена функция Push для добавления элементов в начало списка в обратном порядке.


Листинг 8. Функция для добавления элементов в начало списка
 
 
 void Push(struct node** headRef, int data) 
 	{
 		struct node* newNode = malloc(sizeof(struct node));
 		newNode->data = data;
 		newNode->next = *headRef;  
 		*headRef = newNode;        
 	}
 
 // пример использования этой функции
 struct node* head = NULL; // создание первого элемента
 Push(&head, 1);
 Push(&head, 2);
 Push(&head, 3);
 
 

Символ & - это указание компилятору, что параметр передается по ссылке, т.е. все изменения, которые будут сделаны с этим параметром внутри функции, останутся актуальными для переданного объекта и после выхода из функции. При передаче параметров по ссылке нужно следовать трем правилам:

  1. в определении функции для указателей нужно использовать двойной указатель **;
  2. при вызове функции перед ссылочным параметром нужно поставить &;
  3. в самой функции к ссылочному параметру обращаться через указатель *.

Листинг 9. Реализация функции Push на языке Python
 
 
     def Push(self, x):
         if self.first == None:
             self.first = Node(x,None)
             self.last = self.first
         else:
             self.first = Node(x,self.first)
 
 

В Python-реализации учитываются два варианта: в первом случае список пуст, а во втором создается новый узел, в конструктор которого в качестве второго параметра передается головной элемент списка.

Добавление элементов в конец списка

В листинге 10 представлен пример добавления элементов в конец списка.


Листинг 10. Си – добавление элемента в конец списка
 
 
 struct node* AppendNode(struct node** headRef, int num) 
 {
    struct node* current = *headRef;
    struct node* newNode;
    newNode = malloc(sizeof(struct node));
    newNode->data = num;
    newNode->next = NULL;
    // если список пуст
    if (current == NULL) {
       *headRef = newNode;
    }
    else {
       // иначе
       while (current->next != NULL) {
           current = current->next;
       }
       current->next = newNode;
    }
 }
 
 

В представленном коде выполняется итерация по списку для поиска последнего элемента, а затем его указатель next устанавливается на добавляемый элемент.


Листинг 11. Python - добавление элемента в конец списка
 
 
     def add(self, x):
         if self.first == None:
             self.first = Node(x, None)
             self.last = self.first
         elif self.last == self.first:
             self.last = Node(x, None)
             self.first.next = self.last
         else:
             current = Node(x, None)
             self.last.next = current
             self.last = current
 
 

Вставка элемента на определенную позицию в списке

Для вставки элемента в список необходимо передать указатель на головной элемент, индекс позиции, куда будет вставлен элемент, и, собственно, сам элемент. Если индекс равен нулю, то вызывается функция Push, в противном случае выполняется итерация, а затем снова происходит вызов Push.


Листинг 12. Си - вставка элемента в список
 
 
 void InsertNth(struct node** headRef, int index, int data) 
 {
   if (index == 0) Push(headRef, data);
   else 
   {
     struct node* current = *headRef;
     int i;
     for (i=0; i<index-1; i++) 
     {
       current = current->next;
     }
     Push(&(current->next), data); 
   }
 }
 
 

В Python необходимо сначала проверить, что список не пуст, а затем, что вставка не происходит на нулевую позицию. Если оба условия не выполняются, то происходит итерация по списку до нужной позиции и добавление элемента:


Листинг 13. Python – вставка элемента в список
 
 
     def InsertNth(self,i,x):
         if (self.first == None):
             self.first = Node(x,self.first)
             self.last = self.first.next
             return
         if i == 0:
           self.first = Node(x,self.first)
           return
         curr=self.first
         count = 0
         while curr != None:
             if count == i-1:
               curr.next = Node(x,curr.next)
               if curr.next.next == None:
                 self.last = curr.next
               break
             curr = curr.next
 
 

Удаление головного элемента

Функция Pop удаляет из списка головной узел, вместе с функцией Push она реализует функциональность стека, отцепляя головной элемент от списка и освобождая память. Функция принимает на вход двойной указатель на головной элемент, а возвращает значение удаленного элемента.


Листинг 14. Функция Pop – реализация на языке Си
 
 
 int Pop(struct node ** head)
 {
   struct node * temp = *head;
   int data=temp->data;
   *head = temp->next;
   free(temp);
   return data;
 }
 
 

Для реализации на Python потребуется создать временную локальную переменную для хранения головного элемента. Если список не пустой, то головным узлом становится элемент, следующий за узлом, сохраненным во временной переменной.


Листинг 15. Функция Pop – реализация на Python
 
 
     def Pop(self):
         oldhead=self.first
         if oldhead==None:
             return None
         self.first=oldhead.next
         if self.first==None:
             self.last=None
         return oldhead.value
 
 

Удаление элемента из списка

В листинге 16 приведена реализация функции для удаления элемента из списка на языке Си.


Листинг 16. Си - удаление элемента из списка
 
 
 int Del(struct node ** head,int index)
 {
   int data = (*head)->data;
   if(index==0) Pop(head);
   else
   {
     int i;
     struct node * current = *head;
     for(i=0;i<index-1;i++)
       current=current->next;
     Pop(&(current->next));
   }
   return data;
 };
 
 

В реализации для Python потребуется проверить список на пустоту и объявить две локальных переменных: первая будет хранить текущий элемент, а вторая - предыдущий. Потом выполняется итерация по списку для поиска удаляемого элемента и проверка того, не является ли он последним в списке. Если удаляемый элемент является последним, то предыдущий узел становится последним, в противном случае предыдущий узел связывается со следующим узлом вместо текущего.


Листинг 17. Python - удаление элемента из списка
 
 
     def Del(self,i):
         if (self.first == None):
           return
         old = curr = self.first
         count = 0
         if i == 0:
           self.first = self.first.next
           return
         while curr != None:
             if count == i:
               if curr.next == self.last:
                 self.last = curr
                 break
               else:
                 old.next = curr.next 
               break
             old = curr  
             curr = curr.next
             count += 1
 
 

Вставка элемента в отсортированный список

В листинге 18 представлена функция для вставки элемента в отсортированный список. Как обычно, сначала выполняется проверка, что список не пустой, а затем итерация в поисках ближайшего элемента, значение которого меньше, чем у добавляемого.


Листинг 18. Си - вставка элемента в отсортированный список
 
 
 void SortedInsert(struct node** headRef, struct node* newNode) 
 {
   if (*headRef == NULL || (*headRef)->data >= newNode->data) 
   {
     newNode->next = *headRef;
     *headRef = newNode;
   }
   else 
   {
     struct node* current = *headRef;
     while (current->next!=NULL && current->next->data < newNode->data) 
     {
       current = current->next;
     }
     newNode->next = current->next;
     current->next = newNode;
   }
 }
 
 

В реализации на языке Python выполняется проверка списка на пустоту, а затем выполняется итерация с помощью двух временных переменных, как и в листинге 18.


Листинг 19. Python – вставка элемента в отсортированный список
 
 
     def SortedInsert(self,x):
         if (self.first == None):
           self.first = Node(x,self.last)
           return
         if self.first.value > x:
           self.first = Node(x,self.first)
           return
         old = curr = self.first
         while curr != None:
             if curr.value > x:
               curr = Node(x,curr)
               old.next = curr
               return
             old = curr
             curr = curr.next
         curr = Node(x,None)        
         old.next = curr
 
 

Удаление повторяющихся значений

Данная функция должна применяться к уже отсортированному списку. В качестве параметра в неё передается головной узел списка, и если в ходе итерации текущий элемент оказывается равным следующему за ним, то текущий элемент удаляется.


Листинг 20. Си – удаление повторяющихся значений
 
 
 void RemoveDuplicates(struct node* head) 
 {
   struct node* current = head;
   if (current == NULL) return;
   while(current->next!=NULL) 
   {
     if (current->data == current->next->data) 
     {
       struct node* nextNext = current->next->next;
       free(current->next);
       current->next = nextNext;
     }
     else 
     {
       current = current->next;
     }
   }
 }
 
 

В версии на языке Python добавляется флаг, отмечающий наличие повторяющегося элемента. Этот флаг устанавливается при удалении повторяющегося элемента, и итерация прекращается, в противном случае итерация продолжается.


Листинг 21. Python – удаление повторяющихся значений
 
 
     def RemoveDuplicates(self):
         if (self.first == None):
             return
         old = curr = self.first
         while curr != None:
             _del = 0 
             if curr.next != None:
                 if curr.value == curr.next.value:
                   curr.next = curr.next.next
                   _del = 1
             if _del == 0:
               curr = curr.next
 
 

Копирование списков

В листинге 22 показана функция для копирования списков. В ней используется три указателя: на первый элемент оригинального списка и на первый и последний элементы скопированного списка.


Листинг 22. Си – копирование списков
 
 
 struct node* CopyList(struct node* head) 
 {
    struct node* current = head; //первый элемент оригинального списка
    struct node* newList = NULL; //первый элемент нового списка
    struct node* tail = NULL; //последний элемент нового списка
    while (current != NULL) 
    {
       if (newList == NULL)  //создается первый элемент нового списка
       { 
          newList = malloc(sizeof(struct node));
          newList->data = current->data;
          newList->next = NULL;
          tail = newList;
       }
       else 
       {
          tail->next = malloc(sizeof(struct node));
          tail = tail->next;
          tail->data = current->data;
          tail->next = NULL;
       }
       current = current->next;
    }
    return(newList);
 }
 
 

В листинге 23 приведена реализация этой же функциональности, но на основе рекурсии.


Листинг 23. Си - копирование списков на основе рекурсии
 
 
 struct node* CopyList(struct node* head) 
 {
    struct node* current = head;      
    if (head == NULL) return NULL;
    else 
 	{
       struct node* newList = malloc(sizeof(struct node));   
       newList->data = current->data;
       newList->next = CopyList(current->next);  
       return(newList);
    }
 }
 
 

В Python для копирования списков можно использовать стандартный модуль copy, как показано ниже.

import copy
 L2 = copy.deepcopy(L) // создание копии списка L
 
 

Тестирование производительности

Следующий тест показывает основное преимущество компилируемых языков перед интерпретаторами - преимущество в скорости. В следующем тесте создается одно-связный список длиной в 2000 нод, при этом ключ в ноде может иметь значение от 0 до 100. Ноды вставляются в отсортированном порядке. Т.е. например начало списка может быть таким:

0 1 1 2 2 2 2 3 4 5 7 9 10 10 10 .....

Выяснилась следующая вещь: реализация одного и того же алгоритма вставки случайных нод в связный список в отсортированном порядке ведет себя по-разному в зависимости от языка, а также от величины списка. Различия начинают сильно проявляться начиная с длины списка от нескольких тысяч, причем не в пользу питона. Итерация в питоне начинает тормозить на моей машине начиная где-то с 2-х тысяч. Профайл теста показывает, что основная потеря процессорного времени уходит именно на итерацию.

Тестовый код:

 
 
 import profile
 import random 
 import time
 
 
 class Node:
     def __init__(self, value = None, next = None):
         self.value = value
         self.next = next
 
 class LinkedList:
     def __init__(self):
         self.first = None
         self.last  = None
         self.old   = None
         self.curr  = None
         self.ins   = 0
 
     def __str__(self):
         if self.first != None:
             current = self.first
             out = 'LinkedList = ' +str(current.value) +' '
             while current.next != None:
                 current = current.next
                 out += str(current.value) + ' '
             return out + ''
         return ''
 
 def main():
   t1 = time.time()
   L  = LinkedList()
 
   for i in range ( 0, 2000 ) : 
     _r = int ( random.uniform ( 0, 100 ) )
     if L.first == None:
         L.first = Node(i,None)
     elif L.first.value > _r:
           L.first = Node(_r,L.first)
     else:
         L.old = L.curr = L.first
         L.ins=0
         while L.curr != None:
             if L.curr.value > _r:
               L.curr = Node(_r,L.curr)
               L.old.next = L.curr
               L.ins = 1
               break
             L.old = L.curr
             L.curr = L.curr.next
         if L.ins == 0:    
           L.curr = Node(_r,None)
           L.old.next = L.curr
 
   print L
   t2 = time.time()
   print "\t%.1f" % ((t2 - t1))
 
 
 profile.run('main()')
 
 
Си-шный вариант теста:
 
 
 #include < stdio.h>
 #include < stdlib.h>
 #include < time.h>  
 
 struct node
 {
   int data;
   struct node * next;
 };
 
 
 void SortedInsert(struct node** headRef, struct node* newNode) 
 {
   if (*headRef == NULL || (*headRef)->data >= newNode->data) 
   {
     newNode->next = *headRef;
     *headRef = newNode;
   }
   else 
   {
     struct node* current = *headRef;
     while (current->next!=NULL && current->next->data < newNode->data) 
     {
       current = current->next;
     }
     newNode->next = current->next;
     current->next = newNode;
   }
 }
 
 
 int main()
 {
 
   time_t start,end;
   volatile long unsigned t;
   start = time(NULL);
       
    
   struct node * List = NULL;
   struct node * new;
   int i = 0 ;
   srand((unsigned int)time(NULL));
   for (i = 0; i< 2000 ; i++)
   {
     new = malloc(sizeof(struct node));
     new->data = rand() % 100 + 1;
     SortedInsert(&List,new); 
   }
   
   
   end = time(NULL);
   printf("Loop  %f seconds.\n", difftime(end, start));
   
   return 0;
 }
 
 
Си-шная версия работает практически мгновенно, хотя и ее можно заставить тормозить, но это начинается с гораздо более высокого числового порога. Питоновскую же версию не спасают попытки сделать оптимизацию кода, например за счет сокращения вызовов функции SortedInsert. При динамическом создании обьектов в питоне начиная с определенного момента начинаются проблемы с их итерацией.

В ходе тестирования было выяснено, что реализация одного и того же алгоритма для вставки элементов в отсортированный связный список ведет себя по-разному в зависимости от языка и размера списка. Производительность Python-реализации начинает снижаться, когда в списке накапливается более 2-х тысяч элементов. Анализ результатов теста показывает, что основные потери процессорного времени происходят во время итерации.

Исходный код тестов на языках Си и Python можно найти в архиве performance_benchmark.zip, прикрепленном к статье. Реализация на языке Си работает гораздо быстрее, и ее производительность начинает снижаться, когда размер списка становится значительно больше 2-х тысяч элементов. Версию на языке Python не спасает даже оптимизация кода за счет сокращения вызовов функции SortedInser, так как из-за динамического создания объектов в Python, начиная с определенного момента, возникают проблемы при итерации.

Cвязные списки предоставляют богатый набор функций для добавления и удаления элементов, сортировки, копирования и других операций. Поэтому связные списки являются «краеугольным камнем» и первой ступенью для изучения других структур данных связного типа.

Часть 3

Классификация связных списков

История связных списков

Основной принцип связных списков крайне прост: эта структура данных состоит из последовательности записей, в которой каждая запись хранит помимо самих данных еще и ссылку на следующую запись в этой последовательности. На рисунке 1 изображен связный список из трех записей, каждая запись которого состоит из поля данных - целого числа и ссылки на следующую запись.


Рисунок 1. Пример связного списка
Рисунок 1. Пример связного списка

У последней записи на рисунке отсутствует ссылка, но она есть и указывает на NULL. На основе списков можно реализовать структуры данных, такие как стеки, очереди и ассоциативные массивы.

Ранее уже упоминалось, что в массиве все элементы расположены в памяти по порядку, а в списке они в памяти никак не упорядочены. Более того, элемент может быть добавлен в любую позицию в списке. Однако сама операция по вставке элемента в список требует дополнительных ресурсов, так как нужно последовательно просканировать список для поиска нужной позиции.

В классическом языке Си есть только массив, но отсутствует встроенная реализация связного списка. Однако в других языках, например, в Lisp, существует встроенная реализация данной структуры. Официальная «дата рождения» связных списков - 1955 год, когда они появились на стыке логической теории машин и алгоритмов для решения шахматных задач. Тогда же связные списки начали использоваться для решения проблем трансляции натуральных языков в лингвистических задачах. В 1958 году появился язык Lisp, и связный список стал одной из базовых структур этого языка.

Связные списки стали применяться и при разработке операционных систем, например, для реализации файловых систем. Так, для операционной системы TSS/360 компания IBM разработала двойные связные списки и утилиту на их основе для исправления ошибок в файловой системе. Если при сканировании каталога обнаруживался поврежденный элемент, то происходил откат с заменой поврежденного элемента на его предыдущую версию.

Основные правила реализации связных списков

Список состоит из элементов, называемых узлами (node). Первый узел списка называется «головным» (head), а последний - «хвостовым» (tail). На рисунке 2 изображен двойной связный список.


Рисунок 2. Двойной связный список
Рисунок 2. Двойной связный список

Каждый элемент состоит из 3-х полей, два из которых являются указателями на предыдущий или следующий узел. Элемент может указывать и более чем на два узла, и в этом случае список называется многосвязным.

Помимо упоминавшихся ранее стандартных массивов существуют еще динамические массивы. Размер обычного массива является фиксированной величиной, а в динамический массив можно добавлять или удалять из него элементы. Если элемент добавляется в середину динамического массива, то происходит перераспределение элементов, находящихся справа от него, так как все элементы массива должны быть расположены в памяти строго по порядку. Поэтому вставка элемента в динамический массив требует дополнительных ресурсов, если элемент добавляется не в конец массива. Преимущество связного списка в том, что не требуется перестраивать последовательность узлов, независимо от того, в какую позицию списка вставляется новый элемент. Недостаток связных списков – это последовательный доступ (sequential access) к элементам, тогда как для массивов время доступа постоянно и не зависит от размера - random access. Если приложению требуется быстрый поиск элемента по индексу, то в данном случае списки не подходят, и лучше воспользоваться массивами.

Еще один негативный момент при использовании связных списков связан с нерациональным использованием памяти. Если в узле хранится небольшая порция данных, например, булевское значение, то список становится неэффективными из-за того, что объем памяти, выделяемой под хранение связей, превышает объем памяти, выделяемой под хранение «полезной нагрузки». Для решения этой проблемы существуют развернутые связные списки - unrolled linked list, каждый элемент которого включает целый массив данных. Пример такого списка приведен в листинге 1.


Листинг 1. Развернутый связный список
 
 
 record node 
 {
      node next;
      int numElements;
      array elements;
 }
 
 

Связный список - это рекурсивная структура, так как узел всегда содержит указатель на следующий узел. Это позволяет использовать простой рекурсивный алгоритм для таких операций, как объединение двух списков или изменение порядка элементов на обратный. У односвязных списков есть важное преимущество: если к вершине такого списка добавляется новый элемент, то старый список будет по прежнему доступен по ссылке на только что добавленный узел. Этот прием называется persistent data structure (постоянное хранение данных). У двусвязных списков есть свои преимущества, так как они позволяют выполнять итерацию в обоих направлениях, в отличие от односвязных списков.

Если последний элемент будет указывать на первый элемент списка, то такая структура называется циклическим замкнутым (или кольцевым (circular)) списком. Кольцевые списки можно использовать для списка процессов, в которых применяется «карусельный» (round-robin) алгоритм. Для такого списка достаточно иметь один указатель, который одновременно указывает и на конец, и на начало очереди. Кольцевой список можно разбить на два кольцевых списка или, наоборот, объединить.


Рисунок 3. Кольцевой связный список
Рисунок 3. Кольцевой связный список
Топологическая сортировка

Примеры топологической сортировки

Техническая задача разбивается на ряд подзадач, при этом выполнение одних подзадач должно предшествовать выполнению других подзадач. Топологическая сортировка означает выполнение подзадач в таком порядке, чтобы перед началом выполнения каждой подзадачи все необходимые для этого подзадачи были уже выполнены.

В программе некоторые процедуры могут вызывать другие процедуры. Топологическая сортировка предполагает расположение описаний процедур в таком порядке, чтобы вызываемые процедуры описывались раньше тех, которые их вызывают.

Под топологической сортировкой понимается сортировка элементов, для которых определен частичный порядок, т.е. упорядочивание задано не для всех, а только для некоторых пар элементов.

Предполагается, что существует множество из 3-х элементов a, b и c, которое удовлетворяет трем правилам:

  • транзитивность: если a < b и b < c , то a < c;
  • асимметричность: если a < b , то не b < a;
  • антирефлексивность: невозможность a < a.

Цель топологической сортировки - преобразование частичного порядка в линейный. Графически процесс топологической сортировки показан на рисунках 4 и 5.


Рисунок 4. Исходное множество
Рисунок 4. Исходное множество

Рисунок 5. Результат топологической сортировки
Рисунок 5. Результат топологической сортировки

Топологическая сортировка начинается с того, что во множестве выбирается элемент, которому не предшествует никакой другой. Этот элемент помещается в начало списка и исключается из множества. В оставшемся множестве опять выбирается такой же по свойству элемент, и все повторяется до тех пор, пока множество не станет пустым. Для подобного алгоритма потребуются две структуры, первая будет называться лидером (leader), а вторая - ведомой (trailer).


Листинг 2. Структуры для топологической сортировки
 
 
 struct trailer
 {
   struct leader * id;
   struct trailer * next;
 };
 
 struct leader
 {
   int key;
   int count;
   struct leader * next;
   struct trailer * trail;
 };
 
 

Элемент исходного множества, содержащийся в нем только один раз, является лидером, а остальные — ведомыми. Первоначально исходное множество задается в виде списка пар, как показано в листинге 3.


Листинг 3. Исходное множество
 1 < 2
 2 < 4
 4 < 6 
 1 < 3
 3 < 5
 ...
 
 

На первом шаге эти пары читаются и создается список лидеров. Затем для каждого лидера формируется свой список ведомых. На платформе Unix есть специальная консольная утилита tsort, которая получает на вход список пар и выдает конечный линейный список.


Листинг 4. Использование утилиты tsort
 $ tsort <<EOF
 > 3 8
 > 3 10
 > 5 11
 > 7 8
 > 7 11
 
 > 8 9
 > 11 2
 > 11 9
 > 11 10
 > EOF
 3
 5
 7
 11
 8
 10
 2
 9
 

Задача Иосифа Флавия

Иосиф Флавий - это исторический деятель, живший в первом веке нашей эры, с которым была связана одна драматическая история. Однажды он и еще 40 солдат оказались запертыми в пещере. Они решили не сдаваться римлянам, убив себя самих. Они встали в круг, 40 человек. Выбрали первого, который убил себя тут же на месте. Затем отсчитали по кругу, по часовой стрелке, троих, и тот, на кого упал счет, также убил себя. И так далее по кругу, отсчитывая троих. В конце концов в круге осталось всего 2 человека, одним из которых и был Flavius Josephus. Они и вышли к римлянам живыми вдвоем.

Об этой истории можно прочесть по ссылке, но в рамках статьи больший интерес представляет математическая задача, связанная с этой историей. В этой задаче предлагается вычислить, какой элемент останется последним в списке, если из списка последовательно будет удаляться каждый третий элемент, как показано на рисунке 6.


Рисунок 6. Задача Иосифа Флавия
Рисунок 6. Задача Иосифа Флавия

На рисунке 6, если начать отсчет с нулевого индекса, продвигаться по часовой стрелке и уничтожать каждый третий элемент, то останутся только элементы с индексами 1 и 7. Для моделирования этой ситуации можно взять кольцевой связный список или обычный массив. В связном списке удалить элемент гораздо проще, чем найти последний узел, который останется после удаления всех узлов, не удаляя физически элементов из списка.

В представленном алгоритме для решения задачи Иосифа Флавия для поиска последнего «оставшегося в живых» элемента используется двусвязный круговой список. В процессе поиска происходит динамическое удаление элементов из списка и перестройка связей для поддержки целостности списка. Оба варианта решения задачи на языках Си и Python находятся в файлах last_man_standing_task.c и last_man_standing_task.py, упакованных в архив sources.zip, прикрепленный к статье. Реализация алгоритма на языке Python получилась в два раза компактнее, чем на языке Си.

Использование связных списков в ядре Linux

В ядре Linux применяется особая реализация связных списков, в которой используются специальные алгоритмы для добавления/удаления элементов в список. В листинге 5 показан элемент связного списка, включающий структуру list_head.


Листинг 5. Элемент связного списка, используемого в ядре Linux
 
 
 struct mystruct 
 {
     int data ;
     struct list_head mylist ;
 } ;
 
 

Если структуру list_head добавить к любой другой структуре, то эта структура станет частью связного списка. В листинге 6 создаются два элемента связного списка и инициализируются двумя различными способами.


Листинг 6. Два способа инициализации
 
 
     struct mystruct first = 
 	{
 		.data = 10,
 		.mylist = LIST_HEAD_INIT(first.mylist)
 	} ;
 
 	struct mystruct second ;
 	second.data = 20 ;
 	INIT_LIST_HEAD( & second.mylist ) ;
 
 

Метод LIST_HEAD_INIT, используемый в первом варианте, - это следующий макрос:

	#define LIST_HEAD_INIT(name) { &(name), &(name) }
 

В ядре Linux макросы используются вместо обычных функций, так как макросы позволяют сгенерировать более эффективный код, что положительно сказывается на производительности. Во втором варианте используется inline-функция, приведенная в листинге 7.


Листинг 7. Функция для инициализации списка
 
 
 static inline void INIT_LIST_HEAD(struct list_head *list)
 {
      list->next = list;
      list->prev = list;
 }
 
 

Как видно из определения, создаваемый список является двусвязным, так как в нем содержатся указатели на следующий и предыдущий элементы. Использование inline-функции вместо обычной также окажет положительное влияние на производительность. Когда компилятор будет генерировать исполняемый код этой функции, то он поместит его в объектном файле непосредственно в то место, где была вызвана эта функция. Благодаря этому не потребуется тратить ресурсы на вызов функции.

Для создания самого списка, также будет использоваться макрос - LIST_HEAD:

	#define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)
 
 

А для добавления элементов будет использоваться inline-функция list_add, которая служит «оболочкой» для вызова еще одной функции __list_add.


Листинг 8. Функции для добавления элементов в список
 
 
 	static inline void list_add(struct list_head *new, struct list_head *head)
 	{
 	__list_add(new, head, head->next);
 	}
 
 static inline void __list_add(struct list_head *new,
                                struct list_head *prev,
                                struct list_head *next)
 {
          next->prev = new;
          new->next = next;
          new->prev = prev;
          prev->next = new;
 }
 
 

Теперь можно добавить элементы в только что созданный список:

	list_add ( &first.mylist , &mylinkedlist ) ;
 	list_add ( &second.mylist , &mylinkedlist ) ;
 

В результате получится связный список, состоящий из 2-х элементов, и указатель на первый элемент в переменной mylinkedlist. Для просмотра содержимого списка или выполнения итерации также используются макросы с целью получения быстрого и эффективного исполняемого кода.


Листинг 9. Макрос для просмотра содержимого списка
 
 
 #define list_for_each(pos, head) \
          for (pos = (head)->next; prefetch(pos->next), pos != (head); \
                  pos = pos->next)
 
 


Листинг 10. Использование макроса для итерации по списку
 
 
 struct list_head* position ;
 list_for_each ( position , & mylinkedlist )
     {
          printk ("surfing the linked list next = %p and prev = %p\n" ,
              position->next,
              position->prev );
     }
 
 

Исходный код в листинге 11 суммирует всю информацию, представленную в этой статье. В нем демонстрируется реализация связного списка с помощью макроса define_list, принимающего на вход два параметра - имя списка и тип элемента. Также в листинге 11 объявлены уже знакомые и новые inline-функции, обеспечивающие функциональность связного списка. В методе main объявленные методы и структуры используются для создания связного списка из пяти элементов и последующей итерации по нему.


Листинг 11. Пример объявления и использования связного списка
 
 
 #include <stdbool.h>
 #include <stdio.h>
 #include <stdlib.h>
 
 /* объявление списка */
 struct list_head {
     struct list_head *next, *prev;
 };
 
 /* статический inline-метод для инициализации списка */
 static inline void INIT_LIST_HEAD(struct list_head *list)
 {
     list->next = list;
     list->prev = list;
 }
 
 /* статический inline-метод для вставки элемента в список */
 static inline void __list_add(struct list_head *new,
                   struct list_head *prev,
                   struct list_head *next)
 {
     next->prev = new;
     new->next = next;
     new->prev = prev;
     prev->next = new;
 }
 
 /* статический inline-метод для добавления элементов в конец списка */
 static inline void list_add_tail(struct list_head *new, struct list_head *head)
 {
     __list_add(new, head->prev, head);
 }
 
 #undef offsetof
 #ifdef __compiler_offsetof
 #define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER)
 #else
 #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
 #endif
 
 #define container_of(ptr, type, member) ({          \
     const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
     (type *)( (char *)__mptr – offsetof(type,member) );})
 
 #define list_entry(ptr, type, member) \
     container_of(ptr, type, member)
 
 /* реализация связного списка с необходимой функциональностью */
 #define define_list(name, type) \
     struct name##_head { \
         struct list_head _private; \
     }; \
     \
     static inline type *name##_head_first(struct name##_head *head) { \
         return list_entry(head->_private.next, type, name); \
     } \
     \
     static inline type *name##_next(const type *node) { \
         return list_entry(node->name.next, type, name); \
     } \
     \
     static inline bool name##_is_last(struct name##_head *head, const type *node) { \
         return &head->_private == &node->name; \
     } \
     \
     static inline void name##_init(struct name##_head *head) { \
         INIT_LIST_HEAD(&head->_private); \
     } \
     \
     static inline void name##_add_tail(struct name##_head *head, type *new) { \
         list_add_tail(&new->name, &head->_private); \
     }
 
 /* объявление элемента списка */
 struct node {
     struct list_head node_list;
 
     char *string;
 };
 
 /* объявление связного списка с заданным именем и нужным типом элементов */
 define_list(node_list, struct node);
 
 struct node *new_node(const char *string)
 {
     struct node *ret = malloc(sizeof struct node);
     ret->string = string;
     return ret;
 }
 
 /* метод main */
 int main(int argc, char *argv[])
 {
     /* создание и инициализация списка */
     struct node_list_head head;
     node_list_init(&head);
 
     /* добавление элементов в конец списка */
     node_list_add_tail(&head, new_node("1"));
     node_list_add_tail(&head, new_node("2"));
     node_list_add_tail(&head, new_node("3"));
     node_list_add_tail(&head, new_node("4"));
     node_list_add_tail(&head, new_node("5"));
 
     /* итерация по списку, начиная с первого элемента */
     for (struct node *i = node_list_head_first(&head);
         !node_list_is_last(&head, i); i = node_list_next(i))
     {
         printf("node: %s\n", i->string);
     }
 
     return 0;
 }
 
 

Ниже предлагается алгоритм решения проблемы иосифа, где будет использован циркулярный список, при этом будет найдена последняя оставшаяся в живых нода. Используется дву-связный циркулярный список. В процессе поиска происходит динамическое удаление нод из списка и необходимая перестройка связей для поддержки целосности списка.
 
 
 #include < stdio.h>
 #include < stdlib.h>
 #include < time.h>
 #include < sys/time.h>
 
 
 class Person
 {
 
     public:
 
         Person(int count) : _next(NULL), _prev(NULL) { _count = count; }
         int shout(int shout, int nth)
         {
             if (shout < nth) return (shout + 1);
             _prev->_next = _next;
 
             _next->_prev = _prev;
             return 1;
         }
         int count() { return _count; }
         Person* next() { return _next; }
         void next(Person* person) { this->_next = person ; }
         Person* prev() { return _prev; }
         void prev(Person* person) { this->_prev = person; }
     private:
         int _count;
         Person* _next;
         Person* _prev;
 };
 
 class Chain
 {
     public:
         Chain(int size) : _first(NULL)
         {
             Person* current = NULL;
             Person* last = NULL;
             for(int i = 0 ; i < size ; i++)
             {
                 current = new Person(i);
                 if (_first == NULL) _first = current;
                 if (last != NULL)
                 {
                     last->next(current);
                     current->prev(last);
                 }
                 last = current;
             }
             _first->prev(last);
             last->next(_first);
         }
      
         Person* kill(int nth)
         {
             Person* current = _first;
             int shout = 1;
             while(current->next() != current)
             {
                 Person* tmp = current;
                 shout = current->shout(shout,nth);
                 current = current->next();
                 if (shout == 1)
                 {
                   printf("kill %d\n",tmp->count());
                   delete tmp;
                 }
             }
             _first = current;
             return current;
         }
         Person* first() { return _first; }
     private:
         Person* _first;
 };
 
 int main(int argc, char** argv)
 {
     Chain* chain;
     chain = new Chain(10);
     printf("result: %d\n",chain->kill(3)->count());
     delete chain;
     return 0;
 }
 
 
Аналогичная реализация на питоне:
 
 
 class Person(object):
     def __init__(self,count):
         self.count = count;
         self.prev = None 
 
         self.next = None
     def shout(self,shout,deadif):
         if (shout < deadif): return (shout + 1)
         self.prev.next = self.next
         self.next.prev = self.prev
         return 1
 
 class Chain(object):
     def __init__(self,size):
         self.first = None
         last = None
         for i in range(size):
             current = Person(i)
             if self.first == None : self.first = current
             if last != None :
                 last.next = current
                 current.prev = last
             last = current
         self.first.prev = last
         last.next = self.first
     def kill(self,nth):
         current = self.first
         shout = 1
         while current.next != current:
             shout = current.shout(shout,nth)
             if shout ==1:
               print current.count
             current = current.next
         self.first = current
         return current.count
 
 import time
 chain = Chain(40)
 print chain.kill(3)
 
 

В данной статье рассматривались связные списки, которые относятся к наиболее важным структурам данных, использующихся в современном программировании. В статье рассматривались как теоретические аспекты со связными списками (задача Иосифа Флавия), так и практическая реализация связных списков в ядре ОС Linux. Для теоретической задачи была разработана реализация на двух различных языках программирования: Си и Python. Однако практическая задача была решена с помощью языка Си, так как в нем имеются такие возможности, как inline-функции и макросы, благодаря использованию которых можно значительно увеличить скорость работы приложения.

Часть 4

Связные списки и сортировка

Типы сортировок

Сортировка – это процесс перестановки объектов конечного множества в определенном порядке, предназначенный для облегчения последующего поиска элементов в уже отсортированном множестве. Для сортировки можно использовать огромное множество алгоритмов, поэтому часто требуется выполнить сравнительный анализ нескольких алгоритмов, чтобы определить оптимальный выбор для конкретной задачи.

Методы сортировки обычно разделяются на две категории: сортировка массивов и сортировка файлов, также называемые внутренней и внешней сортировкой, так как массивы располагаются во внутренней памяти, а файлы во внешней. Важнейшее требование к алгоритмам для сортировки массивов и связных списков - экономное расходование памяти, поэтому использование дополнительных массивов для сортировки считается дурным тоном.

Основным критерием для классификации алгоритмов сортировки является их быстродействие. При сортировке выполняются два типа операций - сравнение ключей и перестановка элементов (в случае со связными списками - переназначение указателей). Если в массиве n элементов, то алгоритм считается хорошим, если число перестановок равно произведению числа элементов массива n на логарифм этого числа log(n). Например, стандартная пузырьковая сортировка требует числа перестановок, равного квадрату от n.

Методы сортировки можно разбить на три основных класса:

  • сортировка включениями;
  • сортировка выбором;
  • сортировка обменом.

Принцип, лежащий в основе первого класса, заключается в том, что массив разбивается на две половины - итоговую и входную. Берется элемент из входной половины и вставляется в итоговую в порядке сортировки. Число перестановок элементов в общем случае равно квадрату от n.

В случае сортировки выбором алгоритм таков: берется минимальный элемент массива и ставится в начало массива, и т.д. Число перестановок элементов в общем случае меньше, чем в первом случае, и будет равно произведению числа элементов массива на логарифм от этого числа. Быстрая сортировка относится ко второму классу.

Пузырьковая сортировка

Первым будет рассматриваться алгоритм пузырьковой сортировки, который требует порядка n*n перестановок, поэтому является не самым удачным выбором. В функции llist_bubble_sort, приведенной в листинге 1, выполняется вложенная итерация по списку, с помощью которой реализуется алгоритм пузырьковой сортировки для языка Си.


Листинг 1. Реализация пузырьковой сортировки на языке Си
 
 
 #include <stdio.h>
 #include <stdlib.h>
 
 #define MAX 10
 
 struct lnode 
 {
  int data;
  struct lnode *next;
 } *head, *visit;
 
 void llist_add(struct lnode **q, int num);
 void llist_bubble_sort(void);
 void llist_print(void);
 
 int main(void) 
 {
  struct lnode *newnode = NULL;
  int i = 0;
 
  for(i = 0; i < MAX; i++) 
  {
    llist_add(&newnode, (rand() % 100));
  }
 
  head = newnode;
  printf("до пузырьковой сортировки:\n");
  llist_print();
  printf("после пузырьковой сортировки:\n");
  llist_bubble_sort();
  llist_print();
 
  return 0;
 }
 
 void llist_add(struct lnode **q, int num) 
 {
  struct lnode *tmp; 
  
  tmp = *q;
 
  if(*q == NULL) {
   *q = malloc(sizeof(struct lnode));
    tmp = *q;
  } else {
   while(tmp->next != NULL)
    tmp = tmp->next;
 
    tmp->next = malloc(sizeof(struct lnode));
    tmp = tmp->next;
  }
 
  tmp->data = num;
  tmp->next = NULL;
 }
 
 void llist_print(void) 
 {
  visit = head;
 
  while(visit != NULL) {
   printf("%d ", visit->data);
   visit = visit->next;
  }
  printf("\n");
 }
 
 void llist_bubble_sort(void) 
 {
  struct lnode *a = NULL;
  struct lnode *b = NULL; 
  struct lnode *c = NULL;
  struct lnode *e = NULL; 
  struct lnode *tmp = NULL; 
 
  while(e != head->next) 
  {
 	c = a = head;
 	b = a->next;
 		while(a != e) 
 		{
 			if(a->data > b->data) 
 			{
 				if(a == head) 
 				{
 					tmp = b -> next;
 					b->next = a;
 					a->next = tmp;
 					head = b;
 					c = b;
 				} 
 				else 
 				{
 					tmp = b->next;
 					b->next = a;
 					a->next = tmp;
 					c->next = b;
 					c = b;
 				}
 			} 
 			else 
 			{
 				c = a;
 				a = a->next;
 			}
 			b = a->next;
 			if(b == e)
 				e = a;
 		}
 	}
 }
 
 

В листинге 2 приведена реализация пузырьковой сортировки на языке Python с использованием стандартных списков, встроенных в Python.


Листинг 2. Реализация пузырьковой сортировки на языке Python
 
 
 import random 
 
 lista = [] 
 
 for i in range ( 0, 10 ) : 
   lista.append ( int ( random.uniform ( 0, 10 ) ) )
 
 print lista
 def bubble_sort ( lista ) :
   swap_test = False
   for i in range ( 0, len ( lista ) - 1 ):
     for j in range ( 0, len ( lista ) - i - 1 ):
       if lista[j] > lista[j + 1] :
         lista[j], lista[j + 1] = lista[j + 1], lista[j] 
         swap_test = True
     if swap_test == False:
       break
 
 bubble_sort ( lista ) 
 print lista
 
 

В листинге 3 приведен исходный код пузырьковой сортировки для Python, но уже на основе связных списков.


Листинг 3. Пузырьковая сортировка с использованием связных списков
 
 
 import random 
 
 class Node:
     def __init__(self, value = None, next = None):
         self.value = value
         self.next = next
 
     def __str__(self):
         return 'Node ['+str(self.value)+']'
 
 class LinkedList:
     def __init__(self):
         self.first = None
         self.last  = None
         self.length = 0
 
     def add(self, x):
         if self.first == None:
             self.first = Node(x, None)
             self.last = self.first
         elif self.last == self.first:
             self.last = Node(x, None)
             self.first.next = self.last
         else:
             current = Node(x, None)
             self.last.next = current
             self.last = current
 
     def __str__(self):
         if self.first != None:
             current = self.first
             out = 'LinkedList [ ' +str(current.value) +' '
             while current.next != None:
                 current = current.next
                 out += str(current.value) + ' '
             return out + ']\n'
         return 'LinkedList []'
 
     def BubbleSort(self):
        a = Node(0,None)
        b = Node(0,None)
        c = Node(0,None)
        e = Node(0,None)
        tmp = Node(0,None)
        
        while(e != self.first.next) :
         c = a = self.first
         b = a.next
 
         while a != e:
           if a and b:
             if a.value > b.value:
               if a == self.first:
                 tmp = b.next
                 b.next = a
                 a.next = tmp
                 self.first = b
                 c = b
               else:
                 tmp = b.next
                 b.next = a
                 a.next = tmp
                 c.next = b
                 c = b
             else:
               c = a
               a = a.next
             b = a.next
             if b == e:
               e = a
           else:
               e = a
               
     
 L  = LinkedList()
 
 for i in range ( 0, 10 ) : 
   L.add ( int ( random.uniform ( 0, 10 ) ) )
 
 print L
 L.BubbleSort()
 print L
 
 

Как можно увидеть, код в листинге 3 очень похож на код на языке Си, приведенный в листинге 1, поскольку в Python работа со ссылками на объекты реализована практически так же, как и в языке Си.

Быстрая сортировка

В данном разделе будет рассмотрен алгоритм быстрой (quicksort) сортировки двусвязного списка, на основе рекурсивной функции QuickSortList, представленной в листинге 4. Данная функция работает следующим образом:

  1. выполняется итерация по списку;
  2. в ходе итерации определяется максимальное значение, которое записывается в конец массива;
  3. выполняется следующая итерация, но без только что найденного максимума и т.д.

Листинг 4. Реализация быстрой сортировки на языке Си
 
 
 #include <stdio.h>
 
 // элемент двусвязного списка
 typedef struct _tagIntegerList
 {
 	int nInteger;
 	struct _tagIntegerList *pPrev;
 	struct _tagIntegerList *pNext;
 } IntegerList;
 
 
 // указатели на первый и последний элементы списка
 IntegerList *g_pFirstItem = NULL;
 IntegerList *g_pLastItem = NULL;
 
 // добавление в список
 void AddListItem(int nInteger)
 {
 	IntegerList *pItem = new IntegerList;
 	pItem->nInteger = nInteger;
 	if (g_pFirstItem == NULL)
 	{
 		g_pFirstItem = g_pLastItem = pItem;
 		pItem->pNext = pItem->pPrev = NULL;
 	}
 	else
 	{
 		g_pLastItem->pNext = pItem;
 		pItem->pPrev = g_pLastItem;
 		g_pLastItem = pItem;
 		pItem->pNext = NULL;
 	}
 }
 
 // удаление
 void RemoveAllItems()
 {
 	IntegerList *pDelItem, *pItem = g_pFirstItem;
 
 	while (pItem != NULL)
 	{
 		pDelItem = pItem;
 		pItem = pItem->pNext;
 		delete pDelItem;
 	}
 	g_pFirstItem = g_pLastItem = NULL;
 }
 
 // вывод содержимого списка в консоль
 void PrintList()
 {
 	IntegerList *pItem = g_pFirstItem;
 
 	while (pItem != NULL)
 	{
 		printf("%d  ", pItem->nInteger);
 		pItem = pItem->pNext;
 	}
 		printf("\n");
 }
 
 // быстрая сортировка
 void QuickSortList(IntegerList *pLeft, IntegerList *pRight)
 {
 	IntegerList *pStart;
 	IntegerList *pCurrent; 
 	int nCopyInteger;
 
 	// сортировка окончена - выход
 	if (pLeft == pRight) return;
 
 	// установка двух рабочих указателей - Start и Current
 	pStart = pLeft;
 	pCurrent = pStart->pNext;
 
 	// итерация по списку слева направо
 	while (1)
 	{
 		// элемент с максимальным значением помещается в начало списка
 		if (pStart->nInteger < pCurrent->nInteger)
 		{
 			nCopyInteger = pCurrent->nInteger;
 			pCurrent->nInteger = pStart->nInteger;
 			pStart->nInteger = nCopyInteger;
 		}	
 		
 		if (pCurrent == pRight) break;
 		pCurrent = pCurrent->pNext;
 	}
 
 
 
 	// переключение First и Current - максимум попадает в правый конец списка
 	nCopyInteger = pLeft->nInteger;
 	pLeft->nInteger = pCurrent->nInteger;
 	pCurrent->nInteger = nCopyInteger;
 
 
 	// сохранение Current
 	IntegerList *pOldCurrent = pCurrent;
 
 	// рекурсия
 	pCurrent = pCurrent->pPrev;
 	if (pCurrent != NULL)
 	{
 		if ((pLeft->pPrev != pCurrent) && (pCurrent->pNext != pLeft))
 			QuickSortList(pLeft, pCurrent);
 	}
 
 	pCurrent = pOldCurrent;
 	pCurrent = pCurrent->pNext;
 	if (pCurrent != NULL)
 	{
 		if ((pCurrent->pPrev != pRight) && (pRight->pNext != pCurrent))
 			QuickSortList(pCurrent, pRight);
 	}
 }
 
 int main ()
 {
 
 	AddListItem(100);
 	AddListItem(12);
 	AddListItem(56);
 	AddListItem(67);
 
 	PrintList();
 	QuickSortList(g_pFirstItem, g_pLastItem);
 	PrintList();
 	RemoveAllItems();
 	return 0;
 }
 
 

При сортировке слиянием (mergesort) массив разбивается на две части, каждая часть сортируется отдельно, а потом обе части сливаются. Практически это можно объяснить на следующем примере.

  1. колода карт делится на две части, и каждая часть сортируется по отдельности, чтобы наверху оказалась самая маленькая карта;
  2. из двух верхних карт выбирают меньшую и перекладывают ее в результирующую колоду;
  3. процесс повторяется, пока не кончатся карты в обеих половинах;
  4. если в одной половине карты закончатся раньше, тогда все карты, оставшиеся в другой половине, просто перекладываются в результирующую колоду.

Считается, что этот алгоритм был придуман Джоном фон Нейманом в 1945 году. Недостатком сортировки слиянием считается то, что она требует O(n) памяти.


Листинг 5. Реализация сортировки слиянием на языке Си
 
 
 struct node 
 {
  int number;
  struct node *next;
 };
 
 struct node *addnode(int number, struct node *next) 
 {
  struct node *tnode;
  tnode = (struct node*)malloc(sizeof(*tnode));
  if(tnode != NULL) 
  {
   tnode->number = number;
   tnode->next = next;
  }
  return tnode;
 }
 
 int Length(struct node* head) 
 {
   int count = 0;
   struct node* current = head;
   while (current != NULL) 
   {
     count++;
     current = current->next;
   }
   return(count);
 }
 
 void FrontBackSplit(struct node* source, 
                     struct node** frontRef, 
                     struct node** backRef) 
 {
 
   int len = Length(source);
   int i;
   struct node* current = source;
   if (len < 2) 
   {
     *frontRef = source;
     *backRef = NULL;
   }
   else 
   {
     int hopCount = (len-1)/2;
     for (i = 0; i<hopCount; i++) 
     {
       current = current->next;
     }
     // исходный список разбивается на два подсписка
     *frontRef = source;
     *backRef = current->next;
     current->next = NULL;
   }
 }
 
 struct node* SortedMerge(struct node* a, struct node* b) 
 {
   struct node* result = NULL;
   if (a==NULL) return(b);
   else if (b==NULL) return(a);
   if (a->number <= b->number) 
   {
     result = a;
     result->next = SortedMerge(a->next, b);
   }
   else 
   {
     result = b;
     result->next = SortedMerge(a, b->next);
   }
   return(result);
 }
   
 
 void MergeSort(struct node** headRef) 
 {
   struct node* head = *headRef;
   struct node* a;
   struct node* b;
   // вырожденный случай – длина списка равно 0 или 1
   if ((head == NULL) || (head->next == NULL)) 
   {
     return;
   }
   FrontBackSplit(head, &a, &b);
   MergeSort(&a); // рекурсивная сортировка подсписков
   MergeSort(&b);
   *headRef  = SortedMerge(a, b);
 }
 
 

Сравнение различных алгоритмов

После изучения различных алгоритмов сортировки можно выполнить их сравнительное тестирование. В качестве исходной позиции будет использоваться односвязный список длиной в 50000 элементов, при этом ключ в элементе может иметь значение от 0 до 100. Элементы вставляются в произвольном порядке, и исходный список может иметь следующий вид:

0 10 10 2 9 7 2 3 4 5 2 2 10 1 1 .....
 

А после сортировки список должен иметь следующий вид:

0 1 1 2 2 2 2 3 4 5 7 9 10 10 10 .....
 

В ходе теста будут фиксироваться три временных отметки: запуск программы, начало и конец сортировки. Наибольший интерес будет представлять время, непосредственно затраченное на сортировку. В листинге 6 приведен исходный код функции main для оценки производительности пузырьковой сортировки.


Листинг 6. Оценка производительности пузырьковой сортировки на языке Си
 
 
 int main(void) 
 {
   time_t start,time2,end;
   volatile long unsigned t;
   start = time(NULL);
   
  struct lnode *newnode = NULL;
  int i = 0;
  for(i = 0; i < MAX; i++) 
  {
    llist_add(&newnode, (rand() % 100));
  }
  head = newnode;
  printf("до пузырьковой сортировки:\n");
  time2 = time(NULL);
  printf("на подготовку потребовалось %f секунд.\n", difftime(time2, start));
  printf("после пузырьковой сортировки:\n");
 
  llist_bubble_sort();
 
  end = time(NULL);
  printf("на сортировку потребовалось %f секунд.\n", difftime(end, time2));
 
  return 0;
 }
 
 

В листинге 7 приведен исходный код для проверки производительности быстрой сортировки.


Листинг 7. Оценка производительности быстрой сортировки на языке Си
 
 
 int main ()
 {
   time_t start,time2,end;
   volatile long unsigned t;
   start = time(NULL);
 
  for(int i = 0; i < 50000; i++) 
  {
     AddListItem((rand() % 100));
  }
   
  time2 = time(NULL);
  printf("на подготовку потребовалось %f секунд.\n", difftime(time2, start));
   
  QuickSortList(g_pFirstItem, g_pLastItem);
 
  end = time(NULL);
  printf("на сортировку потребовалось %f секунд.\n", difftime(end, time2));
  
  return 0;
 }
 
 

В случае с сортировкой слиянием главная проблема связана с увеличением стека при рекурсии, так как при увеличении длины списка свыше 50000 элементов могут возникнуть ошибки. Функция main для сортировки слиянием показана в листинге 8.


Листинг 8. Оценка производительности сортировки слиянием на языке Си
 
 
 int main(void) 
 {
  time_t start,time2,end;
  volatile long unsigned t;
  start = time(NULL);
   
  struct node *head;
  
  int i;
 
  head = NULL;
 
  for( i = 0; i < 100; i++) 
  {
    head = addnode((rand() % 100), head);
  }
 
  time2 = time(NULL);
  printf("на подготовку потребовалось %f секунд.\n", difftime(time2, start));
  
  MergeSort(&head) ;
 
  end = time(NULL);
  printf("на сортировку потребовалось %f секунд.\n", difftime(end, time2));
  
  return 0;
 }
 
 

Стоит учесть, что этот тест не претендует на звание «абсолютной истины», так как речь идет о конкретной реализации, применяемой на конкретной системе. Наихудший результат, как и ожидалось, показала пузырьковая сортировка, которой на то, чтобы упорядочить связный список из 50000 элементов, потребовалось более 30 секунд. Быстрая сортировка справилась с этой же задачей за 10 секунд. А самой производительной оказалась сортировка слиянием, выполнив задачу еще быстрее, чем быстрая сортировка. Также тест выявил следующие закономерности.

  1. Наибольшее число перестановок требуется пузырьковой сортировке, затем идет быстрая сортировка, и меньше всего перестановок требуется для сортировки слиянием.
  2. При увеличении длины списка отношение числа перестановок в пузырьковой сортировке к числу перестановок в быстрой сортировке растет не в пользу первой, то есть при увеличении размера списка производительность пузырьковой сортировки начинает снижаться.
  3. Сортировка слиянием имеет самые лучшие показатели по числу перестановок. Аналогичное соотношение числа перестановок для быстрой сортировки и сортировки слиянием при увеличении длины списка изменяется в пользу быстрой сортировки: чем больше список, тем меньше это соотношение, хотя и остается больше единицы.

Как было показано в данной статье, при использовании различных алгоритмов для сортировки связных списков можно добиться очень высокой производительности, невзирая на большой размер списка. Однако конечный результат зависит от целого комплекса факторов: эффективного использования памяти, глубины рекурсии, производительности целевой системы и т.д.

Часть 5

Деревья

Начиная с этой статьи мы переходим от связных списков к изучению деревьев. Это не случайно, так оба эти типа структур данных построены на основе рекурсии. Фактически, связные списки являются подвидом деревьев, называемым вырожденным деревом. В данной статье будут рассмотрены общие принципы построения деревьев и различные варианты обхода узлов дерева.

Основные принципы

Первое появление концепции дерева в математике зафиксировано в середине 19-го века, а затем деревья стали использоваться в самых разных областях, например, в теории электрических цепей или химической изометрии. Использование древовидных структур в информационных технологиях началось с приложений для манипулирования алгебраическими формулами в 60-ых годах прошлого века, примерно тогда же появились традиционные алгоритмы для обхода деревьев.

В общем смысле, дерево - это иерархическая структура, хранящая коллекцию объектов. Деревья широко применяются в компьютерных технологиях, и самым близким примером является файловая система, представляющая собой иерархическую структуру из файлов и каталогов. Дерево (англ. tree) — это непустая коллекция вершин и ребер, удовлетворяющих определенным требованиям. Вершина (англ. vertex) — это объект, называемый также узлом (англ. node) по аналогии со списками, который может иметь имя и содержать другую информацию. Ключевое свойство дерева — между любыми двумя узлами существует только один путь, соединяющий их. Если между какой-либо парой узлов существует более одного пути или если между какой-либо парой узлов путь отсутствует, то подобная структура называется графом, а не деревом. Несвязанный набор деревьев называется лесом (англ. forest).

Для определения узлов существуют следующие сложившиеся термины:

  • root - узел, расположенный в корне дерева;
  • siblings - узлы, имеющие одного и того же родителя;
  • ancestor или parent – родительский узел;
  • descendant – дочерний узел;
  • size – размер узла, равный количеству дочерних узлов плюс один.

В рамках данной статьи будут обсуждаться деревья с произвольным количеством дочерних узлов. Упорядоченное (англ. ordered) дерево — это дерево с определенным корневым узлом, в котором также определен порядок следования дочерних узлов для каждого узла.

Деревья можно разделить на следующие категории:

  1. деревья без корня;
  2. деревья с корнем;
  3. упорядоченные деревья;
  4. м-арные и бинарные деревья.

На рисунке 1 показано, как оглавление книги можно представить в виде дерева. В показанном примере корневой узел имеет три поддерева – три главы, каждая из которых в свою очередь имеет свои подразделы.


Рисунок 1. Пример древовидной структуры
Рисунок 1. Пример древовидной структуры

Путь (англ. path) - это последовательность узлов, которые нужно пройти, чтобы из корневого узла попасть в какой-либо дочерний узел. Длина пути равна числу узлов минус один. Высота (англ. height) - это путь от корня до наиболее удаленного узла. Например, на рисунке 1 высота поддерева часть № 1 равна единице, часть № 2 - двум, а высота поддерева часть № 3 равна нулю, так как оно не имеет дочерних узлов. Дочерние узлы обычно принять считать слева направо, но это можно делать в различном порядке. На рисунке 2 приведен пример дерева и результат использования трех различных подходов для обхода узлов.


Рисунок 2. Пример древовидной структуры
Рисунок 2. Пример древовидной структуры
  1. preorder – сверху-вниз-слева-направо: F, B, A, D, C, E, G, I, H;
  2. inorder – слева-вверх-вниз-вправо: A, B, C, D, E, F, G, H, I;
  3. postorder – обратное движение от детей к родителям: A, C, E, D, B, H, I, G, F.

Если сравнить древовидные структуры со связными списками, то станет понятно, что наибольшую сложность при работе с деревьями представляют динамические операции, такие как вставка и удаление узлов. Например, при удалении узла из бинарного дерева необходимо решить проблему наличия двух дочерних и одного родительского узла.

Рекурсивная реализация алгоритмов для обхода дерева

В листинге 1 приведен псевдокод для трех описанных ранее алгоритмов обхода дерева, основанный на использовании рекурсии. В рамках рассматриваемой реализации было внесено ограничение, что у любого узла не может быть более трех дочерних узлов.


Листинг 1. Псевдокод алгоритмов для обхода дерева
 preorder(node)
   print node.value
   if node.left ≠ null then preorder(node.left) 
   if node.middle ≠ null then preorder(node.middle) 
   if node.right ≠ null then preorder(node.right)
 
 inorder(node)
   if node.left  ≠ null then inorder(node.left)
   print node.value
   if node.middle ≠ null then inorder(node.middle)
   if node.right ≠ null then inorder(node.right)
 
 postorder(node)
   if node.left  ≠ null then postorder(node.left)
   if node.middle ≠ null then postorder(node.middle)
   if node.right ≠ null then postorder(node.right)
   print node.value
 

В листинге 2 приведен пример обхода 3-нарного дерева (где каждый узел может иметь не более трех дочерних элементов) с помощью различных алгоритмов, реализованных на языке Си. Дерево из 10 узлов будет сформировано в методе main, а затем к нему будут применены три варианта обхода, которые будут приведены в отдельном листинге.


Листинг 2. Реализация дерева на языке Си
 
 
 #include <stdio.h>                           
 #include<stdlib.h>
 
 //структура для описания узла дерева
 struct tree                                  
 { 
     int data;                                
     struct tree *lchild, *mchild, *rchild;   
 };
 
 struct tree *my_insert(struct tree *p,int n, int dir);
 void inorder(struct tree *p);                
 void preorder(struct tree *p);               
 void postorder(struct tree *p);              
 
 int main()                                  
 { 
 	int x,y,i;                                    
 	struct tree *root;
 	struct tree *node_2, *node_3, *node_5;
 	struct tree *node_8, *node_9, *node_6,*node_10,*node_4, *node_7   ;
 	
 	//создание дерева
 	root = NULL;
 	root = my_insert(root,1,0);		
 	node_2 = my_insert(root,2,0);		
 	node_3 = my_insert(root,3,1);		
 	node_4 = my_insert(root,4,2);		
 	node_5 = my_insert(node_3,5,0);		
 	node_8 = my_insert(node_5,8,0);		
 	node_9 = my_insert(node_5,9,2);		
 	node_6 = my_insert(node_3,6,2);		
 	node_10 = my_insert(node_6,10,1);		
 	node_7 = my_insert(node_4,7,1);		
 
 	//выполнение обхода дерева различными способами
 	preorder(root);
 	printf("\n");
 	inorder(root);
 	printf("\n");
 	postorder(root);
 
 		return 0;
 }
 
 

В листинге 3 приведен исходный код функции для вставки узлов в дерево. Данная функция принимает на вход три параметра: указатель на вставляемый узел, значение вставляемого узла и направление вставки — влево, в середину или вправо.


Листинг 3. Функция для вставки узлов в дерево
 
 
 struct tree * my_insert(struct tree *p,int n, int dir)               
 {
 	struct tree *temp;
 
 	temp = (struct tree *)malloc(sizeof(struct tree));
 	temp->data = n;
 	temp->lchild = temp->rchild=NULL;
 
 	if(p==NULL)
 	{
 		return temp;
 	}
 	else
 	{
 		if(dir ==0) // влево
 		{
 			p->lchild = temp;
 			return temp;
 		}
 		else if(dir ==1) // посередине
 		{
 			p->mchild = temp;
 			return temp;
 		}
 		else // вправо
 		{
 			p->rchild = temp;
 			return temp;
 		}
 	}	
 }
 
 

В листинге 4 приведен исходный код функций, реализующих различные варианты обхода дерева.


Листинг 4. Функции для обхода узлов дерева
 
 
 void inorder(struct tree *p)
 {
     if(p!=NULL)
     {
         inorder(p->lchild);
         printf("%d ",p->data);
         inorder(p->mchild);
         inorder(p->rchild);
     }
 }
 
 void preorder(struct tree *p)
 {
     if(p!=NULL)
     {
         printf("%d ",p->data);
         preorder(p->lchild);
         preorder(p->mchild);
         preorder(p->rchild);
     }
 }
 
 void postorder(struct tree *p)
 {
     if(p!=NULL)
     {
         postorder(p->lchild);
         postorder(p->mchild);
         postorder(p->rchild);
         printf("%d ",p->data);
     }
 }
 

В листинге 5 приведена реализация алгоритмов обхода дерева на языке Python. В нем объявляются два класса — один для узлов и другой для самого дерева. В конструкторе класса Tree для наглядности объявляются ссылки на узлы.


Листинг 5. Реализация обхода дерева на языке Python
 
 
 //класс, представляющий узел
 class node:
     def __init__(self, data = None, lchild = None, mchild = None, rchild = None):
         self.data = data
         self.lchild  = lchild
         self.mchild  = mchild
         self.rchild  = rchild
 
     def __str__(self):
         return 'Node ['+str(self.value)+']'
 
 //класс, представляющий дерево
 class Tree:
     def __init__(self):
         self.root = None
         self.node_2  = None
         self.node_3  = None
         self.node_4  = None
         self.node_5  = None
         self.node_6  = None
         self.node_7  = None
         self.node_8  = None
         self.node_9  = None
         self.node_10  = None
 
 //функция для добавления элементов в дерево
     def my_insert(self, root_node, data, dir):
         temp = node(0,None,None,None)
         temp.data = data
         if root_node == None:
           return temp
         else:
           if dir == 0:
             root_node.lchild = temp
             return temp
           elif dir == 1:
             root_node.mchild = temp
             return temp
           else:
             root_node.rchild = temp
             return temp
             
 
 //рекурсивные функции для обхода дерева
     def inorder(self,noda):
         if noda!=None:
           self.inorder(noda.lchild);
           print("%d " % noda.data)
           self.inorder(noda.mchild)
           self.inorder(noda.rchild)
 
     def preorder(self,noda):
         if noda!=None:
           print (" %d  " % noda.data)
           self.preorder(noda.lchild);
           self.preorder(noda.mchild)
           self.preorder(noda.rchild)
 
     def postorder(self,noda):
         if noda!=None:
           self.postorder(noda.lchild);
           self.postorder(noda.mchild)
           self.postorder(noda.rchild)
           print (" %d  " % noda.data)
 
 //создание дерева
 t  = Tree()
 t.root   = t.my_insert(t.root,1,0)
 t.node_2 = t.my_insert(t.root,2,0);   
 t.node_3 = t.my_insert(t.root,3,1);   
 t.node_4 = t.my_insert(t.root,4,2);   
 t.node_5 = t.my_insert(t.node_3,5,0);   
 t.node_8 = t.my_insert(t.node_5,8,0);   
 t.node_9 = t.my_insert(t.node_5,9,2);   
 t.node_6 = t.my_insert(t.node_3,6,2);   
 t.node_10 = t.my_insert(t.node_6,10,1);   
 t.node_7  = t.my_insert(t.node_4,7,1);   
 
 //обход дерева
 t.preorder(t.root);
 t.inorder(t.root);
 t.postorder(t.root);
 
 

Нерекурсивная реализация обхода дерева

Дерево можно обойти, и не используя рекурсию, причем это можно сделать любым из трех способов: inorder, preorder и postorder. Для этого можно использовать стандартный стек, работающий по принципу LIFO (последним пришел, первым ушел), в который будут записываться узлы по мере их прохождения. В качестве примера также будет использоваться три-нарное дерево.


Листинг 6. Нерекурсивный обзор дерева на языке Си
 
 
 #include <stdio.h>                           
 #include<stdlib.h>
 #include <iostream>
 #include <stack>
 
 using namespace std;
 
 struct tree                                  
 { 
     int data;                                
     struct tree *lchild, *mchild, *rchild;   
 };
 
 /*
  * функции для итеративного обхода дерева
  */
 void iterativeInorder(tree* root) 
 {
 	stack<tree*> nodeStack;
 	tree *_root, *curr = root;
 	_root = root;
 	for (;;) 
 	{
 		if (curr != NULL) 
 		{
 			nodeStack.push(curr);
 			curr = curr->lchild;
 			continue;
 		}
 		if (nodeStack.size() == 0) 
 		{
 			if(_root != NULL)
 			{
 				curr = _root->rchild;
 				_root = NULL;
 				continue;
 			}
 			else return;
 		}   
 		curr = nodeStack.top();
 		nodeStack.pop();
 		cout <<  curr->data << " ";
 		if(curr->mchild != NULL)
 			curr = curr->mchild;
 		else 
 			curr = curr->rchild;
 	}
 }
 
 void iterativePreorder(tree* root) 
 {
 	stack<tree*> nodeStack;
 	tree *_root, *curr = root;
 	_root = root;
 	for (;;) 
 	{
 		while (curr != NULL) 
 		{
 			cout << curr->data << " ";
 			nodeStack.push(curr);
 			curr = curr->lchild;
 		}	
 		if (nodeStack.size() > 0) 
 		{
 			curr = nodeStack.top();
 			nodeStack.pop();
 			if(curr->mchild != NULL)
 				curr = curr->mchild;
 			else 
 				curr = curr->rchild;
 		}
 		else
 		{
 			if(_root != NULL)
 			{
 				curr = _root->rchild;
 				_root = NULL;
 				continue;
 			}
 			else return;
 		}
 	}
 }
 
 void iterativePostorder(tree* root) 
 {
 	tree *curr = root;
 	stack<tree*> s1,s2;
 	s1.push(curr);
 	tree *tmp=NULL;
 	while (s1.size() > 0)
 	{
 		tmp = s1.top();
 		s1.pop();
 		s2.push(tmp);
 		if (tmp->lchild)
 			s1.push(tmp->lchild);
 		if (tmp->mchild)
 			s1.push(tmp->mchild);
 		if (tmp->rchild)
 			s1.push(tmp->rchild);
 	}
 	
 	while(s2.size() > 0)
 	{
 		tmp = s2.top();
 		s2.pop();
 		cout << tmp->data << " ";
 	}
 }
 
 /*
  * функция для добавления узлов в дерево
  */
 struct tree * my_insert(struct tree *p,int n, int dir)               
 {
 	struct tree *temp;
 	temp = (struct tree *)malloc(sizeof(struct tree));
 	temp->data = n;
 	temp->lchild = temp->rchild=NULL;
 	if(p==NULL)
 	{
 		return temp;
 	}
 	else
 	{
 		if(dir ==0) // влево
 		{
 			p->lchild = temp;
 			return temp;
 		}
 		else if(dir ==1) // посередине
 		{
 			p->mchild = temp;
 			return temp;
 		}
 		else // вправо
 		{
 			p->rchild = temp;
 			return temp;
 		}
 	}
 }
 
 int main()                                  
 { 
 	int x,y,i;                                    
 	struct tree *root;
 	struct tree *node_2, *node_3, *node_5, *node_8;
 	struct tree *node_9, *node_6,*node_10,*node_4, *node_7   ;
 		
 	root = NULL;
 	root = my_insert(root,1,0);		
 	node_2 = my_insert(root,2,0);		
 	node_3 = my_insert(root,3,1);		
 	node_4 = my_insert(root,4,2);		
 	node_5 = my_insert(node_3,5,0);		
 	node_8 = my_insert(node_5,8,0);		
 	node_9 = my_insert(node_5,9,2);		
 	node_6 = my_insert(node_3,6,2);		
 	node_10 = my_insert(node_6,10,1);		
 	node_7 = my_insert(node_4,7,1);		
 
 	iterativeInorder(root);
 	printf("\n");
 	iterativePreorder(root);
 	printf("\n");
 	iterativePostorder(root);
 	
 	return 0;
 }
 
 

Формы представления дерева

Одной из форм представления дерева является обычный массив. Пусть T - дерево, узлы в котором пронумерованы от 1 до n. Простейшей формой представления дерева T может быть линейный массив A, в котором каждый элемент массива A[i] представляет собой указатель на узел или его родителя.

Если i и j - два узла, и узел j является родителем для узла i, то

A[i] = j
 

Для идентификации корневого узла, указатель на его родителя можно сделать нулевым, как показано ниже:

A[i] = 0
 

Каждый узел может иметь только одного родителя. Одновременно с массивом A можно завести массив L, в котором будут храниться метки для узлов. На рисунке 3 дерево представлено в виде массива родителей для каждого узла. Однако при использовании такого представления остается неясным, в каком порядке идут дочерние узлы.


Рисунок 3. Представление дерева в виде массива
Рисунок 3. Представление дерева в виде массива

Еще один возможный вариант представления деревьев – это использование связного списка, содержащего все узлы дерева, при этом дочерние узлы хранятся вместе с родительским, как показано на рисунке 4.


Рисунок 4. Представление дерева в виде списка
Рисунок 4. Представление дерева в виде списка

На этом рисунке показан общий массив узлов, пронумерованный от 1 до 10. У отдельных узлов из этого списка есть дочерние узлы, которые в общем списке помечены точками. Но так как массив имеет фиксированный размер, то в такое дерево нельзя вставить новый узел.

Виды деревьев

А: Expression tree - это разновидность бинарных деревьев, полученные в результате арифметических или логических выражений, при этом операнды размещаются в листьях. Примеры представлены на следующем рисунке:

С помощью бинарных деревьев могут быть представлены достаточно сложные формулы - как например для квадратичной формулы :

A triply linked tree: оно отличается от обычных деревьев тем, что кроме ссылок на левое и правое под-дерево, оно имеет ссылку на родителя:

 
   
 struct node
 { 
     int data;                                
     struct node *left;
     struct node *right;
     struct node *parent;
 };
 
 

Кольцевая структура представлена на следующем рисунке.

Граф:

Free tree - дерево, не имеющее корня:

Теория деревьев является одной из самых востребованных и популярных научных дисциплин в области информационных технологий. Древовидные структуры подходят для решения большого круга задач в самых различных отраслях знания. В компьютерных технологиях деревья являются ключевым компонентом для создания алгоритмов хранения, поиска и обработки информации. Любой программист должен уметь работать с подобными структурами данных, тем более, что как было показано в этой статье, для этого используются стандартные и хорошо зарекомендовавшие себя алгоритмы.

Часть 6

Двоичные деревья

Бинарные (двоичные) деревья являются одним из самых востребованных вариантов данной структуры данных, так как широко используются в поисковых алгоритмах и для решения других вычислительных задач. В данной статье будут рассмотрены основные характеристики бинарных деревьев и различные операции, выполняющиеся над ними.

Как обычно, кроме теоретических аспектов: классификации бинарных деревьев и стандартных приемов для манипулирования ими, в статье будут примеры практической реализации алгоритмов для работы с бинарными деревьями на языках Си и Python.

Классификация бинарных деревьев

Перед тем, как перейти к обсуждению различных типов бинарных деревьев, стоит остановиться на общей классификации поисковых алгоритмов.

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

Для отсортированного списка существует и более эффективный алгоритм. В начале поиска необходимо сравнить искомое число с элементом, который находится ПОСЕРЕДИНЕ уже отсортированного списка. Если серединный элемент оказывается больше искомого числа, значит искомый элемент находится в левой половине. В противном случае - справа. Затем выполняется сравнение с числом, которое находится посередине нужной половины. И так далее до тех пор, пока не будет найдено искомое число. Данный тип поиска называется двоичным, и он, очевидно, быстрее линейного. Необходимое количество делений списка, состоящего из n элементов пополам, называется логарифмом от n по основанию 2. Двоичный поиск является алгоритмом порядка O(log) по основанию 2.

Однако традиционные связные списки не очень подходят для двоичного поиска, и здесь на помощь приходит двоичное дерево, пример которого изображен на рисунке 1.


Рисунок 1. Пример двоичного дерева
Рисунок 1. Пример двоичного дерева

В общем случае каждый узел в дереве может иметь неограниченное количество дочерних узлов. Отличие бинарного дерева от остальных типов деревьев в том, что каждый узел в нем может иметь не более двух дочерних узлов. Обычное двоичное дерево — это структура, состоящая из узлов, каждый из которых содержит некоторое значение, а также указатели на левое и правое поддеревья. Один или оба указателя на эти поддеревья могут иметь значение NULL. Двоичные деревья, как и связные списки, являются рекурсивными структурами.

На рисунке 2 показаны бинарные деревья, которые имеют одинаковый набор узлов, но различный порядок их следования. В последнем случае дерево вырождается в связный список.


Рисунок 2. Различные реализации одного и того же бинарного дерева
Рисунок 2. Различные реализации одного и того же бинарного дерева

Существуют следующие разновидности бинарных деревьев:

  • полное бинарное дерево - каждый узел, за исключением листьев, имеет по 2 дочерних узла;
  • идеальное бинарное дерево - это полное бинарное дерево, в котором все листья находятся на одной высоте;
  • сбалансированное бинарное дерево - это бинарное дерево, в котором высота 2-х поддеревьев для каждого узла отличается не более чем на 1. Глубина такого дерева вычисляется как двоичный логарифм log(n), где n - общее число узлов;
  • вырожденное дерево - дерево, в котором каждый узел имеет всего один дочерний узел, фактически это связный список;
  • бинарное поисковое дерево (BST) - бинарное дерево, в котором для каждого узла выполняется условие: все узлы в левом поддереве меньше, и все узлы в правом поддереве больше данного узла.
Вычисление путей

Путь (англ. path) - это расстояние от корня дерева до какого либо узла. В расширенном бинарном дереве каждый путь оканчивается листом. Если число листьев обозначить как S, а число остальных узлов обозначить как N, то справедлива формула:

S = N +1
 

т.е. для расширенного дерева число листьев на единицу больше числа НЕлистьев (узлов, имеющих дочерние узлы).

Если путь от корневого узла до листа обозначить как внешний путь, а путь от корневого узла до НЕлиста обозначить как внутренний путь, тогда сумма всех внешних путей для дерева, изображенного на рисунке 3 равна:

E=3+3+2+3+4+4+3+3=25,
 

а сумма внутренних путей будет равна:

I=2+1+0+2+3+1+2=11.
 

и тогда будет справедлива формула:

E=I+2n
 

где n - число внутренних узлов (НЕлистьев).


Рисунок 3. Пример расширенного дерева
Рисунок 3. Пример расширенного дерева

Предположим, имеется следующий набор листьев:

2,3,5,7,11,13,17,19,23,29,31,37,41
 

Тогда можно сформулировать следующие задачи:

  1. сконструировать бинарное дерево таким образом, чтобы сумма путей была минимальной, так как это сокращает время вычислений для различных алгоритмов.
  2. сконструировать полное расширенное бинарное дерево таким образом, чтобы сумма произведений путей от корневого узла до листьев на значение листового узла была минимальной.

Давид Хаффман (David Huffman) предложил алгоритм для решения этой проблемы, в котором на каждом шаге выбираются и складываются два наименьших листа, как показано в листинге 1, что приводит к дереву, изображенному на рисунке 4.


Листинг 1. Пример алгоритма Хаффмана
   2 3 5 7 11 13 17 19 23 29 31 37 41
     5 5 7 11 13 17 19 23 29 31 37 41
      10 7 11 13 17 19 23 29 31 37 41
        17    24 17 19 23 29 31 37 41
              24 34 19 23 29 31 37 41
              24 34    42 29 31 37 41
                       42 53 65 37 41
                       42 53 65    78
                          95 65    78
                          95      143
                                  238
 


Рисунок 4. Бинарное дерево, построенное по алгоритму Хаффмана
Рисунок 4. Бинарное дерево, построенное по алгоритму Хаффмана
Коды Хаффмана

Коды Хаффмана - это алгоритм, используемый для сжатия данных. Пусть имеется некое исходное текстовое сообщение, состоящее из 5 символов: a, b, c, d, e, и каждый символ имеет свою собственную частоту:

  • a встречается 12 раз;
  • b - 4 раза;
  • c - 15 раз;
  • d - 8 раз;
  • e - 25 раз.

Нужно закодировать это сообщение с помощью 0 и 1 таким образом, чтобы размер результирующей строки оказался минимальным. В таблице приведен пример кодирования символов для данного сообщения:

Если зашифровать сообщение bcd с помощью кода №1, то получится - 001010011. С помощью кода №2 можно делать то же самое, но получившая строка будет короче - 1101001.

Теперь можно сформулировать саму проблему: необходимо подобрать такой алгоритм шифрования, при котором длина зашифрованной строки будет минимальной.

В первом варианте на каждый символ отводилось по 3 символа, а во втором варианте - уже 2.2, но можно сделать еще короче и получить коэффициент, равный 2.15. Это делается с помощью алгоритма Хаффмана, в котором берутся 2 символа, имеющие наименьшую частоту, и объединяются, как два дочерних узла.

Алгоритм для строки, состоящей из 5 символов, реализуется следующим образом. На первом шаге объединяются два символа - a и d, как имеющие наименьшую частоту. На втором в качестве родителя добавляется символ c. На третьем шаге добавляется символ e, и в конце - символ b. В результате получается следующий код:

  • b – 0;
  • e – 10;
  • c – 110;
  • a – 1111;
  • d – 1110.

Следующий код реализует поиск минимальных кодов для строки, показанной на рисунке:

 
 
 #include < stdio.h>
 #include < stdlib.h>
 #include < string.h>
  
 #define BYTES 256
  
 struct huffcode 
 {
   int nbits;
   int code;
 };
 typedef struct huffcode huffcode_t;
  
 struct huffheap {
   int *h;
   int n, s, cs;
   long *f;
 };
 typedef struct huffheap heap_t;
  
 /* heap handling funcs */
 static heap_t *_heap_create(int s, long *f)
 {
   heap_t *h;
   h = malloc(sizeof(heap_t));
   h->h = malloc(sizeof(int)*s);
   h->s = h->cs = s;
   h->n = 0;
   h->f = f;
   return h;
 }
  
 static void _heap_destroy(heap_t *heap)
 {
   free(heap->h);
   free(heap);
 }
  
 #define swap_(I,J) do { int t_; t_ = a[(I)];  \
       a[(I)] = a[(J)]; a[(J)] = t_; } while(0)
 
 static void _heap_sort(heap_t *heap)
 {
   int i=1, j=2; /* gnome sort */
   int *a = heap->h;
  
   while(i < heap->n) { /* smaller values are kept at the end */
     if ( heap->f[a[i-1]] >= heap->f[a[i]] ) {
       i = j; j++;
     } else {
       swap_(i-1, i);
       i--;
       i = (i==0) ? j++ : i;
     }
   }
 }
 #undef swap_
  
 static void _heap_add(heap_t *heap, int c)
 {
   if ( (heap->n + 1) > heap->s ) {
     heap->h = realloc(heap->h, heap->s + heap->cs);
     heap->s += heap->cs;
   }
   heap->h[heap->n] = c;
   heap->n++;
   _heap_sort(heap);
 }
  
 static int _heap_remove(heap_t *heap)
 {
   if ( heap->n > 0 ) {
     heap->n--;
     return heap->h[heap->n];
   }
   return -1;
 }
  
 /* huffmann code generator */
 huffcode_t **create_huffman_codes(long *freqs)
 {
   huffcode_t **codes;
   heap_t *heap;
   long efreqs[BYTES*2];
   int preds[BYTES*2];
   int i, extf=BYTES;
   int r1, r2;
  
   memcpy(efreqs, freqs, sizeof(long)*BYTES);
   memset(&efreqs[BYTES], 0, sizeof(long)*BYTES);
  
   heap = _heap_create(BYTES*2, efreqs);
   if ( heap == NULL ) return NULL;
  
   for(i=0; i < BYTES; i++) if ( efreqs[i] > 0 ) _heap_add(heap, i);
  
   while( heap->n > 1 )
   {
     r1 = _heap_remove(heap);
     r2 = _heap_remove(heap);
     efreqs[extf] = efreqs[r1] + efreqs[r2];
     _heap_add(heap, extf);
     preds[r1] = extf;
     preds[r2] = -extf;
     extf++;
   }
   r1 = _heap_remove(heap);
   preds[r1] = r1;
   _heap_destroy(heap);
  
   codes = malloc(sizeof(huffcode_t *)*BYTES);
  
   int bc, bn, ix;
   for(i=0; i < BYTES; i++) {
     bc=0; bn=0;
     if ( efreqs[i] == 0 ) { codes[i] = NULL; continue; }
     ix = i;
     while( abs(preds[ix]) != ix ) {
       bc |= ((preds[ix] >= 0) ? 1 : 0 ) << bn;
       ix = abs(preds[ix]);
       bn++;
     }
     codes[i] = malloc(sizeof(huffcode_t));
     codes[i]->nbits = bn;
     codes[i]->code = bc;
   }
   return codes;
 }
  
 void free_huffman_codes(huffcode_t **c)
 {
   int i;
  
   for(i=0; i < BYTES; i++) if (c[i] != NULL) free(c[i]);
   free(c);
 }
  
 #define MAXBITSPERCODE 100
  
 void inttobits(int c, int n, char *s)
 {
   s[n] = 0;
   while(n > 0) {
     s[n-1] = (c%2) + '0';
     c >>= 1; n--;
   }
 }
  
 const char *test = "abcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeaaaaccccccceeeeeeeeeeeeeeeeebbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb";
  
 int main()
 {
   huffcode_t **r;
   int i;
   char strbit[MAXBITSPERCODE];
   const char *p;
   long freqs[BYTES];
  
   memset(freqs, 0, sizeof freqs);
  
   p = test;
   while(*p != '\0') freqs[*p++]++;
  
   r = create_huffman_codes(freqs);
  
   for(i=0; i < BYTES; i++) {
     if ( r[i] != NULL ) {
       inttobits(r[i]->code, r[i]->nbits, strbit);
       printf("%c (%d) %s\n", i, r[i]->code, strbit);
     }
   }
  
   free_huffman_codes(r);
  
   return 0;
 }
 
 
 
Высота бинарного дерева

Для определения высоты дерева потребуется пройти от корня сначала по левому поддереву, потом по правому, сравнить две этих высоты и выбрать максимальное значение. И не забыть к получившемуся значению прибавить единицу (корневой элемент). В листинге 2 приведена рекурсивная функция для выполнения этой задачи.


Листинг 2. Определение высоты дерева – рекурсивная реализация на языке Си
 
 
 int height(struct node *p)
 {
         struct node *temp=p;
         int h1=0,h2=0;
         if(p==NULL)return(0);
         if(p->left){h1=height(p->left);}
         if(p->right){h2=height(p->right);}
         return(max(h1,h2)+1);
 }
 
 

«Зеркальное» отражение бинарного дерева

Когда два дерева являются зеркальным отражением друг друга, то говорится, что они симметричны. Для получения «зеркальной» копии дерева используется алгоритм, приведенный в листинге 3. Сначала выполняется проверка на наличие у корня дерева дочерних узлов, и если эти узлы есть, то они меняются местами. Потом эти же действия рекурсивно повторяются для левого и правого дочерних узлов. Если существует только один дочерний узел, тогда можно переходить на один уровень ниже по дереву и продолжать.


Листинг 3. Реверс дерева – рекурсивная реализация на языке Си
 
 
 void reverse(struct tree *p)
 {
 	struct tree * temp;
 	
 	if(p)
 	{
 		if(p->left  &&  p->right) 
 		{
 			temp = p->left;
 			p->left = p->right;
 			p->right = temp;
 			reverse(p->left);
 			reverse(p->right);
 		}	
 		else if (p->left && !p->right) reverse(p->left);
 		else if (!p->left &&  p->right) reverse(p->right);
 	}
 }
 
 

Поиск узла в бинарном дереве

Для поиска узла в бинарном дереве по содержащимся в нем значениям можно использовать функцию lookup, приведенную в листинге 4:


Листинг 4. Поиск узла в дереве – рекурсивная реализация на языке Си
 
 
 int lookup(struct node* node, int target) 
 {
 	if (node == NULL) 
 {
 	return(0);
 }
 else 
 {
 		if (target == node->data) return(1);
 		else 
 		{
 			if (target < node->data) return(lookup(node->left, target));
 			else return(lookup(node->right, target));
 		}
 	}
 } 
 
 

Ширина бинарного дерева

Под шириной дерева понимается максимальное количество узлов, которые расположены на одной высоте. Чтобы определить ширину дерева, достаточно просто добавить счетчик в уже рассмотренный алгоритм для определения высоты дерева.


Листинг 5. Определение ширины дерева – рекурсивная реализация на языке Си
 
 
 int getMaxWidth(struct node* root)
 {
 	int maxWdth = 0;
 	int i;
 	int width = 0 ;
 	int h = height(root);
 	for( i = 1; i< h; i++)
 	{
 		width =   getWidth(root, i);
 		if(width > maxWdth)
 			maxWdth  = width;
 	}
 	return maxWdth;
 }
 
 int getWidth(struct node* root,int level)
 {
 	if (!root) return 0;
 	if (level == 1) return 1;
 	else if (level > 1)
 	return getWidth(root->left, level-1) +  getWidth(root->right, level-1);
 	getWidth(root->right, level-1);
 }
 
 

Количество узлов в бинарном дереве

Вычислить количество узлов в бинарном дереве также можно с помощью рекурсии.


Листинг 6. Вычисление количества узлов в дереве – рекурсивная реализация на языке Си
 
 
 int size(struct node* node) 
 {
 	if (node==NULL) 
 	{
 		return(0);
 	} 
 	else 
 	{
 		return(size(node->left) + 1 + size(node->right));
 	}
 }
 
 

Сравнение бинарных деревьев

Чтобы определить, совпадают ли два разных дерева, можно использовать алгоритм из листинга 7.


Листинг 7. Сравнение бинарных деревьев – рекурсивная реализация на языке Си
 
 
 int sameTree(struct node* a, struct node* b) 
 {
 	if (a==NULL && b==NULL) return(true);
 	else if (a!=NULL && b!=NULL) 
 	{
 		return(
 			a->data == b->data &&
 			sameTree(a->left, b->left) &&
 
 			sameTree(a->right, b->right)
 			);
 	}
 	else return(false);
 } 
 
 

Реализация на си
 
 
 #include < stdio.h>
 #include < stdlib.h>
 
 #define bool int
  
 /* стандартная нода для бинарного дерева */
 struct node
 {
   int data;
   struct node* left;
   struct node* right;
 };
  
 
 /* вывод на экран*/
 void printLevelOrder(struct node* root)
 {
   int h = height(root);
   int i;
  
   /*ltr -> задаем направление печати - слева-направо или наоборот
     если.ltr=1, то слева-направо */
   bool ltr = 1;
   for(i=1; i<=h; i++)
   {
     printGivenLevel(root, i, ltr);
   }
 }   
  
 void printGivenLevel(struct node* root, int level, int ltr)
 {
   if(root == NULL)
     return;
   if(level == 1)
     printf("%d ", root->data);
   else if (level > 1)
   {
     if(ltr)
     {
       printGivenLevel(root->left, level-1, ltr);
       printGivenLevel(root->right, level-1, ltr);
     }
     else
     {
       printGivenLevel(root->right, level-1, ltr);
       printGivenLevel(root->left, level-1, ltr);
     }
   }
 }
  
 /* вычисляем высоту дерева.*/
 int height(struct node* node)
 {
    if (node==NULL)
        return 0;
    else
    {
      int lheight = height(node->left);
      int rheight = height(node->right);
  
      if (lheight > rheight)
          return(lheight+1);
      else return(rheight+1);
    }
 }
  
 /* добавление ноды */
 struct node* newNode(int data)
 {
   struct node* _node = (struct node*) malloc(sizeof(struct node));
   _node->data = data;
   _node->left = NULL;
   _node->right = NULL;
  
   return(_node);
 }
 
 int getMaxWidth(struct node* root)
 {
   int maxWdth = 0;
   int i;
   int width = 0 ;
   int h = height(root);
   for( i = 1; i< h; i++)
   {
     width =   getWidth(root, i);
     if(width > maxWdth)
         maxWdth  = width;
   }
   return maxWdth;
 }
 
 int getWidth(struct node* root,int level)
 {
   if (!root) return 0;
   if (level == 1) return 1;
   else if (level > 1)
       return getWidth(root->left, level-1) +  getWidth(root->right, level-1);
   getWidth(root->right, level-1);
 }
 
 
 int lookup(struct node* node, int target) 
 {
   if (node == NULL) 
   {
     return(0);
   }
   else 
   {
     if (target == node->data) return(1);
     else 
     {
       // рекурсия
       if (target < node->data) return(lookup(node->left, target));
       else return(lookup(node->right, target));
     }
   }
 } 
 
 
 int main()
 {
   struct node *root  = newNode(8);
   root->left         = newNode(4);
   root->right        = newNode(12);
   root->left->left   = newNode(2);
   root->left->right  = newNode(6);
   root->right->left  = newNode(10);
   root->right->right = newNode(14);
   root->left->left->left  = newNode(1);
   root->right->right->right = newNode(25);
   root->left->left->left->left     = newNode(0);
   root->left->left->right    = newNode(3);
   root->right->right->right->right = newNode(100);
   root->right->right->right->left  = newNode(20);
 
   printLevelOrder(root);
 
   printf("\nВысота: %d\n", height(root));
   
   printf("\nШирина %d\n", getMaxWidth(root));
 
   printf("\n%d\n",lookup(root,100));
   printf("\n%d\n",lookup(root,33));
 
   return 0;
 }
  
 
$11 Реализация на питоне
  
 
 class node:
     def __init__(self, data = None, left = None, right = None):
         self.data   = data
         self.left   = left
         self.right  = right
 
     def __str__(self):
         return 'Node ['+str(self.value)+']'
 
 class Tree:
     def __init__(self):
         self.root = None
 
     def newNode(self, data):
         temp = node(0,None,None)
         temp.data = data
         return temp
 
     def height(self,node):
       if node==None:
           return 0
       else:
         lheight = self.height(node.left)
         rheight = self.height(node.right)
     
         if lheight > rheight:
             return(lheight+1)
         else:
           return(rheight+1)
 
 
     def printGivenLevel(self, root, level, ltr):
       if root == None:
         return
       if level == 1:
         print ("%d " % root.data)
       elif level > 1:
         if ltr:
           self.printGivenLevel(root.left, level-1, ltr);
           self.printGivenLevel(root.right, level-1, ltr);
         else:
           self.printGivenLevel(root.right, level-1, ltr);
           self.printGivenLevel(root.left, level-1, ltr);
 
     def printLevelOrder(self, root):
       h = self.height(self.root)
       i=1
       ltr = 1
       while(i<=h):
         self.printGivenLevel(self.root, i, ltr)
         i +=1
     
     
     def getMaxWidth(self,root):
       maxWdth = 0
       i = 1
       width = 0 ;
       h = self.height(root)
       while( i< h):
         width =   self.getWidth(root, i)
         if(width > maxWdth):
             maxWdth  = width;
         i +=1    
 
       return maxWdth;
 
     
     def getWidth(self, root, level):
       if root == None:
         return 0
       if level == 1: 
         return 1
       elif level > 1:
           return self.getWidth(root.left, level-1) +  self.getWidth(root.right, level-1)
       self.getWidth(root.right, level-1)
 
 
 
 
 t  = Tree()
 t.root        = t.newNode(8)
 t.root.left   = t.newNode(4)
 t.root.right  = t.newNode(12)
 t.root.left.left   = t.newNode(2)
 t.root.left.right  = t.newNode(6)
 t.root.right.left  = t.newNode(10)
 t.root.right.right = t.newNode(14)
 t.root.left.left.left  = t.newNode(1)
 t.root.right.right.right = t.newNode(25)
 t.root.left.left.left.left  = t.newNode(0)
 t.root.left.left.right      = t.newNode(3)
 t.root.right.right.right.right = t.newNode(100)
 t.root.right.right.right.left  = t.newNode(20)
 
 t.printLevelOrder(t.root)
 
 print ("\nВысота: %d\n" % t.height(t.root))
 
 print ("\nШирина %d\n" % t.getMaxWidth(t.root))
 
 

К статье присоединен файл sources.zip, в котором находятся два файла исходного кода: tree_operations.c и tree_operations.py. В первом файле содержится полноценная программа на языке Си, использующая функции, разработанные в этой статье, для выполнения операций над бинарным деревом. Во втором файле приведен сценарий на языке Python, в котором реализованы сходные алгоритмы для работы с бинарными деревьями. Реализация на Python ближе по стилю к объектно-ориентированному программированию, так как в ней используются классы для объявления самого дерева и входящих в него узлов.

В данной статье была выполнена классификация бинарных деревьев и рассмотрены алгоритмы для выполнения важнейших операций: определение высоты и ширины дерева, отражение дерева и поиск в нем определенного элемента. Также был рассмотрен алгоритм Хаффмана, который может использоваться для построения расширенных деревьев и, как следствие, для кодирования информации.

Часть 7

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

Эта статья посвящена одной из разновидностей двоичных деревьев: бинарным поисковым деревьям. Как обычно будут рассмотрены теоретические алгоритмы для выполнения различных операций: вставка и удаление узла, поиск максимума/минимума и практические реализации данных алгоритмов на языках Си и Python.

Бинарные поисковые деревья

Бинарные поисковые деревья (англ. binary search tree или сокращенно BST) - это разновидность двоичного дерева, обладающая следующими отличительными свойствами:

  1. для каждого узла X (если X не равен NULL) все узлы в его левом поддереве содержат значения, которые ВСЕГДА меньше значения узла X.
  2. все узлы в правом поддереве узла Х содержат значения, которые соответственно ВСЕГДА больше значения узла X.
  3. каждый узел в таком дереве является родителем для своих поддеревьев.

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

Результат вставки узлов в бинарное поисковое дерево может оказаться непредсказуемым. Если вставлять в такое дерево узлы, которые уже были предварительно отсортированы, то это приведет к вырождению дерева. На рисунке 1 показаны две одинаковые по содержанию реализации поискового дерева, но с различными корневыми узлами.


Рисунок 1. Два варианта представления бинарного поискового дерева
Рисунок 1. Два варианта представления бинарного поискового дерева
Рисунок 1. Два варианта представления бинарного поискового дерева

В листинге 1 приведено объявление структур для узла бинарного дерева и самого дерева на языке Си.


Листинг 1. Определение структур для представления дерева и его узлов
 
 
 struct node
 {
   int data;
   struct node * left;
   struct node * right;
 };
 
 struct tree
 {
   struct node * root;	// указатель на корень дерева
   int count;			// количество узлов в дереве
 };
 
 

Структура, использующаяся для описания узла дерева, полностью совпадает со структурой, использующейся для описания связного списка. Используя эти две структуры можно подготовить функцию на языке Си для создания дерева (см. листинг 2).


Листинг 2. Функция для создания дерева
 
 
 struct tree * tree_create(void)
 {
 struct tree * new_tree = malloc(sizeof * new_tree);
 	if (new_tree == NULL) return NULL;
 	new_tree->root = NULL;
 	new_tree->count = 0;
 	return new_tree;
 }
 
 

Вставка узла в бинарное поисковое дерево

Перед вставкой нового элемента в бинарное дерево обязательно нужно проверить, нет ли в нем уже такого элемента. Для этого необходимо начать обход дерева с корневого узла и проверить, не превосходит ли значение корневого узла добавляемого значения. Если корневой узел больше добавляемого элемента, то необходимо переместиться в левое дочернее дерево. В противном случае - в правое. Функция поиска определенного узла в дереве, приведенная в листинге 3, вернет 1 в случае, если искомое значение будет найдено, или 0, если указанное значение в дереве отсутствует.


Листинг 3. Функция для поиска узла в дереве
 
 
 int bin_search(const struct tree * search_tree, int item)
 {
   const struct node * search_node;
   search_node = search_tree->root;
 	for(;;)
 	{
 		if (search_node == NULL) return 0;
 		else if (item == search_node->data) return 1;
 		else if (item > search_node->data) search_node = search_node->right;  
 		else search_node = search_node->left;  
 	}
 }
 
 

После выполнения данной проверки можно переходить к добавлению узла в бинарное дерево. Функция вставки аналогична функции поиска: необходимо пройти по дереву и вставить узел в нужное место. Для этого следует выбрать левое или правое поддерево корневого узла, а затем рекурсивно перемещаться по выбранному поддереву до тех пор, пока не будет найдена позиция для вставки узла, как показано в листинге 4.


Листинг 4. Функция для вставки узла в бинарное поисковое дерево
 
 
 int insert(struct tree * search_tree, int item)
 {
 	struct node * search_node, **new;
 
 	new = &search_tree->root;
 	search_node = search_tree->root;
 
 	for(;;)
 	{
 		if(search_node == NULL)
 		{
 			search_node = *new = malloc(sizeof * search_node);
 			if(search_node != NULL)
 			{
 				search_node->data = item;
 				search_node->left = search_node->right=NULL;
 				search_tree->count++;
 				return 1;
 			}
 			else return 0;
 		}
 		else if(item == search_node->data) return 2;
 else if(item > search_node->data)
 {
 new = &search_node->right;
 			search_node = search_node->right;
 		}
 		else
 		{
 			new = &search_node->left;
 			search_node = search_node->left;
 		}
 	}
 }
 
 

Элемент, добавленный первым, автоматически становится корнем дерева. Функция может вернуть одно из 3-х значений: 0 (при вставке произошла ошибка), 1 (узел успешно вставлен), 2 (такой элемент уже есть в дереве).

Удаление узла из бинарного поискового дерева

Функция удаления узла из бинарного дерева также будет возвращать 0, если возникла ошибка, или 1 в случае удачного удаления элемента. В данной функции используется уже знакомый алгоритм поиска, который будет искать элемент, помеченный для удаления. После того, как этот элемент будет обнаружен, возможны 3 варианта действий, которые представлены на рисунке 2.


Рисунок 2. Три варианта удаления элемента из бинарного поискового дерева
Рисунок 2. Три варианта удаления элемента из бинарного поискового дерева
Рисунок 2. Три варианта удаления элемента из бинарного поискового дерева

В первом случае (вариант a) узел z имеет только левый дочерний узел, и при удалении он и будет заменен им. Во втором варианте (рисунок b) узел z заменяется узлом y.

В третьем варианте (рисунок с) корневой узел z заменяется узлом x, что приводит к дополнительным перестроениям в правом поддереве. Узел x становится преемником узла z, так как в левом поддереве узла z все узлы меньше 5, и преемника нужно искать в правом поддереве узла z.


Листинг 5. Функция для удаления узла из бинарного поискового дерева
 
 
 int delete(struct tree * search_tree, int ** item)
 {
 	struct node ** q,*z;
 	
 	q=&search_tree->root;
 	z=search_tree->root;
 	//поиск удаляемого элемента
 	for(;;)
 	{
 		if(z == NULL) return 0;
 		else if(item == (int **)z->data) break;
 		else if(item > (int **)z->data)
 		{
 			q = &z->right;
 			z = z->right;
 		}
 		else
 		{
 			q = &z->left;
 			z = z->left;
 		}
 	}		
 	
 	// непосредственное удаление элемента
 	if(z->right == NULL) *q = z->left;
 	else
 	{
 		struct node * y = z->right;
 		if(y->left == NULL)
 		{
 			y->left = z->left;
 			*q-y;
 		}
 		else
 		{
 			struct node * x=y->left;
 			while(x->left != NULL)
 			{
 				y = x;
 				x = y->left;
 			}
 			y->left = x->right;
 			x->left = z->left;
 			x->right = z->right;
 			*q=x;
 		}
 	}
 
 	search_tree->count --;
 	free(z);
 	return 1;
 }
 
 

Проход по дереву

Для прохода по дереву можно использовать рекурсию, так как любое двоичное дерево - это рекурсивная структура. Функции, приведенные в листинге 6, могут распечатать дерево, начиная с любого узла: сначала печатается левое поддерево, потом правое.


Листинг 6. Функции для вывода содержимого дерева
 
 
 //функция для распечатки фрагмента дерева - с любого узла
 static void walk(const struct node * search_node)
 {
 	if(node == NDLL) return;
 	walk(node->left);
 	printf("%d ", search_node->data);
 	walk(node->right);
 }	
 
 //функция для распечатки дерева целиком - с корня
 void walk2(const struct tree * my_tree)
 {
 	walk(my_tree->root);
 }
 
 

Для прохода по дереву можно обойтись и одной функцией, если ввести массив указателей на узлы, который будет заполняться во время прохода. В функции будет выполняться вложенный цикл для прохода дерева от текущего узла влево до конца. А дополнительный массив поможет обойти все дерево за один проход, так как в нем будет храниться указатель на текущий корневой узел.


Листинг 8. Нерекурсивная реализация обхода дерева
 
 void traverse(const struct tree * search_tree)
 {
 	struct node * stack[32];
 	int count;
 	struct node * search_node;
 	count = 0;
   search_node = search_tree->root;
 
 	for(;;)
 	{
 		while(search_node != NOLL)
 		{
 			stack[count++] = search_node;
 			search_node = search_node->left;
 		}
 		if(count == 0) return ;
 		search_node = stack[-count];
 		printf("%d",search_node->data);
 		search_node = search_node->right;
 	}
 }
 
 

В листинге 8 присутствует намеренное упрощение, так как в нем используется упрощенный статический вариант стека, хотя в реальной ситуации память под стек обязательно должна выделяться динамически.

Удаление дерева

В этом разделе приведены функции для полного удаления дерева, начиная с листьев и заканчивая корневым узлом.


Листинг 9. Функции для удаления дерева
 
 
 //функция для удаления отдельного узла дерева и его потомков
 static void destroy(struct node * search_node)
 {
 	if(search_node == NOLL) return;
 	destroy(search_node->left);
 	destroy(search_node->right);
 	free(search_node);
 } 
 
 //функция для полного удаления дерева
 void destroy(struct tree * search_tree)
 {
 	destroy(search_tree->root);
 	free(search_tree);
 }
 
 

Нахождение минимума и максимума в бинарном поисковом дереве

В листинге 10 приведены две функции для поиска в дереве узлов с минимальным и максимальным значением. Минимальное значение нужно искать в левом поддереве корневого элемента, а максимальное - в правом.


Листинг 10. Функции для поиска минимального и максимальных значений
 
 
 struct node * tree_minimum(struct tree * search_tree)
 {
 	struct node * search_node;
 search_node = search_tree->root;
 	while (search_node->left != NULL)
 			search_node = search_node->left;
 	return search_node;
 }
 
 struct node * tree_maximum(struct tree * search_tree)
 {
 	struct node * search_node;
 	search_node = search_tree->root;
 	while (search_node->right != NULL)
 			search_node = search_node->right;
 	return search_node;
 }
 
 

Определение типа двоичного дерева

Чтобы определить относится ли данное двоичное дерево к поисковым бинарным деревьям, можно использовать функцию из листинга 11.


Листинг 11. Определение типа двоичного дерева
 
 
 int isBST(struct node* node) 
 {
 	return(isBSTUtil(node, INT_MIN, INT_MAX));
 }
 
 int isBSTUtil(struct node* node, int min, int max) 
 {
 	if (node==NULL) return(true);
 
 	if (node->data<min || node->data>max) return(false);
 
 return (
 		isBSTUtil(node->left, min, node->data) &&
 		isBSTUtil(node->right, node->data+1, max)
 );
 }
 
 

Практическая реализация алгоритмов

Реализация на си

Мы сначала добавляем в бинарное дерево 10 элементов, при этом естественно соблюдаются все его атрибуты - т.е. для добавляемого элемента в дереве ищется его место по бинарному алгоритму. Потом мы проходим дерево и распечатываем его, потом удаляем элемент, потом снова распечатываем дерево, потом удаляем все дерево. Весь работающий код целиком для двоичного поискового лерева:

 
 
 #include < stdio.h>
 #include < stdlib.h>
 
 int count;
 
 struct node
 {
 	int data;
 	struct node * left;
   struct node * right;
 };
 
 struct tree
 {
 	struct node * root;
   int count;
 };
 
 
 struct tree * tree_create(void)
 {
 	struct tree * new_tree = malloc(sizeof * new_tree);
   if (new_tree == NULL) return NULL;
 	new_tree->root = NULL;
 	new_tree->count = 0;
 	return new_tree;
 }
 
 int bin_search(const struct tree * search_tree, int item)
 {
 	const struct node * search_node;
   search_node = search_tree->root;
 	for(;;)
 	{
 		if (search_node == NULL) return 0;
 		else if (item == search_node->data) return 1;
 		else if (item > search_node->data) search_node = search_node->right;  
 		else search_node = search_node->left;  
 	}
 }
 
 
 
 int insert(struct tree * search_tree, int item)
 {
 	struct node * search_node, **new;
 
 	new = &search_tree->root;
 	search_node = search_tree->root;
 
 	for(;;)
 	{
 		if(search_node == NULL)
 		{
 			search_node = *new = malloc(sizeof * search_node);
 			if(search_node != NULL)
 			{
 				search_node->data = item;
 				search_node->left = search_node->right=NULL;
 				search_tree->count++;
 				return 1;
 			}
 			else return 0;
 		}
 		else if(item == search_node->data) return 2;
     else if(item > search_node->data)
     {
       new = &search_node->right;
 			search_node = search_node->right;
 		}
 		else
 		{
 			new = &search_node->left;
 			search_node = search_node->left;
 		}
 	}
 }
 
 
 int delete(struct tree * search_tree, int ** item)
 {
 	struct node ** q,*z;
 	
 	q=&search_tree->root;
 	z=search_tree->root;
 	for(;;)
 	{
 		if(z == NULL) return 0;
 		else if(item == (int **)z->data) break;
 		else if(item > (int **)z->data)
 		{
 			q = &z->right;
 			z = z->right;
 		}
 		else
 		{
 			q = &z->left;
 			z = z->left;
 		}
 	}		
 	
 	// нашли - теперь удаляем
 	if(z->right == NULL) *q = z->left;
 	else
 	{
 		struct node * y = z->right;
 		if(y->left == NULL)
 		{
 			y->left = z->left;
 			*q-y;
 		}
 		else
 		{
 			struct node * x=y->left;
 			while(x->left != NULL)
 			{
 				y = x;
 				x = y->left;
 			}
 			y->left = x->right;
 			x->left = z->left;
 			x->right = z->right;
 			*q=x;
 		}
 	}
 
 	search_tree->count --;
 	free(z);
 	return 1;
 }
 
 
 void traverse(struct tree * search_tree)
 {
 	struct node * stack[search_tree->count];
 	int count;
 	struct node * search_node;
 	count = 0;
   search_node = search_tree->root;
 
 
 	for(;;)
 	{
 		while(search_node != NULL)
 		{
 			stack[count++] = search_node;
 			search_node = search_node->left;
 		}
 		if(count == 0) return ;
 		search_node = stack[--count];
 		printf("%d\n",search_node->data);
 		search_node = search_node->right;
 	}
 }
 
 
 static void destroy(struct node * search_node)
 {
 	if(search_node == NULL) return;
 	destroy(search_node->left);
 	destroy(search_node->right);
 	free(search_node);
 } 
 
 
 void bin_destroy(struct tree * search_tree)
 {
 	destroy(search_tree->root);
 	free(search_tree);
 }
 
 
 struct node * tree_minimum(struct tree * search_tree)
 {
 	struct node * search_node;
   search_node = search_tree->root;
 	while (search_node->left != NULL)
 			search_node = search_node->left;
 	return search_node;
 }
 
 
 struct node * tree_maximum(struct tree * search_tree)
 {
 	struct node * search_node;
   search_node = search_tree->root;
 	while (search_node->right != NULL)
 			search_node = search_node->right;
 	return search_node;
 }
 
 
 
 int  main()
 {
 
 	struct tree * my_tree = tree_create();
 	int res = insert(my_tree, 100);
 	res = insert(my_tree, 10);
 	res = insert(my_tree, 4);
 	res = insert(my_tree, 13);
 	res = insert(my_tree, 27);
 	res = insert(my_tree, 3);
 	res = insert(my_tree, 31);
 	res = insert(my_tree, 7);
 	res = insert(my_tree, 12);
 	res = insert(my_tree, 8);
 
 	my_tree->count = 10;
 	traverse(my_tree);
 	struct node * tree_min = tree_minimum(my_tree);
 	printf("\n%d\n\n", tree_min->data);
 	struct node * tree_max = tree_maximum(my_tree);
 	printf("\n%d\n\n", tree_max->data);
 	res = delete(my_tree, 31);
 	traverse(my_tree);
 	bin_destroy(my_tree);
 	
 	return 0 ;
 
 }
 
 
Реализация на питоне
 
 
 class node:
     def __init__(self, data = None, left = None, right = None):
         self.data   = data
         self.left   = left
         self.right  = right
 
     def __str__(self):
         return 'Node ['+str(self.data)+']'
 
 class Tree:
     def __init__(self):
         self.root = None
         self.count = 0
 
     def insert(self,data):
         if self.root == None:
             self.root = node(data,None,None)
             return
             
         root = self.root        
         while (root != None):
             if (data < root.data):
                 if root.left == None:
                     root.left = node(data, None, None)
                     return
                 else:
                   root = root.left
             else:
                 if root.right == None:
                    root.right = node(data, None,None)
                    return
                 else:
                    root = root.right
 
 
     def traverse(self,node):
         if node == None:
             return
         print node.data
         if node.left:
           self.traverse(node.left)
         if node.right:
           self.traverse(node.right)
 
 t  = Tree()
 res = t.insert( 100)
 res = t.insert( 10)
 res = t.insert( 4)
 res = t.insert( 13)
 res = t.insert( 27)
 res = t.insert( 3)
 res = t.insert( 31)
 res = t.insert( 7)
 res = t.insert( 12)
 res = t.insert( 8)
 t.traverse(t.root)
 
 

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

В данной статье были рассмотрены основные алгоритмы, использующиеся для работы с одной из самых популярных структур данных – бинарным поисковым деревом. Кроме теоретических описаний в статье были представлены и практические реализации данных алгоритмов на языке программирования Си.

Следующий листинг показывает реализацию bst-деревьев на языке python. Программа выполняет стандартные операции с bst-деревом: вставляет и удаляет ноды, проверяет валидность всего дерева. По сценарию программа генерит bst-дерево, состоящее из 50 узлов, выводит его на экран, затем удаляет рутовую ноду и снова выводит получившееся bst-дерево на экран:

 
 
 import random
 
 class BSTnode(object):
     def __init__(self, parent, t):
         self.key = t
         self.parent = parent
         self.left = None
         self.right = None
         self.size = 1
         
     def update_stats(self):
         self.size = (0 if self.left is None else self.left.size) + (0 if self.right is None else self.right.size) 
 
     def insert(self, t, NodeType):
         self.size += 1
         if t < self.key:
             if self.left is None:
                 self.left = NodeType(self, t)                
                 return self.left
             else:
                 return self.left.insert(t, NodeType)
         else:
             if self.right is None:
                 self.right = NodeType(self, t)   
                 return self.right
             else:
                 return self.right.insert(t, NodeType)
 
     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)
 
     def minimum(self):
         current = self
         while current.left is not None:
             current = current.left
         return current
             
     def successor(self):
         if self.right is not None:
             return self.right.minimum()
         current = self
         while current.parent is not None and current.parent.right is current:
             current = current.parent
         return current.parent
 
     def delete(self):
         if self.left is None or self.right is None:
             if self is self.parent.left:
                 self.parent.left = self.left or self.right
                 if self.parent.left is not None:
                     self.parent.left.parent = self.parent
             else:
                 self.parent.right = self.left or self.right
                 if self.parent.right is not None:
                     self.parent.right.parent = self.parent 
             current = self.parent
             while current.key is not None:
                 current.update_stats()
                 current = current.parent
             return self
         else:
             s = self.successor()
             self.key, s.key = s.key, self.key
             return s.delete()        
         
             
     def __repr__(self):
         return ' '
 
 class BST(object):
 
     def __init__(self, NodeType=BSTnode):
         self.root = None
         self.NodeType = NodeType
         self.psroot = self.NodeType(None, None)
     
     def reroot(self):
         self.root = self.psroot.left
 
     def insert(self, t):
         if self.root is None:
             self.psroot.left = self.NodeType(self.psroot, t)
             self.reroot()
             return self.root
         else:
             return self.root.insert(t, self.NodeType)
         
     def find(self, t):
         if self.root is None:
             return None
         else:
             return self.root.find(t)
         
     def delete(self, t):
  	deleted = self.root.delete()
 	return
         node = self.find(t)
 	if node:
 	  #deleted = self.root.delete()
 	  deleted = node.delete()
 	  self.reroot()
 	  return deleted
 	return None
 
     def __str__(self):
         if self.root is None: return ''
         def recurse(node):
             if node is None: return [], 0, 0
             label = str(node.key)
             left_lines, left_pos, left_width = recurse(node.left)
             right_lines, right_pos, right_width = recurse(node.right)
             middle = max(right_pos + left_width - left_pos + 1, len(label), 2)
             pos = left_pos + middle // 2
             width = left_pos + middle + right_width - right_pos
             while len(left_lines) < len(right_lines):
                 left_lines.append(' ' * left_width)
             while len(right_lines) < len(left_lines):
                 right_lines.append(' ' * right_width)
             if (middle - len(label)) % 2 == 1 and node.parent is not None and \
                node is node.parent.left and len(label) < middle:
                 label += '.'
             label = label.center(middle, '.')
             if label[0] == '.': label = ' ' + label[1:]
             if label[-1] == '.': label = label[:-1] + ' '
             lines = [' ' * left_pos + label + ' ' * (right_width - right_pos),
                      ' ' * left_pos + '/' + ' ' * (middle-2) +
                      '\\' + ' ' * (right_width - right_pos)] + \
               [left_line + ' ' * (width - left_width - right_width) +
                right_line
                for left_line, right_line in zip(left_lines, right_lines)]
             return lines, pos, width
         return '\n'.join(recurse(self.root) [0])
 
     def validate_(self,  min, max):
 	return self.validate(self.root, min, max)
 	
          
 
     def validate(self, root, min, max):
 	if (root == None):
 		return True
 	if (root.key <= min or root.key >= max):
 		return False
 	return self.validate(root.left, min, root.key) and self.validate(root.right, root.key, max);
 
 
 tree = BST()
 l = []
 for i in range(1,50):
   ii = random.randint(1, 50)
   if ii in l:
     pass
   else:
     l.append(ii)
 
 for ll in l:
    tree.insert(ll)
    
 print tree
 tree.delete(0)
 print tree
 
 f = open('bst','w')
 f.write(str(tree))
 f.close
 
 print tree.validate_( 0, 10000000000)
 
 
 

Часть 8

Сбалансированные двоичные деревья (AVL-деревья)

В этой главе будет рассматриваться другая разновидность бинарных поисковых деревьев - AVL-деревья или сбалансированные двоичные деревья с минимальным временем поиска по дереву. Это свойство AVL-деревьев обеспечивается их сбалансированностью, которая одновременно усложняет алгоритмы для вставки узлов в дерево и их последующего удаления. В рамках статьи будут рассмотрены характеристики AVL-деревьев и алгоритмы для работы с ними, реализованные на языке Си.

Сбалансированные деревья

Прежде чем переходить к обсуждению сбалансированных деревьев, необходимо вернуться к значению термина «высота дерева». Высота дерева – это число узлов от вершины до самого нижнего узла, т.е. максимальное количество узлов, по которому можно пройти, начав с корня дерева и перемещаясь в одном направлении.

Очевидно, что время поиска по двоичному дереву зависит от высоты дерева, и чем выше дерево - тем больше времени требуется на поиск определенного узла в дереве. Например, если высота дерева равна 5, то в наихудшем случае придется выполнить 5 сравнений.

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


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

Чтобы создать сбалансированное двоичное дерево, необходимо изменить структуру узла, добавив в него дополнительный указатель на родительский узел, как показано в листинге 1.


Листинг 1. Структура узла для сбалансированного дерева
 
 
 struct node
 {
 	int data;
 	struct node * left;
 	struct node * right;
 	struct node * parent;
 }
 
 

И определить функцию, которая будет искать «наследника» (ближайшее большее число) для указанного родительского узла.


Листинг 2. Функция для поиска наследника
 
 
 static struct node * successor(struct node * x)
 {
 	struct node * y;
 	if(x->right != NULL)
 	{
 		у = x->right;
 		while(y->left != NULL) 
 			у = y->left;
 	}
 	else
 	{
 		у = x->parent;
 		while(y != NULL && x == y->right)
 		{
 			x = y ;
 			y = y->parent;
 		}
 	}
 	return y;
 }
 
 

Если у узла имеется правый дочерний узел, то его наследником будет минимальное значение в правом поддереве (см. рисунок 2 – наследником узла 8 будет узел 9, как минимальный в правом поддереве узла 8). Если же правый потомок отсутствует, тогда в поисках наследника необходимо перемещаться вверх и вправо (см. рисунок 2 – наследником узла 11 будет узел 12).


Рисунок 2. Сбалансированное дерево
Рисунок 2. Сбалансированное дерево

Указатель на родительский узел - это не единственный способ облегчить проход по дереву. Так, в дереве возможна ситуация, когда узел не имеет дочерних узлов. Это можно использовать для хранения указателей на другие части дерева, например, на предшественника и наследника данного узла. Для этого в узел потребуется добавить два битовых поля, как показано в листинге 3.


Листинг 3. Расширенная структура для описания узла дерева
 
 
 struct node
 {
 	int data;
 	struct node * left;
 	struct node * right;
 	unsigned l_thread:1;
 	unsigned r_thread:1;
 };
 
 

Эти поля используются следующим образом:

  • если битовые поля содержат 0, значит, указатели left и right указывают на левое и правое поддеревья данного узла;
  • если битовые поля содержат 1, значит, указатели left и right указывают на родителя и потомка данного узла.

Используя данные поля, можно переписать функцию для поиска наследника, как показано в листинге 4.


Листинг 4. Модифицированная функция для поиска наследника узла
 
 
 static struct node * successor(struct  node * x)
 {
 	struct node * y;
 	у = x->right;
 	if(x->r_thread == 0)
 	while(y->l_thread == 0)
 		у = y->left;
 	return y;
 }
 
 

Для данной реализации дерева есть специальное название - дерево с полными ссылками. Также существуют деревья с правыми ссылками, где вместо двух битовых полей используется одно. Дерево с правыми ссылками более эффективно при поиске, так как на его прохождение требуется меньше времени.

Для получения сбалансированного двоичного дерева придется потратить определенные усилия. Так, если в дерево вставлять уже отсортированный массив, то оно может выродиться в список. Поэтому после каждой вставки необходимо проводить балансировку дерева.

А в общем случае после любой модификации дерева требуется выполнять балансировку дерева, чтобы минимизировать его высоту, так как меньше всего времени требуется на поиск по двоичному дереву с минимальной высотой. Балансировка влияет и на процессы вставки/удаления узлов, которые также будут проходить быстрее из-за более эффективного поиска. На данный момент не существует общепринятых стандартов для балансировки дерева, так что в этой области допускается определенная свобода при реализации новых или выборе из уже существующих алгоритмов балансировки.

AVL-деревья

Одним из известных типов сбалансированных двоичных деревьев является AVL-дерево, у которого коэффициент сбалансированности находится в пределах от -1 до +1. Полностью сбалансированное двоичное дерево с n узлами имеет высоту равную log(n+1) по основанию 2, округленную до ближайшего целого числа. В листинге 5 приведен исходный код структуры, описывающей узел AVL-дерева.

AVL - аббревиатура, созданная из первых букв фамилий советских математиков: Г.М. Адельсона-Вельского и Е.М. Ландиса, придумавших данную структуру данных. Для определения AVL-дерева используется коэффициент сбалансированности - разница между высотой правого и левого поддеревьев.

Листинг 5. Структура, определяющая узел AVL-дерева
 
 
 struct avl_node
 {
 	struct avl_node * link[2];
 	int data;
 	short bal;
 };
 
 

В нем сразу видно отличие от классической реализации – указатели на поддеревья будут храниться в специальном массиве, а не в двух отдельных переменных. Переменная bal определяет значение коэффициента сбалансированности, и поэтому может принимать только значения из списка: -1, 0, +1.

Добавление узла в AVL-дерево

Процесс вставки узла в AVL-дерево отличается от добавления узла в обычное бинарное дерево. Так, для вставки нового узла в AVL-дерево, необходимо:

  1. найти место, где должен будет находиться новый узел;
  2. добавить узел в дерево на найденную позицию;
  3. пересчитать коэффициенты сбалансированности для узлов, находящихся выше добавленного узла;
  4. если дерево стало несбалансированным, то выполнить балансировку.

В листинге 6 приведен исходный код функции для вставки узла в AVL-дерево.


Листинг 6. Функция для вставки узла в AVL-дерево
 
 
 int avl_insert(struct avl_tree * tree, int item)
 {
 	struct avl_node ** v, *w, *x, *y, *z;
 
 /* если в дереве еще нет узлов */
 	v = &tree->root;
 	x = z = tree->root;
 	if(x == NULL)
 	{
 		tree->root = new_node(tree,item);
 		return tree->root != NULL;
 	}
 
 /* фрагмент №1 */
 /* поиск подходящей позиции и последующая вставка элемента */
 	for(;;)
 	{
 		int dir;
 		/* такой элемент уже есть в дереве – функцию можно завершить */
 		if(item == z->data) return 2;
 
 		dir = (item > z->data) ;
 		y = z->link[dir];
 		if(y == NULL)
 		{
 			y = z->link[dir] = new_node(tree,item);
 			if(y == NULL) return 0;
 			break;
 		}
 		if(y->bal != 0)
 		{
 			v = &z->link[dir];
 			x = y;
 		}
 		z = y;
 	}
 
 /* фрагмент №2 */
 /* пересчет коэффициентов сбалансированности для узлов, затронутых вставкой */
 	w = z = x->link[item > x->data];
 	while(z != y)
 		if(item < z->data)
 		{
 			z->bal = -1;
 			z = z->link[0];
 		}
 		else
 		{
 			z->bal	=	+1;
 			z = z->link[1];
 		}
 
 /* фрагмент № 3 */
 /* балансировка при добавлении нового узла в левое поддерево */
 	if(item < x->data)
 	{
 		if (x->bal != -1)
 			x->bal --;
 		else if(w->bal == -1)
 		{
 			*v=w;
 			x->link[0] = w->link[1];
 			w->link[1] = x;
 			x->bal = w->bal = 0;
 		}
 		else
 		{
 			*v = z = w->link[1];
 			w->link[1] = z->link[0];
 			z->link[0] = w;
 			x->link[0] = z->link[1];
 			z->link[1] = x;
 			if(z->bal == -1)
 			{
 				x->bal = 1;
 				w->bal = 0;
 			}			
 			else if(z->bal == 0)
 				x->bal = w->bal = 0;
 			else
 			{
 				x->bal = 0;
 				w->bal = -1;
 			}
 			z->bal=0;
 		}
 	}
 /* фрагмент № 4 */
 /* балансировка при добавлении нового узла в правое поддерево */
 	else 
 	{
 		if( x->bal != +1)
 			x->bal++;
 		else if(w->bal == +1)
 		{
 			*v = w;
 			x->link[1] = w->link[0];
 			w->link[0] = x;
 			x->bal = w->bal = 0;	
 		}
 		else
 		{
 			*v = z = w->link[0];
 			w->link[0] = z->link[1];
 			z->link[1] = w;
 			x->link[1] = z->link[0];
 			z->link[0] = x;
 			if(z->bal == +1)
 			{
 				x->bal = -1;
 				w->bal = 0;			
 			}
 			else if(z->bal == 0)
 				x->bal = w->bal = 0;
 			else
 			{
 				x->bal = 0;
 				w->bal = 1;
 			}
 			z->bal = 0;
 		}
 	}
 	return 1;
 }
 
 

Так как функция avl_insert получилась довольно объемной, стоит рассмотреть ее в подробностях. В фрагменте №1 листинга 6 производится поиск позиции и вставка узла в AVL-дерево. В этом фрагменте используется временная переменная z для отслеживания текущего узла. Если значение добавляемого узла равно значению, содержащемуся в узле z, то функция завершается, так как бинарное дерево не может содержать узлы с дублирующимися значениями.

Затем в переменную y записывается указатель на следующий узел, находящийся в нужном поддереве (левом - если добавляемое значение меньше значения, содержащегося в текущем узле, или правом – если оно больше). Если y оказывается равным NULL, значит, у текущего узла отсутствует нужное поддерево и именно сюда и нужно вставлять добавляемое значение в виде нового узла. Для создания нового узла используется функция new_node приведенная в листинге 7.


Листинг 7. Функция для создания нового узла AVL-дерева
 
 
 struct avl_node * new_node(struct avl_tree * tree, int item)
 {
 	struct avl_node * node = malloc(sizeof * node);
 	node->data = item;
 	node->link[0] = node->link[1] = NULL;
 	node->bal = 0 ;
 	tree->count ++ ;
 	return node;
 };
 
 

Переменные x и v во фрагменте №1 используются для отслеживания последнего пройденного узла с ненулевым коэффициентом сбалансированности. Так как если коэффициент сбалансированности равен 0, то при вставке нового узла он изменится на +1 или -1, и в этом случае балансировка не потребуется. Если же коэффициент изначально не равен 0, то после вставки узла дерево придется балансировать.

Когда вставка нового узла y приводит к изменению коэффициентов для узлов, расположенных выше него, то требуется обновить коэффициенты для узлов, находящихся между узлами x и y. Эти действия выполняются во фрагменте №2 листинга 7.

Фрагмент № 3 листинга 6 соответствует ситуации, когда узел y находится в левом поддереве узла x. В этом случае, когда коэффициент сбалансированности для x изначально был равен -1, а после добавления узла стал равным -2, требуется выполнить балансировку. На рисунке 3 представлены два варианта выполнения балансировки.


Рисунок 3. Примеры балансировки дерева
Рисунок 3. Примеры балансировки дерева

В верхней половине рисунка 3 выполняется правая ротация узлов w и x, при этом узел w перемещается на место узла x. Узел x становится правым дочерним узлом для узла w, и в результате высота остается такой же, как и до вставки. В нижней половине рисунка 3 показана двойная ротация - сначала левая ротация узлов w и y, затем правая для узлов y и x.

Фрагмент №4 листинга описывает ситуацию с балансировкой, когда узел y находится в правом поддереве узла x.

Удаление узла из AVL-дерева

Удаление узла из AVL-дерева сложнее аналогичной операции для простого двоичного дерева и включает в себя следующие этапы:

  1. поиск узла, который требуется удалить; в процессе поиска запоминаются пройденные узлы для выполнения последующей балансировки;
  2. удаление искомого узла и обновление списка пройденных узлов;
  3. выполнение балансировки и перерасчет коэффициентов сбалансированности.

Листинг 8. Функция для удаления узла из AVL-дерева
 
 
 int avl_delete(struct avl_tree * tree, int item)
 {
 	struct avl_node * ap[32];
 	int ad[32];
 	
 	int k = 1;
 
 	struct avl_node ** y, * z;
 
 	ad[0] = 0 ;
 	ap[0] = (struct avl_node * ) &tree->root;
 
 	z = tree->root;
 
 /* поиск узла, выбранного для удаления */
 	for(;;)
 	{
 		int dir;
 		if(z == NULL)
 			return 0 ;
 		if (item == z->data)
 			break;
 
 		dir = item > z->data;
 		ap[k] = z;
 		ad[k++] = dir;
 		z = z->link[dir];
 	}
 
 /* выполняется удаление узла из дерева */
 	tree->count-- ;
 	y = &ap[k - 1]->link[ad[k-1]];
 	if(z->link[1] == NULL)
 		*y = z->link[0];
 	else
 	{ 
 		struct avl_node *x = z->link[1];
 		if (x->link[0] == NULL)
 		{
 			x->link[0] = z->link[0];
 			*y = x;
 			x->bal = z->bal;
 			ad[k] = 1;
 			ap[k++] = x;
 		}
 		else
 		{
 			struct avl_node *w = x->link[0];
 			int j = k++;
 			ad[k] = 0 ;
 			ap[k++] = x;
 			while (w->link[0] != NULL)
 			{
 				x = w;
 				w = x->link[0];
 				ad[k] = 0 ;
 				ap[k++] = x;
 			}
 			
 			ad[j] = 1;
 			ap[j] = w;
 			w->link[0] = z->link[0];
 			x->link[0] = w->link[1];
 			w->link[1] = z->link[1];
 			w->bal = z->bal;
 			*y = w;
 		}
 	}
 	free(z);
 
 /* балансировка получившегося дерева */
 	while(--k)
 	{
 		struct avl_node *w, *x;
 		w = ap[k];	
 		if (ad[k] == 0 )
 		{
 			if (w->bal == -1)
 			{
 				w->bal = 0;
 				continue;
 			}
 			else if (w->bal == 0 )
 			{
 				w->bal = 1;
 				break;
 			}
 			
 			x = w->link[1];
 			if (x->bal > -1)
 			{
 				w->link[1]= x->link[0];
 				x->link[0] = w;
 				ap[k-1]->link[ad[k-1]] = x;
 				if (x->bal == 0 )
 				{
 					x->bal = -1;
 					break;
 				}
 				else
 					w->bal = x->bal = 0 ;
 			}
 			else
 			{
 				z = x->link[0];
 				x->link[0] = z->link[1];
 				z->link[1] = x;
 				w->link[1] = z->link[0];
 				z->link[0] = w;
 				if (z->bal == 1)
 				{
 					w->bal = -1;
 					x->bal = 0;
 				}
 				else if (z->bal == 0 )
 					w->bal = x->bal = 0;
 				else
 				{
 					w->bal = 0;
 					x->bal = 1;
 				}
 				z->bal = 0;
 				ap[k-1]->link[ad[k-1]] = z;
 			}
 		}
 		else
 		{
 			if (w->bal == 1)
 			{
 				w->bal = 0 ;
 				continue;
 			}
 			else if (w->bal ==0)
 			{
 				w->bal = -1;
 				break;
 			}
 
 			x = w->link[0];
 			if (x->bal < 1)
 			{
 				w->link[0] = x->link[1]		;
 				x->link[1] = w;
 				ap[k-1]->link[ad[k-1]] = x;
 				if (x->bal == 0 )
 				{
 					x->bal = 1;
 					break;
 				}
 				else
 					w->bal = x->bal = 0;
 			}
 			else if (x->bal == 1)
 			{
 				z = x->link[1];
 				x->link[1] = z->link[0];
 				z->link[0] = x;
 				w->link[0] = z->link[1];
 				z->link[1] = w;
 				if (z->bal == -1)
 				{
 					w->bal = 1;
 					x->bal = 0;
 				}
 				else if (z->bal == 0 )
 					w->bal = x->bal = 0 ;
 				else
 				{
 					w->bal = 0 ;
 					x->bal = -1;
 				}
 				z->bal = 0;
 				ap[k-1]->link[ad[k-1]] = z;
 			}
 		}
 	}
 	return 1;
 }
 
 

В начале этой функции идет поиск узла, который необходимо удалить. Каждый пройденный узел z сравнивается с целевым значением item. Пройденные узлы помещаются в массив ap, а направления, по которым осуществляется движение, сохраняются в массив ad.

После этого происходит удаление узла из дерева, при этом возможны те же три варианта развития событий, как и при удалении узла из обычного двоичного дерева. Однако для AVL-дерева необходимо дополнительно отслеживать список узлов, расположенных выше удаляемого узла. После удаления выполняется балансировка, как и в случае с добавлением узла в дерево, но не по левому/правому поддеревьям, а по расположенным сверху элементам.

Несмотря на преимущества, предоставляемые AVL-деревьями при выполнении поиска по дереву, их использование затрудняется необходимостью балансировки после выполнения операций добавления / удаления узлов. Алгоритм балансировки представляет основную проблему, так как его неудачная реализация может негативно влиять на производительность программы, использующей данный тип дерева.

В статье были рассмотрены как теоретические аспекты работы с AVL-деревьями, так и основные алгоритмы для работы с ними, представленные в виде функций на языке Си. Изучив представленную реализацию и теоретические аспекты балансировки дерева, пользователь сможет сам разработать алгоритм балансировки AVL-дерева на Python.

Источник: Richard Heathfield . C Unleashed.

Часть 9

Красно-черные деревья

В данной статье рассматривается разновидность бинарных поисковых деревьев - красно-черные деревья, которые также относятся к сбалансированным деревьям. Такие деревья используются для решения самых разных задач, например, в одной из реализаций планировщика ядра ОС Linux (completely fair scheduler) или для создания ассоциативных массивов. В статье, как обычно, будут разбираться особенности реализации красно-черных деревьев и алгоритмов для работы с ними.

Красно-черные деревья

Красно-черное дерево (англ. red-black tree) - это еще одна форма сбалансированного бинарного поискового дерева. Впервые оно было представлено в 1972 году как еще одна разновидность сбалансированного бинарного дерева. Время поиска, вставки или удаления узла для красно-черного дерева является логарифмической функцией от числа узлов.

Данный тип деревьев отличается от других реализаций следующими свойствами:

  • каждый узел ассоциируется с определенным цветом - красным или черным;
  • корневой узел может быть любого цвета;
  • красные узлы могут иметь только черные дочерние узлы;
  • все пути от узла до любого листа, расположенного ниже в дереве, содержат одно и то же количество черных узлов.

Высота красно-черного дерева, состоящего из N узлов, лежит в диапазоне от двоичного логарифма log(N+1) до 2 * log(N+1).

В листинге 1 приведены структуры на языке Си, описывающие узлы красно-черного и AVL-деревьев.


Листинг 1. Исходный код узлов, использующихся в различных типах BST-деревьев
 
 
 /* структура, описывающая узел красно-черного дерева */
 struct rb_node 
 {
 	int red;
 	int data;
 	struct rb_node *link[2];
 };
 
 /* структура, описывающая узел AVL-дерева */
 struct avl_node
 {
 	struct avl_node * link[2];
 	int data;
 	short bal;
 };
 
 

Как можно заметить, структура узла AVL-дерева очень похожа на структуру, использующуюся для хранения информации об узле красно-черного дерева. Только коэффициент сбалансированности bal в красно-черном дереве заменен на переменную red, определяющую цвет узла (красный или черный). Но функции вставки/удаления узлов для красно-черного дерева значительно отличаются от аналогичных операций для AVL-дерева и должны быть рассмотрены отдельно.

Также для работы с красно-черным деревом потребуется вспомогательная структура из листинга 2.


Листинг 2. Структура, описывающая красно-черное дерево
 
 
 struct rb_tree 
 {
 	struct rb_node *root; // указатель на корневой узел
 	int count; // количество узлов в дереве
 };
 
 

Вставка узла в красно-черное дерево

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

Для упрощения алгоритма предполагается, что листья (узлы, не имеющие потомков) имеют черный цвет. В листинге 3 приведен исходный код функции для определения цвета узла.


Листинг 3. Функция для определения цвета узла
 
 
 int is_red ( struct rb_node *node )
 {
 	return node != NULL && node->red == 1;
 }
 
 

Для ротации узлов в дереве будут использоваться функции, представленные в листинге 4. Первая функция меняет местами два узла, вторая функция выполняет два таких обмена:


Листинг 4. Функции для ротации узлов в красно-черном дереве
 
 
 /* функция для однократного поворота узла */
 struct rb_node *rb_single ( struct rb_node *root, int dir )
 {
 	struct rb_node *save = root->link[!dir];
 
 	root->link[!dir] = save->link[dir];
 	save->link[dir] = root;
 
 	root->red = 1;
 	save->red = 0;
 
 	return save;
 }
 
 /* функция для двукратного поворота узла */
 struct rb_node *rb_double ( struct rb_node *root, int dir )
 {
 	root->link[!dir] = rb_single ( root->link[!dir], !dir );
 	return rb_single ( root, dir );
 }
 
 

В листинге 5 приведен исходный код функции для создания нового узла.


Листинг 5. Функция для создания нового узла
 
 
 struct rb_node *make_node ( int data )
 {
 	struct rb_node *rn = malloc ( sizeof *rn );
  
 	if ( rn != NULL ) {
 		rn->data = data;
 		rn->red = 1; /* –инициализация красным цветом */
 		rn->link[0] = NULL;
 		rn->link[1] = NULL;
 	}
 	return rn;
 }
 
 

При вставке узла в цветное дерево не требуется прибегать к рекурсии, так как это можно сделать за один проход. В общем случае при вставке нового узла возможны три варианта.

  1. происходит изменение цвета;
  2. требуется сделать один поворот;
  3. требуется сделать двойной поворот.

Для этого в памяти кроме текущего узла нужно хранить еще три уровня дерева: «родителя», «деда» и «прадеда» текущего узла.


Рисунок 1. Вставка узла в красно-черное дерево.
Рисунок 1. Вставка узла в красно-черное дерево.

На рисунке 1 в первом варианте у добавляемого узла (q) проверяются дочерние узлы. Если дочерние узлы - красного цвета, а добавляемый узел – черного, то выполняется смена цветов. Необходимо также проверить на совпадение цвета 2 узла (второй и третий варианты) - добавляемый узел (q) и его родителя (p). Если они оба красного цвета, то выполняется одиночная либо двойная ротация.


Листинг 6. Функция для вставки узла в красно-черное дерево
 
 
 int rb_insert ( struct rb_tree *tree, int data )
  {
    /* если добавляемый элемент оказывается первым – то ничего делать не нужно*/
    if ( tree->root == NULL ) {
      tree->root = make_node ( data );
      if ( tree->root == NULL )
        return 0;
    }
    else {
      struct rb_node head = {0}; /* временный корень дерева*/
      struct rb_node *g, *t;     /* дедушка и родитель */
      struct rb_node *p, *q;     /* родитель и итератор */
      int dir = 0, last;
  
      /* вспомогательные переменные */
      t = &head;
      g = p = NULL;
      q = t->link[1] = tree->root;
  
      /* основной цикл прохода по дереву */
      for ( ; ; ) 
      {
        if ( q == NULL ) {
          /* вставка ноды */
          p->link[dir] = q = make_node ( data );
          tree->count ++ ;
          if ( q == NULL )
            return 0;
        }
        else if ( is_red ( q->link[0] ) && is_red ( q->link[1] ) ) 
        {
          /* смена цвета */
          q->red = 1;
          q->link[0]->red = 0;
          q->link[1]->red = 0;
        }
         /* совпадение 2-х красных цветов */
        if ( is_red ( q ) && is_red ( p ) ) 
        {
          int dir2 = t->link[1] == g;
  
          if ( q == p->link[last] )
            t->link[dir2] = rb_single ( g, !last );
          else
            t->link[dir2] = rb_double ( g, !last );
        }
  
        /* такой узел в дереве уже есть  - выход из функции*/
 
        if ( q->data == data )
        {
          break;
        }
  
        last = dir;
        dir = q->data < data;
  
        if ( g != NULL )
          t = g;
        g = p, p = q;
        q = q->link[dir];
      }
  
      /* обновить указатель на корень дерева*/
      tree->root = head.link[1];
    }
    /* сделать корень дерева черным */
    tree->root->red = 0;
  
    return 1;
  }
 
 

Удаление узла из красно-черного дерева

При удалении узла из цветного дерева цвет родительского узла не изменяется. Удаление красного узла не влечет никаких последствий, коллизию может вызвать только удаление узла черного цвета. Поэтому при удалении черного узла для обеспечения целостности дерева необходимо использовать различные операции: простую смену цвета (если это возможно) или одну или несколько ротаций. На рисунке 2 представлены 4 ситуации, возможных при удалении черного узла.


Рисунок 2. Удаление узла из красно-черного дерева
Рисунок 2. Удаление узла из красно-черного дерева

Если при удалении черного узла, его «брат» (узел, находящийся на том же уровне, что и удаляемый) и все их четыре потомка имеют черный цвет (это вариант I на рисунке 2), то выполняется изменение цвета. Если «брат» удаляемого узла окрашен в красный цвет, то производится ротация, изображенная на варианте II. Если удаляемый узел и его «брат» черного цвета, а правый потомок «брата» - красного, то выполняется двойная ротация, изображенная на варианте 4. Если левый потомок «брата» красного, то выполняется одиночная ротация, как в пятом варианте.


Листинг 7. Функция для удаления узла из красно-черного дерева
 
 
 int br_remove ( struct rb_tree *tree, int data )
  {
    if ( tree->root != NULL ) 
    {
      struct rb_node head = {0}; /* временный указатель на корень дерева */
      struct rb_node *q, *p, *g; /* вспомогательные переменные */
      struct rb_node *f = NULL;  /* узел, подлежащий удалению */
      int dir = 1;
  
      /* инициализация вспомогательных переменных */
      q = &head;
      g = p = NULL;
      q->link[1] = tree->root;
  
      /* поиск и удаление */
      while ( q->link[dir] != NULL ) {
        int last = dir;
  
        /* сохранение иерархии узлов во временные переменные */
        g = p, p = q;
        q = q->link[dir];
        dir = q->data < data;
  
        /* сохранение найденного узла */
        if ( q->data == data )
          f = q;
  
        if ( !is_red ( q ) && !is_red ( q->link[dir] ) ) {
          if ( is_red ( q->link[!dir] ) )
            p = p->link[last] = rb_single ( q, dir );
          else if ( !is_red ( q->link[!dir] ) ) {
            struct rb_node *s = p->link[!last];
  
 
            if ( s != NULL ) {
              if ( !is_red ( s->link[!last] ) && !is_red ( s->link[last] ) ) {
                /* смена цвета узлов */
                p->red = 0;
                s->red = 1;
                q->red = 1;
              }
              else {
                int dir2 = g->link[1] == p;
  
                if ( is_red ( s->link[last] ) )
                  g->link[dir2] = rb_double ( p, last );
                else if ( is_red ( s->link[!last] ) )
                  g->link[dir2] = rb_single ( p, last );
  
                /* корректировка цвета узлов */
                q->red = g->link[dir2]->red = 1;
                g->link[dir2]->link[0]->red = 0;
                g->link[dir2]->link[1]->red = 0;
              }
            }
          }
        }
      }
  
      /* удаление найденного узла */
      if ( f != NULL ) {
        f->data = q->data;
        p->link[p->link[1] == q] =
          q->link[q->link[0] == NULL];
        free ( q );
      }
  
      /* обновление указателя на корень дерева */
      tree->root = head.link[1];
      if ( tree->root != NULL )
        tree->root->red = 0;
    }
  
    return 1;
  }
 
 

Сравнение AVL и красно-черных деревьев

У AVL и цветных деревьев есть как общие черты, так и отличия. Например, совпадает время, требующееся для вставки удаления/узлов в оба типа деревьев, которое в общем случае равно двоичному логарифму от общего числа узлов в дереве.

Для модификации обоих типов деревьев требуется выполнение дополнительных ротаций. Но вставка в AVL-дерево требует не более одной ротации, а удаление узла уже может потребовать большого количества ротаций, в общем случае, двоичный логарифм от числа узлов в дереве. Модификация красно-черных деревьев выполняется легче, так как вставка требует не более 2-х ротаций, а удаление - не более трех.

Также в случае, когда общее число узлов дерева] одинаково, максимальная высота AVL- дерева всегда будет меньше, чем максимальная высота красно-черного дерева. Высота красно-черного дерева может превышать высоту AVL-дерева в 1.38 раз, поэтому для выполнения поиска по красно-черному дереву требуется больше времени.

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

Сравнение производительности AVL и красно-черных деревьев

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

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

Реализация красно-черного дерева на языке Си была представлена в этой статье, а реализацию AVL-дерева можно взять из предыдущей статьи. В листинге 8 представлена программа для проверки производительности AVL-дерева, а в листинге 9 – эта же программа, но уже для красно-черного дерева.

Реализация на си:
 
 
 struct rb_node 
 {
    int red;
    int data;
    struct rb_node *link[2];
 };
  
 struct rb_tree 
 {
    struct rb_node *root;
    int count;
 };
 
 ...
 
 struct rb_tree * tree_create()
 {
   struct rb_tree * new_tree = malloc(sizeof * new_tree);
   if (new_tree == NULL) return NULL;
   new_tree->root = NULL;
   new_tree->count = 0;
   return new_tree;
 }
 
 int height(struct rb_node* node)
 {
    if (node==NULL)
        return 0;
    else
    {
      int left = height(node->link[0]);
      int right = height(node->link[1]);
  
      if (left > right)
          return(left+1);
      else return(right+1);
    }
 }
 
 
 int  main()
 {
  
   struct rb_tree * my_tree = tree_create();
   int rnd = (rand() % count);
   int res = rb_insert ( my_tree, rnd );
 
 }
 
 

Листинг 8. Тестирование производительности AVL-дерева
 
 
 int main()
 {
 
   struct avl_tree * my_tree = tree_create();
   
   int res = 0;
   int i = 0 ;
   int rnd = 0;
   int count = 10000000;
   
   time_t start,time2;
   volatile long unsigned t;
   start = time(NULL);
   
   srand (time (NULL));
   for( i = 0; i < count; i++) 
   {
     rnd = (rand() % count);
     res = avl_insert(my_tree, rnd);
     if(my_tree->count==5000000) break;
   }
   
  time2 = time(NULL);
  printf("\n затрачено %f секунд.\n", difftime(time2, start));
   
  printf("\n высота=%d количество узлов=%d\n",height(my_tree->root),my_tree->count);
   
  return 0 ;
 }
 
 


Листинг 9. Тестирование производительности красно-черного дерева
 
 
 int  main()
 {
   
   int count = 10000000;
   int res = 0;
   int i = 0 ;
   int rnd = 0;
   
   struct rb_tree * my_tree = tree_create();
 
   time_t start,time2;
   volatile long unsigned t;
   start = time(NULL);
   
   srand (time (NULL));
   for( i = 0; i < count; i++) 
   {
     rnd = (rand() % count);
     res = rb_insert ( my_tree, rnd );
     if(my_tree->count==5000000) break;
   }
 
   time2 = time(NULL);
   printf("\n затрачено %f секунд.\n", difftime(time2, start));
   
   printf("\n высота=%d количество узлов=%d\n",height(my_tree->root),my_tree->count);
   
   return 0 ;
 }
 
 

В ходе тестирования были получены следующие результаты: одному и тому же компьютеру потребовалось 16 секунд на вставку 5 миллионов узлов в AVL-дерево и 20 секунд на вставку такого же количества узлов в красно-черное дерево. При этом высота AVL-дерева оказалась равной 27, а цветного дерева - 28.

Таким образом, теория была подтверждена практикой: высота AVL-дерева оказалась чуть меньше высоты красно-черного дерева, что положительно сказалось на скорости вставки узлов в AVL-дерево. Используя представленные материалы, предлагается выполнить «обратное» тестирование на скорость удаления узлов из дерева, чтобы проверить утверждение, что удаление из AVL-дерева требует больше времени, нежели удаление из цветного дерева.

Часть 10

B-деревья и TRIE-деревья

TRIE-деревья

В современных текстовых редакторах (неважно online или offline) обязательно присутствует функция проверки орфографии вводимого текста на основе встроенного словаря. Эта функция должна извлечь из текста все слова и проверить их написание на соответствие со словарем. Для построения подобных словарей используется древовидная структура данных, которая называется TRIE-дерево (или дерево префиксов). Предположим, имеется следующий фрагмент текста:

THE THEN THIN THIS TIN SIN SING.
 

Требуется составить дерево из слов, входящих в это предложение, однако в этих словах присутствует много повторяющихся символов. TRIE-дерево предназначено для решения подобной задачи, как показано на рисунке 1.


Рисунок 1. TRIE-дерево
Рисунок 1. TRIE-дерево

Символ $ в терминальных узлах дерева - это endmarker, который позволит продолжить составление дерева со всеми возможными сочетаниями символов. Представленное дерево построено на основе английского алфавита, поэтому каждый узел может иметь не более 27 потомков - 26 букв и endmarker. На практике у большинства узлов будет меньше 27 потомков.

У TRIE-дерева есть свои преимущества и недостатки, так, оно требует больше памяти, чем двоичные деревья. В бинарном дереве у каждого узла может быть не более двух потомков, а в TRIE-дереве вообще нет ограничений на количество потомков, так что все упирается только в доступную память и количество символов в используемом алфавите.

В листинге 1 представлен один из возможных вариантов определения базовой структуры TRIE-дерева.


Листинг 1. Базовая структура для представления узлов TRIE-дерева
 
 
 enum trie_node_type
 {
   TRIE_LEAF,
   TRIE_SUBTRIE
 };
 
 typedef enum trie_node_type * trie_pointer;
 

В TRIE-дереве листья обозначаются как TRIE_LEAF, а поддеревья обозначаются как TRIE_SUBTRIE. Поэтому можно определить два типа узлов, как показано в листингах 2 и 3.


Листинг 2. Структура для описания поддерева
 
 
 //константы для управления скоростью поиска и использования памяти
 #define LOG_TRIE_BRAHCH_FACTOR 4 
 #define TRIE_BRANCH_FACTOR (1<<L0G_TRIE_BRANCH_FACT0R)
 
 struct trie_subtrie
 {
   enum trie_node_type type;
   struct trie_leaf * exact_match;
   //количество ключей, для которых узел является префиксом
   int count;
   trie_pointer next_level[TRIE_BRANCH_FACTOR];
 };
 
 


Листинг 3. Структура для описания узла
 
 
 struct trie_leaf
 {
   enum trie_node_type type;
   unsigned char * key; // уникальный поисковый ключ
   size_t len_key; // длина ключа
   trie_result result; //используется для вставки нового ключа
 }; 
 
 

В листинге 4 представлена структура для описания самого TRIE-дерева и функция для его создания.


Листинг 4. Создание TRIE-дерева
 
 
 struct trie
 {
   trie_pointer root;
 }; 
 
 struct trie * trie_create(void)
 {
   struct trie * trie = malloc(sizeof(*trie));
   if(trie)
   {
     trie->root=0;
   }
   return trie;
 }
 
 

Удаление дерева выполняется с помощью рекурсивной функции, способной работать как с узлами, имеющими потомков, так и с терминальными узлами.


Листинг 5. Функции для удаления узлов TRIE-дерева
 
 
 //функция для удаления всего дерева
 void trie_destroy(struct trie * trie)
 {
   if(trie)
   {
     destroy_node(trie->root);
     free(trie);
   }
 }
 
 //функция для удаления узла TRIE-дерева
 static void destroy_node(trie_pointer node)
 {
   if(node == 0) return;
   
   switch(*node)
   {
     case TRIE_LEAF:
     {
       struct trie_leaf * p = (struct trie_leaf * ) node;
       destroy_leaf(p);
       break;
     }
     case TRIE_SUBTRIE:
     {
       struct trie_subtrie * p = (struct trie_subtrie * )node;
       int i;
       destroy_leaf(p->exact_match);
       for(i=0; i<TRIE_BRANCH_FACTOR;i++)
           destroy_node(p->next_level[i]);
       free(p);
       break;
     }
     default:
   }
 }
 
 // функция для удаления терминального узла
 static void destroy_leaf(struct trie_leaf * leaf)
 {
   if(leaf)
   {
     free(leaf->key);
     free(leaf);
   }
 }
 
 

B-деревья

Как было показано в предыдущих статьях, если бинарное поисковое дерево сбалансировано, то его высота имеет логарифмическую зависимость от числа узлов. Поэтому, чем больше высота дерева, тем больше времени требуется на поиск в нем, так как для поиска нужного значения нужно пройти по большему количеству узлов.

Для решения этой проблемы предлагается древовидная структура, в которой высота получившегося дерева специально понижена. В B-дереве каждый узел может иметь более двух дочерних узлов, так что это дерево уже нельзя назвать бинарным деревом.

Характеристики B-дерева:

  1. m - порядок (максимальное количество дочерних узлов);
  2. каждый узел, кроме корневого, должен иметь как минимум m/2 дочерних узлов;
  3. корневой узел имеет как минимум 2 дочерних узла;
  4. все листья находятся на одном уровне;
  5. узел, имеющий k потомков, может иметь k-1 ключей.

Что касается ограничения на величину m, то оно зависит от характеристик жесткого диска, в частности от размера его блока.

Каждый узел в B-tree имеет упорядоченный набор ключей и набор указателей на своих потомков. Например, если у узла n0 имеются три потомка - n1, n2, n3, то ключами узла n0 должны быть два разделителя - a1 и a2, при этом - все ключи поддерева n1 должны быть меньше a1, все ключи поддерева n2 должны быть меньше a2, и т.д.

B-tree - это сбалансированное дерево, поэтому у каждого узла есть две константы:

  • U - максимально возможное число дочерних узлов;
  • L - минимально возможное число дочерних узлов.

Когда происходит вставка или удаление узла, эти константы рекурсивно проверяются по всему дереву сверху вниз. Если в каком-то узле возникает отклонение от значений L и U, то узлы будут объединяться или разделяться для восстановления баланса.

B-деревья широко применяются в базах данных и файловых системах. Также встречаются различные варианты B-деревьев, например, 2-3-дерево, где каждый узел может иметь не более трех потомков.

На рисунке 2 показан пример B-дерева. Когда количество ключей в узле превышает определенный порог, то этот узел разделяется на два узла, между которыми ключи делятся поровну. Каждый ключ в узле является корнем для поддерева, в котором хранятся ключи, находящиеся в диапазоне между соответствующими ключами корневого узла.


Рисунок 2. B-дерево
Рисунок 2. B-дерево

Так как B-дерево относится к сбалансированным, то путь от корня до любого листа требует одинакового количества шагов. Существует связь между максимальным количеством ключей в узле и максимальным количеством его потомков. Если число ключей обозначить как 2d, то число узлов обычно будет на единицу больше - 2d + 1. Также существует зависимость между высотой дерева h и количеством ключей n.

В данном типе дерева все листья должны располагаться на одном уровне дерева, поэтому такие деревья растут в сторону увеличения числа дочерних узлов, а не в высоту. Производительность поиска по B-дереву зависит от величины блока и скорости доступа к жесткому диску. Поэтому для повышения эффективности поиска важно уменьшить количество узлов за счет высокой ветвистости листьев.

Существуют два типа B-деревьев: B+ и B*. На рисунке 3 представлено B+-дерево. В данной реализации все данные хранятся в отдельном слое дерева - в листьях, при этом они отсортированы. Этот слой может быть организован в связный список, что является основным отличием от обычного B-дерева.


Рисунок 3. B+-дерево
Рисунок 3. B+-дерево

B*-дерево используется в файловых системах HFS и Reiser4 и отличается B+-деревьев тем, что когда узел полностью заполнен данными, то он не разбивается на 2 узла. Вместо этого ищется место в уже существующем соседнем узле, и только после того, как оба узла будут заполнены, они разделяются на три узла.

Операции с B-деревом

Для поиска или вставки узла в такое дерево требуется всего один проход. Поиск в B-дереве отличается от поиска в обычном бинарном дереве тем, что в последнем случае он основан на выборе между правым и левым узлом. В случае с B-деревом - это линейный поиск между соседними ключами.

При вставке ключа нужно учесть несколько вариантов: ключ может добавляться как в узел, так и в лист. В первом случае если происходит переполнение узла, то он делится пополам. На рисунке 4 показано, как может происходить формирование B-дерева в случае, когда в него последовательно вставляются натуральные числа от 1 до 7. В этом примере каждый узел может содержать не более двух ключей.


Рисунок 4. Создание B-дерева
Рисунок 4. Создание B-дерева

При удалении ключа происходит аналогичный процесс - объединение или разбиение узлов, который может затронуть все дерево от текущего узла до корня. Удаление также можно реализовать за один проход, но необходимо учесть два варианта развития событий:

  • ключ является разделителем;
  • при удалении ключа число ключей может стать меньше необходимого минимума.
Заключение

На этом цикл, посвященный различным структурам данных, закончен. В нем были рассмотрены базовые формы организации данных применительно к двум популярным языкам программирования: Си и Python.

Особое внимание было уделено связным спискам, как одной из наиболее важных и фундаментальных структур. Так было выполнено сравнение эффективности различных алгоритмов для работы со связными списками.

Вторая половина цикла была посвящена не менее значимой структуре данных — деревьям. Благодаря востребованности деревьев для файловых систем и баз данных, в данной области постоянно проводятся различные исследования и предлагаются новые подходы или оптимизированные версии уже существующих алгоритмов.

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

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

 Автор  Комментарий к данной статье
Анна
  Подскажите,пожалуйста,подробнее вставку элемента в произвольное место связного списка,а в частности пошагово про struct node**
2013-01-21 05:32:48
Нонна
  Замечательный цикл статей! Доступно изложены принципы работы с различными структурами данных. 
Все проиллюстрировано примерами. Особая благодарность за pyton! 
Спасибо за Вашу работу, которая облегчает жизнь нам, начинающим осваивать структуры данных. 
2017-02-17 09:03:28