1. Дейкстра с двоичной кучей.

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

2. Дерево поиска.

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

Задан список запросов к серверу. В каждом запросе сначала указывается логин, затем пароль и третьим параметром тип запроса: 0 – для авторизации, 1 – для регистрации. Программа должна быстро выводить логин и фразу «Доступ открыт!» или «Доступ запрещен» для каждого запроса авторизации.

3. Гороскоп.

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

Приложение к лекции.

using System;
using System.Collections.Generic;

namespace ConsoleApplication47
{
    internal class Program
    {
        private static int[,] _graf;
        private static List<Vertex> _list;

        public class Vertex
        {
            public Vertex(int index, int distance)
            {
                Index = index;
                Distance = distance;
            }

            public int Index;
            public int Distance;
        }

        public static void Main(string[] args)
        {
            int start = 0;
            int end = 0;
            //Console.Write("Введите N=");
            //int n = Convert.ToInt32(Console.ReadLine());
            int n = 7;

            int[,] graf = new int[n, n];
            _list = new List<Vertex>();

            //Console.Write("Введите M=");
            //int m = Convert.ToInt32(Console.ReadLine());
            int m = 10;

            /*
            for (int i = 0; i < m; i++)
            {
                Console.Write("Номер города, из которого идет дорога: ");
                start = Convert.ToInt32(Console.ReadLine());
                Console.Write("Номер города, в который идет дорога: ");
                end = Convert.ToInt32(Console.ReadLine());
                Console.Write("Номер города, в который идет дорога: ");
                int size = Convert.ToInt32(Console.ReadLine());
                graf[start, end] = size;
                graf[end, start] = size;
            }
            */

            graf[0, 3] = 25;
            graf[3, 0] = 25;
            graf[0, 5] = 23;
            graf[5, 0] = 23;
            graf[0, 6] = 27;
            graf[6, 0] = 27;
            graf[1, 3] = 22;
            graf[3, 1] = 22;
            graf[1, 4] = 29;
            graf[4, 1] = 29;
            graf[2, 4] = 24;
            graf[4, 2] = 24;
            graf[2, 6] = 23;
            graf[6, 2] = 23;
            graf[3, 4] = 54;
            graf[4, 3] = 54;
            graf[4, 5] = 59;
            graf[5, 4] = 59;
            graf[4, 6] = 49;
            graf[6, 4] = 49;

            //Console.Write("Введите X=");
            //start = Convert.ToInt32(Console.ReadLine());
            start = 0;

            //Console.Write("Введите Y=");
            //end = Convert.ToInt32(Console.ReadLine());
            end = 4;

            int[] path = new int[n];
            for (int i = 0; i < n; i++)
            {
                path[i] = Int32.MaxValue;
            }

            Boolean[] uses = new Boolean[n];


            path[start] = 0;
            int usesCount = 0;

            Vertex ver = new Vertex(start, 0);
            Add(ver);

            while (usesCount < n)
            {
                /*   int min = Int32.MaxValue;
                   int current = 0;
                   for (int i = 0; i < n; i++)
                   {
                       if (!uses[i] && path[i] < min)
                       {
                           min = path[i];
                           current = i;
                       }
                   }*/
                int current = GetMax();

                for (int i = 0; i < n; i++)
                {
                    if (graf[current, i] > 0 && !uses[i])
                    {
                        if (path[current] + graf[current, i] < path[i])
                        {
                            path[i] = path[current] + graf[current, i];
                            Add(new Vertex(i, path[i]));
                        }
                    }
                }

                uses[current] = true;
                usesCount++;
            }

            for (int i = 0; i < n; i++)
            {
                Console.WriteLine(i + " - " + path[i]);
            }

            Console.WriteLine("Ответ: " + path[end]);
        }

        private static void Add(Vertex value)
        {
            _list.Add(value);
            int i = HeapSize() - 1;
            int parent = (i - 1) / 2;

            while (i > 0 && _list[parent].Distance > _list[i].Distance)
            {
                Vertex temp = _list[i];
                _list[i] = _list[parent];
                _list[parent] = temp;

                i = parent;
                parent = (i - 1) / 2;
            }
        }

        private static void Heapify(int i)
        {
            int leftChild;
            int rightChild;
            int largestChild;

            for (;;)
            {
                leftChild = 2 * i + 1;
                rightChild = 2 * i + 2;
                largestChild = i;

                if (leftChild < HeapSize() && _list[leftChild].Distance < _list[largestChild].Distance)
                {
                    largestChild = leftChild;
                }

                if (rightChild < HeapSize() && _list[rightChild].Distance < _list[largestChild].Distance)
                {
                    largestChild = rightChild;
                }

                if (largestChild == i)
                {
                    break;
                }

                Vertex temp = _list[i];
                _list[i] = _list[largestChild];
                _list[largestChild] = temp;
                i = largestChild;
            }
        }

        private static int GetMax()
        {
            int result = _list[0].Index;
            _list[0] = _list[HeapSize() - 1];
            _list.RemoveAt(HeapSize() - 1);
            Heapify(0);
            return result;
        }

        private static int HeapSize()
        {
            return _list.Count;
        }

        private static void Print()
        {
            int i = 0;
            int k = 1;
            while (i < HeapSize())
            {
                while ((i < k) && (i < HeapSize()))
                {
                    Console.Write(_list[i].Distance + " ");
                    i++;
                }

                Console.WriteLine();
                k = k * 2 + 1;
            }
        }
    }
}

using System;
using System.Collections.Generic;

namespace ConsoleApplication47
{
    internal class Program
    {
        private static int[,] _graf;

        public class User
        {
            public User(string login, string password)
            {
                Login = login;
                Password = password;
            }

            public string Login;
            public string Password;
        }

        public class Inquiry
        {
            public Inquiry(string login, string password, int type)
            {
                Login = login;
                Password = password;
                Type = type;
            }

            public string Login;
            public string Password;
            public int Type;
        }

        public static void Main(string[] args)
        {
            List<Inquiry> inquiries = new List<Inquiry>();
            inquiries.Add(new Inquiry("admin", "12345", 1));
            inquiries.Add(new Inquiry("user", "111", 1));
            inquiries.Add(new Inquiry("Admin", "777", 1));
            inquiries.Add(new Inquiry("admin", "12345", 0));
            inquiries.Add(new Inquiry("user", "12345", 0));
            inquiries.Add(new Inquiry("user", "111", 0));
            inquiries.Add(new Inquiry("Sasha123", "12011995", 1));
            inquiries.Add(new Inquiry("admin", "12345", 0));
            inquiries.Add(new Inquiry("Sasha123", "12011995", 0));
            inquiries.Add(new Inquiry("Sasha123", "12345", 0));

            User first = new User("", "wjekljkljhsf234jhkh345h34h534j5h34kj5h3jh23j45jhewjhfsdlkjfg");
            BinaryTree tree = new BinaryTree(first, null);

            for (int i = 0; i < inquiries.Count; i++)
            {
                if (inquiries[i].Type == 1)
                {
                    User user = new User(inquiries[i].Login, inquiries[i].Password);
                    tree.Add(user);
                }
                else
                {
                    User user = new User(inquiries[i].Login, inquiries[i].Password);
                    if (tree.Search(user) == null)
                    {
                        Console.WriteLine("Элемент не найден!");
                    }
                    else
                    {
                        Console.WriteLine("Элемент найден!");
                    }
                }
            }
        }

        public class BinaryTree
        {
            private BinaryTree _parent, _left, _right;
            private User _value;

            public BinaryTree(User value, BinaryTree parent)
            {
                _value = value;
                _parent = parent;
            }

            public void Add(User value)
            {
                if (String.Compare(value.Login, _value.Login) < 0)
                {
                    if (_left == null)
                    {
                        _left = new BinaryTree(value, this);
                    }
                    else if (_left != null)
                    {
                        _left.Add(value);
                    }
                }
                else
                {
                    if (_right == null)
                    {
                        _right = new BinaryTree(value, this);
                    }
                    else if (_right != null)
                    {
                        _right.Add(value);
                    }
                }
            }

            private BinaryTree Search(BinaryTree tree, User value)
            {
                if (tree == null)
                {
                    return null;
                }

                if (string.Compare(value.Login, tree._value.Login) == 0 &&
                    string.Compare(value.Password, tree._value.Password) == 0)
                {
                    return tree;
                }

                if (string.Compare(value.Login, tree._value.Login) > 0)
                {
                    return Search(tree._right, value);
                }
                else
                {
                    return Search(tree._left, value);
                }
            }

            public BinaryTree Search(User value)
            {
                return Search(this, value);
            }

            private void Print(BinaryTree node)
            {
                if (node == null) return;

                Print(node._left);

                Console.Write(node + " ");

                if (node._right != null)
                {
                    Print(node._right);
                }
            }

            public void Print()
            {
                Print(this);

                Console.WriteLine();
            }

            public override string ToString()
            {
                return _value.Login;
            }
        }
    }
}

using System;

namespace ConsoleApplication48
{
    internal class Program
    {
        private class ZodiacSign
        {
            public ZodiacSign(int day, string sign)
            {
                Day = day;
                Sign = sign;
            }

            public int Day;
            public string Sign;
        }

        public static void Main(string[] args)
        {
            ZodiacSign[] signs = new ZodiacSign[13];

            signs[0] = new ZodiacSign(19, "Козерог");
            signs[1] = new ZodiacSign(18, "Водолей");
            signs[2] = new ZodiacSign(20, "Рыбы");
            signs[3] = new ZodiacSign(20, "Овен");
            signs[4] = new ZodiacSign(20, "Телец");
            signs[5] = new ZodiacSign(20, "Близнецы");
            signs[6] = new ZodiacSign(22, "Рак");
            signs[7] = new ZodiacSign(22, "Лев");
            signs[8] = new ZodiacSign(23, "Дева");
            signs[9] = new ZodiacSign(23, "Весы");
            signs[10] = new ZodiacSign(21, "Скорпион");
            signs[11] = new ZodiacSign(21, "Стрелец");
            signs[12] = new ZodiacSign(32, "Козерог");

            while (true)
            {
                Console.WriteLine("Для выхода введите 0!");
                Console.Write("Введите номер дня рождения:");
                int day = Convert.ToInt32(Console.ReadLine());
                if (day == 0)
                {
                    break;
                }

                Console.Write("Введите номер месяца рождения:");
                int month = Convert.ToInt32(Console.ReadLine());


                string prediction = "";
                if (day <= signs[month - 1].Day)
                {
                    prediction = signs[month - 1].Sign;
                }
                else
                {
                    prediction = signs[month].Sign;
                }

                Console.WriteLine(prediction);
            }
        }
    }
}

Итоги занятия.

1. Двоичная куча.

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

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

Двоичная куча представляет собой полное бинарное дерево, для которого выполняется основное свойство кучи: приоритет каждой вершины больше приоритетов её потомков. В простейшем случае приоритет каждой вершины можно считать равным её значению. В таком случае структура называется max-heap, поскольку корень поддерева является максимумом из значений элементов поддерева. А дерево называется полным бинарным, если у каждой вершины есть не более двух потомков, а заполнение уровней вершин идет сверху вниз (в пределах одного уровня – слева направо).

Двоичную кучу удобно хранить в виде одномерного массива, причем левый потомок вершины с индексом i имеет индекс 2*i+1, а правый 2*i+2. Корень дерева – элемент с индексом 0. Высота двоичной кучи равна высоте дерева, то есть log2N, где N – количество элементов массива.

2. Добавление элемента.

Новый элемент добавляется на последнее место в массиве, то есть позицию с индексом heapSize, где heapSize это количество элементов в куче:

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

Иначе говоря, новый элемент «всплывает», «проталкивается» вверх, пока не займет свое место. Сложность алгоритма не превышает высоты двоичной кучи (так как количество «подъемов» не больше высоты дерева), то есть равна O(log2N).

public void add(int value)
{
    _list.Add(value);
    int i = heapSize - 1;
    int parent = (i - 1) / 2;

    while (i > 0 && _list[parent] < _list[i])
    {
        int temp = _list[i];
        _list[i] = _list[parent];
        _list[parent] = temp;

        i = parent;
        parent = (i - 1) / 2;
    }
}

3. Упорядочение двоичной кучи.

В ходе других операций с уже построенной двоичной кучей также может нарушиться основное свойство кучи: вершина может стать меньше своего потомка.

Метод heapify восстанавливает основное свойство кучи для дерева с корнем в i-ой вершине при условии, что оба поддерева ему удовлетворяют. Для этого необходимо «опускать» i-ую вершину (менять местами с наибольшим из потомков), пока основное свойство не будет восстановлено (процесс завершится, когда не найдется потомка, большего своего родителя). Нетрудно понять, что сложность этого алгоритма также равна O(log2N).

public void heapify(int i)
{
    int leftChild;
    int rightChild;
    int largestChild;

    for (; ; )
    {
        leftChild = 2 * i + 1;
        rightChild = 2 * i + 2;
        largestChild = i;

        if (leftChild < heapSize && _list[leftChild] > _list[largestChild]) 
        {
            largestChild = _leftChild;
        }

        if (rightChild < heapSize && _list[rightChild] > _list[largestChild])
        {
            largestChild = rightChild;
        }

        if (largestChild == i) 
        {
            break;
        }

        int temp = _list[i];
        _list[i] = _list[largestChild];
        _list[largestChild] = temp;
        i = largestChild;
    }
}

4. Построение двоичной кучи.

Наиболее очевидный способ построить кучу из неупорядоченного массива – это по очереди добавить все его элементы. Временная оценка такого алгоритма O(N log2N). Однако можно построить кучу еще быстрее — за О(N). Сначала следует построить дерево из всех элементов массива, не заботясь о соблюдении основного свойства кучи, а потом вызвать метод heapify для всех вершин, у которых есть хотя бы один потомок (так как поддеревья, состоящие из одной вершины без потомков, уже упорядочены). Потомки гарантированно есть у первых heapSize/2 вершин.

5. Извлечение (удаление) максимального элемента.

В упорядоченном max-heap максимальный элемент всегда хранится в корне. Восстановить упорядоченность двоичной кучи после удаления максимального элемента можно, поставив на его место последний элемент и вызвав heapify для корня, то есть упорядочив все дерево.

public int getMax()
{
    int result = _list[0];
    _list[0] = _list[heapSize - 1];
    _list.RemoveAt(heapSize - 1);
    heapify(0);
    return result;
}

6. Сортировка с применением двоичной кучи.

Заметим, что можно отсортировать массив, сначала построив из него двоичную кучу, а потом последовательно извлекая максимальные (или соответственно минимальные) элементы. Оценим временную сложность такого элемента: построение кучи – O(N), извлечение N элементов – O(N log2N). Следовательно, итоговая оценка O(N log2N). При этом дополнительная память для массива не используется.

Приложение к лекции.

using System;
using System.Collections.Generic;
using System.Net.Sockets;
using System.Runtime.InteropServices;

namespace ConsoleApplication46
{
    internal class Program
    {
        private static List<int> _list;

        public static void Main(string[] args)
        {
            _list = new List<int>();
            add(5);
            add(7);
            add(9);
            add(11);
            add(3);
            add(7);
            add(15);
            Print();
            int x = GetMax();
            Console.WriteLine(x);
            Print();
        }

        private static void add(int value)
        {
            _list.Add(value);
            int i = HeapSize() - 1;
            int parent = (i - 1) / 2;

            while (i > 0 && _list[parent] < _list[i])
            {
                int temp = _list[i];
                _list[i] = _list[parent];
                _list[parent] = temp;

                i = parent;
                parent = (i - 1) / 2;
            }
        }

        private static void Heapify(int i)
        {
            int leftChild;
            int rightChild;
            int largestChild;

            for (;;)
            {
                leftChild = 2 * i + 1;
                rightChild = 2 * i + 2;
                largestChild = i;

                if (leftChild < HeapSize() && _list[leftChild] > _list[largestChild])
                {
                    largestChild = leftChild;
                }

                if (rightChild < HeapSize() && _list[rightChild] > _list[largestChild])
                {
                    largestChild = rightChild;
                }

                if (largestChild == i)
                {
                    break;
                }

                int temp = _list[i];
                _list[i] = _list[largestChild];
                _list[largestChild] = temp;
                i = largestChild;
            }
        }

        private static int GetMax()
        {
            int result = _list[0];
            _list[0] = _list[HeapSize() - 1];
            _list.RemoveAt(HeapSize() - 1);
            Heapify(0);
            return result;
        }

        private static int HeapSize()
        {
            return _list.Count;
        }

        private static void Print()
        {
            int i = 0;
            int k = 1;
            while (i < HeapSize())
            {
                while ((i < k) && (i < HeapSize()))
                {
                    Console.Write(_list[i] + " ");
                    i++;
                }

                Console.WriteLine();
                k = k * 2 + 1;
            }
        }
    }
}

Итоги занятия.

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

В программировании используют достаточно много видов деревьев:

N-арное дерево — это дерево, в котором каждая вершина имеет не более чем N детей.

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

А еще В-деревья, деревья цифрового поиска, нагруженные деревья, patricia-деревья, синтаксические деревья и другие.

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

В приведенном примере на рисунке оба дерева построены из одного
и того же набора ключей, но высота первого дерева больше, поэтому время выполнения операций над ним будет больше. Например, при поиске узла с ключом 6 в первом случае требуется просмотреть все шесть узлов, а во втором только три узла: 3->5->6.

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

Как построить дерево поиска минимальной высоты?

Если набор ключей известен заранее, то его надо упорядочить. Корнем поддерева становится узел с ключом, значение которого – медиана этого набора. Для упорядоченного набора, содержащего нечетное количество ключей, – это ключ, находящийся ровно в середине набора. Для набора 1,2,3,4,5,6, который содержит четное количество ключей, в качестве медианы может быть выбран ключ как со значением 3, так и со значением 4.

Для определенности выберем 3. Узел с этим ключом будет корнем дерева.

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

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

Но полный набор ключей не всегда известен заранее.

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

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

Рассмотрим три основных вида сбалансированных деревьев поиска:

⦁ АВЛ-деревья,
⦁ красно-черные деревья и
⦁ самоперестраивающиеся деревья (splay-деревья).

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

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

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

2. АВЛ-деревья.

АВЛ-деревом называется такое дерево поиска, в котором для любого его узла высоты левого и правого поддеревьев отличаются не более, чем на 1. Эта структура данных разработана советскими учеными Адельсон-Вельским Георгием Максимовичем и Ландисом Евгением Михайловичем в 1962 году. Аббревиатура АВЛ соответствует первым буквам фамилий этих ученых. Первоначально АВЛ-деревья были придуманы для организации перебора в шахматных программах. Советская шахматная программа «Каисса» стала первым официальным чемпионом мира в 1974 году.

В каждом узле АВЛ-дерева, помимо ключа, данных и указателей на левое и правое поддеревья (левого и правого сыновей), хранится показатель баланса – разность высот правого и левого поддеревьев. Ниже приведен пример АВЛ-дерева. Таким образом, получается, что в АВЛ-дереве показатель баланса balance для каждого узла, включая корень, по модулю не превосходит 1. На рисунке ниже справа приведен пример дерева, которое не является АВЛ-деревом, поскольку в одном из узлов баланс нарушен, т.е. |balance|>1. Здесь и далее для АВЛ-деревьев будем указывать в узле значение показателя баланса.

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

Но анализ возможных случаев показывает, что для исправления разбалансировки в узле p достаточно выполнить либо простой поворот влево вокруг p, либо так называемый большой поворот влево вокруг того же p. Простой поворот выполняется при условии, что высота левого поддерева узла q меньше высоты его правого поддерева: h(s)≤h(D).

Большой поворот применяется при условии h(s)>h(D) и сводится в данном случае к двум простым — сначала правый поворот вокруг q и затем левый вокруг p.

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

АВЛ-деревья исторически были первым примером использования сбалансированных деревьев поиска. В настоящее время более популярны красно-черные деревья (КЧ-деревья). Изобретателем красно-черного дерева считается немецкий ученый Рудольф Байер. КЧ-деревья – это двоичные деревья поиска, каждый узел которых хранит дополнительное поле color, обозначающее цвет: красный или черный, и для которых выполнены приведенные ниже свойства.

Будем считать, что если left или right равны NULL, то это «указатели» на фиктивные листья. Таким образом, все узлы – внутренние (нелистовые).

Свойства КЧ-деревьев:

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

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

Сам узел не включается в это число. Например, у дерева, приведенного на рисунке ниже, черная высота корня равна 2.

Определение: Черная высота дерева – черная высота его корня.

4. Самоперестраивающиеся деревья (splay trees).

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

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

⦁ если узел с ключом k есть в дереве, то он становится корнем;
⦁ если узла с ключом k нет в дереве, то корнем становится его предшественник или последователь.

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

5. Сравнение АВЛ, красно-черных и самоперестраивающихся деревьев (splay trees).

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

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

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

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

В каком случае какой вид деревьев лучше всего использовать.

Если входные данные полностью рандомизированы, то наилучшим вариантом оказываются деревья поиска общего вида – несбалансированные. Если входные данные в основном рандомизированные, но периодически встречаются упорядоченные наборы, то стоит выбрать КЧ-деревья. Если при вставке преобладают упорядоченные данные, то АВЛ-деревья оказываются лучше в случае, когда дальнейший доступ к элементам рандомизирован, а самоперестраивающиеся деревья – когда дальнейшие доступ последователен или кластеризован.

Итоги занятия.

1. Деревья.

Давайте рассмотрим еще одну структуру данных - дерево.

Дерево – связный граф без циклов.
Справочник терминов:
Корень — самый верхний узел дерева.
Ребро — связь между двумя узлами.
Потомок — узел, имеющий родительский узел.
Родитель — узел, имеющий ребро, соединяющее его с узлом-потомком.
Лист — узел, не имеющий узлов-потомков на дереве.
Высота — это длина самого дальнего пути к листу.
Глубина — длина пути к корню.

Например, дерево может выглядеть так:

Структура организации.

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

Дерево на картинке выше очень простое. Оно отражает только отношение родства категорий, но не накладывает никаких ограничений на свою структуру. У генерального директора может быть как один непосредственный подчиненный, так и несколько или ни одного. На рисунке отдел продаж находится левее отдела маркетинга, но порядок на самом деле не имеет значения. Единственное ограничение дерева — каждый узел может иметь не более одного родителя. Самый верхний узел (совет директоров, в нашем случае) родителя не имеет. Этот узел называется «корневым», или «корнем».

2. Двоичное дерево поиска.

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

Давайте посмотрим на дерево, построенное по этим правилам:

Обратите внимание, как указанные ограничения влияют на структуру дерева. Каждое значение слева от корня (8) меньше восьми, каждое значение справа — больше либо равно корню. Это правило применимо к любому узлу дерева.

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

Добавление элементов (метод add).

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

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

tree.Add(8);
tree.Add(4);
tree.Add(2);
tree.Add(3);
tree.Add(10);
tree.Add(6);
tree.Add(7);

Рассмотрим подробнее первые шаги.

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

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

Затем мы добавляем тройку. Она идет левее 8 и 4. Но так как 3 больше, чем 2, она становится правым ребенком 2, согласно третьему правилу.

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

Удаление элементов (метод remove).

Поведение: Удаляет первый узел с заданным значением.
Сложность: O(log n) в среднем; O(n) в худшем случае.
Удаление узла из дерева — одна из тех операций, которые кажутся простыми, но на самом деле таят в себе немало подводных камней.

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

Случай 1: У удаляемого узла нет правого ребенка.

В этом случае мы просто перемещаем левого ребенка (при его наличии) на место удаляемого узла. В результате дерево будет выглядеть так:

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

В этом случае нам надо переместить правого ребенка удаляемого узла (6) на его место. После удаления дерево будет выглядеть так:

Случай 3: У удаляемого узла есть первый ребенок, у которого есть левый ребенок.

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

Поиск значений (метод search).

Возвращает само значение, если такое значение содержится в дереве. В противном случает возвращает null.
Сложность: O(log n) в среднем; O(n) в худшем случае.
Метод проходит по дереву, выполняя в каждом узле следующие шаги:
Если текущий узел null, вернуть null.
Если значение текущего узла равно искомому, вернуть текущий узел.
Если искомое значение меньше значения текущего узла, установить левого ребенка текущим узлом и перейти к шагу 1.
В противном случае, установить правого ребенка текущим узлом и перейти к шагу 1.

Количество узлов в дереве.

Для подсчета получения количества узлов в дереве проще всего добавить переменную, значение которой инкрементируется методом add и декрементируется методом remove.

3. Обход деревьев.

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

Префиксный обход.

Сложность: O(n).
При префиксном обходе алгоритм получает значение текущего узла перед тем, как перейти сначала в левое поддерево, а затем в правое. Начиная от корня, сначала мы получим значение 4. Затем таким же образом обходятся левый ребенок и его дети, затем правый ребенок и все его дети.
Порядок обхода: 4, 2, 1, 3, 5, 7, 6, 8
Префиксный обход обычно применяется для копирования дерева с сохранением его структуры.

Постфиксный обход.

Сложность: O(n).
При постфиксном обходе мы посещаем левое поддерево, правое поддерево, а потом, после обхода всех детей, переходим к самому узлу.
Порядок обхода: 1, 3, 2, 6, 8, 7, 5, 4
Постфиксный обход часто используется для полного удаления дерева, так как в некоторых языках программирования необходимо убирать из памяти все узлы явно, или для удаления поддерева. Поскольку корень в данном случае обрабатывается последним, мы, таким образом, уменьшаем работу, необходимую для удаления узлов.

Инфиксный обход.

Сложность: O(n).
Инфиксный обход используется тогда, когда нам надо обойти дерево в порядке, соответствующем значениям узлов. В примере выше в дереве находятся числовые значения, поэтому мы обходим их от самого маленького до самого большого. То есть от левых поддеревьев к правым через корень.
Порядок обхода: 1, 2, 3, 4, 5, 6, 7, 8
В примере этот обход используется в методе print.

Приложение к лекции.

using System;

namespace ConsoleApplication44
{
    internal class Program
    {
        public static void Main(string[] args)
        {
            BinaryTree tree = new BinaryTree(15, null);
            tree.Add(25);
            tree.Add(23);
            tree.Add(29);
            tree.Add(17);
            tree.Add(31);
            tree.Add(5);
            tree.Remove(23);
            
            if (tree.Search(25) == null)
            {
                Console.WriteLine("Элемент не найден!");
            }
            else
            {
                Console.WriteLine("Элемент найден!");
            }
            
            tree.Print();
        }
    }

    public class BinaryTree
    {
        private BinaryTree _parent, _left, _right;
        private int _value;

        public BinaryTree(int value, BinaryTree parent)
        {
            _value = value;
            _parent = parent;
        }

        public void Add(int value)
        {
            if (value < _value)
            {
                if (_left == null)
                {
                    _left = new BinaryTree(value, this);
                }
                else if (_left != null)
                {
                    _left.Add(value);
                }
            }
            else
            {
                if (_right == null)
                {
                    _right = new BinaryTree(value, this);
                }
                else if (_right != null)
                {
                    _right.Add(value);
                }
            }
        }

        private BinaryTree Search(BinaryTree tree, int value)
        {
            if (tree == null)
            {
                return null;
            }
            
            if (value == tree._value)
            {
                return tree;
            }

            if (value > tree._value)
            {
                return Search(tree._right, value);
            }
            else
            {
                return Search(tree._left, value);
            }
        }

        public BinaryTree Search(int value)
        {
            return Search(this, value);
        }

        public bool Remove(int value)
        {
            //Проверяем, существует ли данный узел
            BinaryTree tree = Search(value);
            if (tree == null)
            {
                //Если узла не существует, вернем false
                return false;
            }

            BinaryTree curTree;
            //Если удаляем корень
            if (tree == this)
            {
                if (tree._right != null)
                {
                    curTree = tree._right;
                }
                else
                {
                    curTree = tree._left;
                }

                while (curTree._left != null)
                {
                    curTree = curTree._left;
                }

                int temp = curTree._value;
                Remove(temp);
                tree._value = temp;

                return true;
            }

            //Удаление листьев
            if (tree._left == null && tree._right == null && tree._parent != null)
            {
                if (tree == tree._parent._left)
                {
                    tree._parent._left = null;
                }
                else
                {
                    tree._parent._right = null;
                }

                return true;
            }

            //Удаление узла, имеющего левое поддерево, но не имеющее правого поддерева
            if (tree._left != null && tree._right == null)
            {
                //Меняем родителя
                tree._left._parent = tree._parent;
                if (tree._parent != null && tree == tree._parent._left)
                {
                    tree._parent._left = tree._left;
                }
                else if (tree._parent != null && tree == tree._parent._right)
                {
                    tree._parent._right = tree._left;
                }

                return true;
            }

            //Удаление узла, имеющего правое поддерево, но не имеющее левого поддерева
            if (tree._left == null && tree._right != null)
            {
                //Меняем родителя
                tree._right._parent = tree._parent;
                
                if (tree._parent != null && tree == tree._parent._left)
                {
                    tree._parent._left = tree._right;
                }
                else if (tree._parent != null && tree == tree._parent._right)
                {
                    tree._parent._right = tree._right;
                }

                return true;
            }

            //Удаляем узел, имеющий поддеревья с обеих сторон
            if (tree._right != null && tree._left != null)
            {
                curTree = tree._right;

                while (curTree._left != null)
                {
                    curTree = curTree._left;
                }

                //Если самый левый элемент является первым потомком
                if (curTree._parent == tree)
                {
                    curTree._left = tree._left;
                    tree._left._parent = curTree;
                    curTree._parent = tree._parent;
                    
                    if (tree._parent != null && tree == tree._parent._left)
                    {
                        tree._parent._left = curTree;
                    }
                    else if (tree._parent != null && tree == tree._parent._right)
                    {
                        tree._parent._right = curTree;
                    }

                    return true;
                }
                //Если самый левый элемент НЕ является первым потомком
                else
                {
                    if (curTree._right != null)
                    {
                        curTree._right._parent = curTree._parent;
                    }

                    curTree._parent._left = curTree._right;
                    curTree._right = tree._right;
                    curTree._left = tree._left;
                    tree._left._parent = curTree;
                    tree._right._parent = curTree;
                    curTree._parent = tree._parent;
                    
                    if (tree._parent != null && tree == tree._parent._left)
                    {
                        tree._parent._left = curTree;
                    }
                    else if (tree._parent != null && tree == tree._parent._right)
                    {
                        tree._parent._right = curTree;
                    }

                    return true;
                }
            }

            return false;
        }

        private void Print(BinaryTree node)
        {
            if (node == null) return;
            
            Print(node._left);
            
            Console.Write(node + " ");
            
            if (node._right != null)
            {
                Print(node._right);
            }
        }

        public void Print()
        {
            Print(this);
            
            Console.WriteLine();
        }

        public override string ToString()
        {
            return _value.ToString();
        }
    }
}

Итоги занятия.

1. Примеры задач на графы. Связность. Компоненты связности.

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

2. Компоненты связности.

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

Фрагмент кода:

int count = 0;
//Console.Write("Введите N=");
//int n = Convert.ToInt32(Console.ReadLine());
int n = 10;

int[,] graf = new int[n, n];

//Console.Write("Введите M=");
//int m = Convert.ToInt32(Console.ReadLine());
int m = 8;

/*
for (int i = 0; i < m; i++)
{
    Console.Write("Номер города, из которого идет дорога: ");
    start = Convert.ToInt32(Console.ReadLine());
    Console.Write("Номер города, в который идет дорога: ");
    end = Convert.ToInt32(Console.ReadLine());
    Console.Write("Номер города, в который идет дорога: ");
    int size = Convert.ToInt32(Console.ReadLine());
    graf[start, end] = size;
    graf[end, start] = size;
}
*/

graf[0, 3] = 1;
graf[3, 0] = 1;
graf[0, 6] = 1;
graf[6, 0] = 1;
graf[3, 6] = 1;
graf[6, 3] = 1;
graf[1, 5] = 1;
graf[5, 1] = 1;
graf[5, 4] = 1;
graf[4, 5] = 1;
graf[7, 8] = 1;
graf[8, 7] = 1;
graf[7, 9] = 1;
graf[9, 7] = 1;
graf[8, 9] = 1;
graf[9, 8] = 1;

int[] path = new int[n];
for (int i = 0; i < n; i++)
{
    path[i] = Int32.MaxValue;
}

for (int start = 0; start < n; start++)
{
    if (path[start] == Int32.MaxValue)
    {
        Queue<int> list = new Queue<int>();
        path[start] = 0;
        list.Enqueue(start);
        while (list.Count > 0)
        {
            int u = list.Dequeue();
            for (int i = 0; i < n; i++)
            {
                if (graf[u, i] > 0)
                {
                    if (path[u] + graf[u, i] < path[i])
                    {
                        path[i] = path[u] + graf[u, i];
                        list.Enqueue(i);
                    }
                }
            }
        }

        for (int i = 0; i < n; i++)
        {
            Console.WriteLine(i + " - " + path[i]);
        }

        Console.WriteLine();
        count++;
    }
}

for (int i = 0; i < n; i++)
{
    Console.WriteLine(i + " - " + path[i]);
}

Console.WriteLine();

Console.WriteLine(count);

3. Связи решают все.

Вам очень надо для решения важного вопроса «выйти» на конкретного человека – Ивана Ивановича через солидных знакомых. У вас есть информация, кто с кем из определенного круга лиц поддерживает достаточно близкие отношения (в том числе и вы). Есть ли у вас шанс получить нужную рекомендацию?

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

Фрагмент кода:

private static bool[] _uses;
private static int[,] _graf;
private static int _n;
private static int _start = 0;
private static int _end = 0;

public static void Main(string[] args)
{
    //Console.Write("Введите N=");
    //_n = Convert.ToInt32(Console.ReadLine());
    _n = 10;

    _graf = new int[_n, _n];

    //Console.Write("Введите M=");
    //int m = Convert.ToInt32(Console.ReadLine());
    int m = 9;

    /*
    for (int i = 0; i < m; i++)
    {
        Console.Write("Номер города, из которого идет дорога: ");
        _start = Convert.ToInt32(Console.ReadLine());
        Console.Write("Номер города, в который идет дорога: ");
        _end = Convert.ToInt32(Console.ReadLine());
        Console.Write("Номер города, в который идет дорога: ");
        int size = Convert.ToInt32(Console.ReadLine());
        _graf[_start, _end] = size;
        _graf[_end, _start] = size;
    }
    */

    _graf[0, 3] = 1;
    _graf[3, 0] = 1;
    _graf[0, 6] = 1;
    _graf[6, 0] = 1;
    _graf[3, 6] = 1;
    _graf[6, 3] = 1;
    _graf[3, 7] = 1;
    _graf[7, 3] = 1;
    _graf[7, 8] = 1;
    _graf[8, 7] = 1;
    _graf[9, 7] = 1;
    _graf[7, 9] = 1;
    _graf[9, 8] = 1;
    _graf[8, 9] = 1;
    _graf[1, 5] = 1;
    _graf[5, 1] = 1;
    _graf[4, 5] = 1;
    _graf[5, 4] = 1;

    //Console.Write("Введите X=");
    //_start = Convert.ToInt32(Console.ReadLine());
    _start = 0;

    //Console.Write("Введите Y=");
    //_end = Convert.ToInt32(Console.ReadLine());
    _end = 9;

    _uses = new bool[_n];

    Dfs(_start);

    if (!_uses[_end])
    {
        Console.WriteLine("Путь не найден!");
    }
}
static void Dfs(int v)
{
    if (_uses[v])  // Если мы здесь уже были, то тут больше делать нечего
    {
        return;
    }
    
    _uses[v] = true;   // Помечаем, что мы здесь были
    
    if (v == _end)   // Проверяем, конец ли
    {
        Console.WriteLine("Путь найден!");
        return;
    }
    
    for (int i = 0; i < _n; i++)  // Для каждого ребра
    {
        if (_graf[v, i] > 0)
        {
             Dfs(i);  // Запускаемся из соседа
        }
    }
}

4. Путь

Пусть надо найти и вывести кратчайший путь из вершины Start в вершину End.

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

Фрагмент кода:

int start = 0;
int end = 0;
int current = 0;
//Console.Write("Введите N=");
//int n = Convert.ToInt32(Console.ReadLine());
int n = 7;

int[,] graf = new int[n, n];

//Console.Write("Введите M=");
//int m = Convert.ToInt32(Console.ReadLine());
int m = 10;

/*
for (int i = 0; i < m; i++)
{
    Console.Write("Номер города, из которого идет дорога: ");
    start = Convert.ToInt32(Console.ReadLine());
    Console.Write("Номер города, в который идет дорога: ");
    end = Convert.ToInt32(Console.ReadLine());
    Console.Write("Номер города, в который идет дорога: ");
    int size = Convert.ToInt32(Console.ReadLine());
    graf[start, end] = size;
    graf[end, start] = size;
}
*/

graf[0, 3] = 25;
graf[3, 0] = 25;
graf[0, 5] = 23;
graf[5, 0] = 23;
graf[0, 6] = 27;
graf[6, 0] = 27;
graf[1, 3] = 22;
graf[3, 1] = 22;
graf[1, 4] = 29;
graf[4, 1] = 29;
graf[2, 4] = 24;
graf[4, 2] = 24;
graf[2, 6] = 23;
graf[6, 2] = 23;
graf[3, 4] = 54;
graf[4, 3] = 54;
graf[4, 5] = 59;
graf[5, 4] = 59;
graf[4, 6] = 49;
graf[6, 4] = 49;

//Console.Write("Введите X=");
//start = Convert.ToInt32(Console.ReadLine());
start = 0;

//Console.Write("Введите Y=");
//end = Convert.ToInt32(Console.ReadLine());
end = 4;

int[] path = new int[n];
for (int i = 0; i < n; i++)
{
    path[i] = Int32.MaxValue;
}

Boolean[] uses = new Boolean[n];
int[] previous = new int[n];

path[start] = 0;
previous[start] = -1;

int usesCount = 0;
while (usesCount < n)
{
    int min = Int32.MaxValue;
    current = 0;
    for (int i = 0; i < n; i++)
    {
        if (!uses[i] && path[i] < min)
        {
            min = path[i];
            current = i;
        }
    }

    for (int i = 0; i < n; i++)
    {
        if (graf[current, i] > 0 && !uses[i])
        {
            if (path[current] + graf[current, i] < path[i])
            {
                path[i] = path[current] + graf[current, i];
                previous[i] = current;
            }
        }
    }

    uses[current] = true;
    usesCount++;
}

for (int i = 0; i < n; i++)
{
    Console.WriteLine(i + " - " + path[i] + " " + previous[i]);
}

if (path[end] != Int32.MaxValue)
{
    current = end;
    LinkedList<int> move = new LinkedList<int>();
    while (current != -1)
    {
        move.AddFirst(current);
        current = previous[current];
    }

    LinkedListNode<int> node;
    node = move.First;
    while (node != null)
    {
        Console.Write(node.Value + " ");
        node = node.Next;
    }

    Console.WriteLine("Длина пути: " + path[end]);
}
else
{
    Console.WriteLine("Нет пути:!");
}

Итоги занятия.

1. Поиск в глубину (DFS).

Сегодня мы продолжим разбирать алгоритмы на графах. Еще один очень распространенный алгоритм – поиск в глубину (DFS). Если объяснять просто, то в поиске в ширину, если помните, у нас из каждой вершины как бы выбегала толпа народа, которая потом снова делилась на большие толпы, а в поиске в глубину бегает только один неутомимый товарищ, который должен успеть оббежать все вершины в поисках нужной и очень быстро.

На первый взгляд кажется, что поиск в ширину BFS гораздо быстрее, ведь толпа может бежать сразу в нескольких направлениях, но на самом деле для большинства задач разница не очень большая, так как перед тем, как отправить толпы в нужных направлениях необходимо «остановиться и подумать» (даже в алгоритме Дейкстры найти вершину с минимальным весом), а в поиске в глубину DFS, практически не думая, сразу бежим в свободную (не посещенную ранее) вершину с минимальным номером.

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

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

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

2. Алгоритм.

Пусть надо найти путь из вершины S в вершину F.
Поиск в глубину (DFS) работает следующим образом:
Если номера вершин S и F совпали – путь найден;
Если из вершины S есть дуга вершину X и вершина X не была посещена ранее – то найти путь из X в F рекурсивно.
Второй шаг выполняется для всех вершин, в которые можно перейти из S.
Если все дуги из S обработаны и ни по одной из них не был найден путь – значит такого пути нет.

Давайте разберем пример на основе задачи про лабиринт.

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

Теперь задача приняла такой вид: есть множество комнат, между некоторыми из них можно перемещаться. Требуется найти путь из комнаты A в комнату B.

В теории графов «комнаты» называются вершинами, «переходы» между ними — ребрами. Комната А — начальная вершина, комната В — конечная.

Граф можно перерисовать в несколько более распространенном в теории графов виде:

Здесь овалы — это вершины (или комнаты), линии — ребра (или переходы между ними). Вершина 1 — начальная, вершина 12 — конечная.

И как же мы будем решать эту задачу?

Решение, которое сразу приходит на ум — помечать каждую вершину при входе в нее, и никогда не ходить в уже помеченные вершины — это и есть обход в глубину:

DFS (рекурсивный алгоритм).

Фрагмент кода:

internal class Program
{
    private static bool[] _uses;
    private static int[,] _graf;
    private static int _n;
    private static int _start = 0;
    private static int _end = 0;
    
    public static void Main(string[] args)
    {
        //Console.Write("Введите N=");
        //_n = Convert.ToInt32(Console.ReadLine());
        _n = 13;

        _graf = new int[_n, _n];

        //Console.Write("Введите M=");
        //int m = Convert.ToInt32(Console.ReadLine());
        int m = 11;

        /*
        for (int i = 0; i < m; i++)
        {
            Console.Write("Номер города, из которого идет дорога: ");
            _start = Convert.ToInt32(Console.ReadLine());
            Console.Write("Номер города, в который идет дорога: ");
            _end = Convert.ToInt32(Console.ReadLine());
            Console.Write("Номер города, в который идет дорога: ");
            int size = Convert.ToInt32(Console.ReadLine());
            _graf[_start, _end] = size;
            _graf[_end, _start] = size;
        }
        */

        _graf[1, 2] = 1;
        _graf[2, 1] = 1;
        _graf[2, 3] = 1;
        _graf[3, 2] = 1;
        _graf[3, 4] = 1;
        _graf[4, 3] = 1;
        _graf[4, 5] = 1;
        _graf[5, 4] = 1;
        _graf[5, 6] = 1;
        _graf[6, 5] = 1;
        _graf[6, 7] = 1;
        _graf[7, 6] = 1;
        _graf[4, 8] = 1;
        _graf[8, 4] = 1;
        _graf[8, 9] = 1;
        _graf[9, 8] = 1;
        _graf[9, 10] = 1;
        _graf[10, 9] = 1;
        _graf[10, 11] = 1;
        _graf[11, 10] = 1;
        _graf[11, 12] = 1;
        _graf[12, 11] = 1;

        //Console.Write("Введите X=");
        //_start = Convert.ToInt32(Console.ReadLine());
        _start = 1;

        //Console.Write("Введите Y=");
        //_end = Convert.ToInt32(Console.ReadLine());
        _end = 12;

        _uses = new bool[_n];

        Dfs(_start);

    }
    static void Dfs(int v)
    {
        if (_uses[v])  // Если мы здесь уже были, то тут больше делать нечего
        {
            return;
        }
        
        _uses[v] = true;   // Помечаем, что мы здесь были
        
        if (v == _end)   // Проверяем, конец ли
        {
            Console.WriteLine("Путь найден!");
            return;
        }
        
        for (int i = 0; i < _n; i++)  // Для каждого ребра
        {
            if (_graf[v, i] > 0)
            {
                 Dfs(i);  // Запускаемся из соседа
            }
        }
    }
}

Сколько ресурсов требуется алгоритму?

Алгоритм просматривает каждое ребро один раз, и выполняет для каждой вершины константное число действий. Обозначая число вершин как V, а ребер — как E, получаем, что время работы — O(V+E). Кстати, такая же сложность и у алгоритма поиска в ширину.

Глубина рекурсии, в которой мы находимся, не превышает общего числа вызовов функции DFS — числа вершин. То есть, объем памяти, необходимый для работы алгоритма, равен O(V).

Нерекурсивный DFS.

Любой рекурсивный алгоритм можно переписать в нерекурсивном виде. Вот код для DFS с использованием стека:

Фрагмент кода:

…
bool[] uses = new bool[n];

Stack<int> s = new Stack<int>();
s.Push(start);
while (s.Count > 0)
{
    int v = s.Pop();
    for (int i = 0; i < n; i++)
    {
        if (graf[v, i] > 0 && !uses[i])
        {
            s.Push(i);
            uses[i] = true;
            if (i == end)
            {
                s.Clear();
                Console.WriteLine("Путь найден!");
                break;
            }
        }
    }
}

Задание: Попробуйте самостоятельно написать алгоритм поиска в глубину с выводом в консоль номеров вершин в порядке их посещения.

Итоги занятия.

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

Алгоритм Дейкстры — алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных.

Пусть требуется найти кратчайшие расстояния от 1-й вершины до всех остальных.

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

Метка самой вершины 1 полагается равной 0, метки остальных вершин – недостижимо большое число (в идеале — бесконечность). Это отражает то, что расстояния от вершины 1 до других вершин пока неизвестны. Все вершины графа помечаются как не посещенные.

Первый шаг.

Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6. Обходим соседей вершины по очереди.

Первый сосед вершины 1 – вершина 2, потому что длина пути до неё минимальна. Длина пути в неё через вершину 1 равна сумме кратчайшего расстояния до вершины 1 (значению её метки) и длины ребра, идущего из 1-й во 2-ю, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2 (10000), поэтому новая метка 2-й вершины равна 7.

Аналогично находим длины пути для всех других соседей (вершины 3 и 6).

Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит. Вершина 1 отмечается как посещенная.

Второй шаг.

Шаг 1 алгоритма повторяется. Снова находим «ближайшую» из не посещённых вершин. Это вершина с минимальной красной меткой - вершина 2 с меткой 7.

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

Вершина 1 уже посещена. Следующий сосед вершины 2 — вершина 3, так как имеет минимальную метку из вершин, отмеченных как не посещённые. Если идти в неё через 2, то длина такого пути будет равна 17 (7 + 10 = 17). Но текущая метка третьей вершины равна 9, а 9 < 17, поэтому метка не меняется.

Ещё один сосед вершины 2 — вершина 4. Если идти в неё через 2-ю, то длина такого пути будет равна 22 (7 + 15 = 22). Поскольку 22<10000, устанавливаем метку вершины 4 равной 22.

Все соседи вершины 2 просмотрены, помечаем её как посещенную.

Третий шаг.

Повторяем шаг алгоритма, выбрав вершину 3. После её «обработки» получим следующие результаты.

Четвертый шаг.

Пятый шаг.

Шестой шаг.

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

Фрагмент кода:

int start = 0;
int end = 0;
Console.Write("Введите N=");
int n = Convert.ToInt32(Console.ReadLine());

int[,] graf = new int[n, n];

Console.Write("Введите M=");
int m = Convert.ToInt32(Console.ReadLine());

for (int i = 0; i < m; i++)
{
    Console.Write("Номер города, из которого идет дорога: ");
    start = Convert.ToInt32(Console.ReadLine());
    Console.Write("Номер города, в который идет дорога: ");
    end = Convert.ToInt32(Console.ReadLine());
    Console.Write("Номер города, в который идет дорога: ");
    int size = Convert.ToInt32(Console.ReadLine());
    graf[start, end] = size;
    graf[end, start] = size;
}

Console.Write("Введите X=");
start = Convert.ToInt32(Console.ReadLine());

Console.Write("Введите Y=");
end = Convert.ToInt32(Console.ReadLine());

int[] path = new int[n];
for (int i = 0; i < n; i++)
{
    path[i] = Int32.MaxValue;
}

Boolean[] uses = new Boolean[n];

path[start] = 0;
int usesCount = 0;
while (usesCount < n)
{
    int min = Int32.MaxValue;
    int current=0;
    for (int i = 0; i < n; i++)
    {
        if (!uses[i] && path[i] < min)
        {
            min = path[i];
            current = i;
        }
    }
    
    for (int i = 0; i < n; i++)
    {
        if (graf[current, i] > 0 && !uses[i])
        {
            if (path[current] + graf[current, i] < path[i])
            {
                path[i] = path[current] + graf[current, i];
            }
        }
    }

    uses[current] = true;
    usesCount++;
}

for (int i = 0; i < n; i++)
{
    Console.WriteLine(i + " - " + path[i]);
}

Console.WriteLine("Ответ: " + path[end]);

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

Задание: Попробуйте самостоятельно реализовать алгоритм Дейкстры для ориентированного графа (каждое ребро задает движение только в одном направлении: от первой указанной вершины до второй).

Итоги занятия.

1. Теория графов. Поиск в ширину (BFS).

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

Условие задачи: Есть N городов. Некоторые из этих городов могут быть попарно связаны друг с другом дорогами. Всего дорог М. Каждая дорога связывает два города и имеет длину (в километрах). Необходимо ответить на вопрос, можно ли проехать по имеющимся дорогам из города X в город Y, и, если да, то какое минимальное количество километров между городами надо проехать.

Исходные данные:
Сначала вводится N – количество городов.
Затем М – количество дорог.
Далее для каждой дороги вводится номер города, из которого она идет, номер города, в который она идет, и расстояние в километрах. Города нумеруются, начиная с 0.
Потом вводится Х – номер города, из которого планируется начать движение.
И Y – номер города, в котором планируется закончить движение.

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

Мы будем использовать один из основных алгоритмов на графах - поиск в ширину.

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

2. Поиск в ширину (BFS). Описание алгоритма.

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

На вход алгоритма подаётся заданный граф (невзвешенный), и номер стартовой вершины Х. Граф может быть как ориентированным, так и неориентированным, для алгоритма это не важно.

Сам алгоритм можно понимать, как процесс "поджигания" графа: на нулевом шаге поджигаем только вершину Х. На каждом следующем шаге огонь с каждой уже горящей вершины перекидывается на всех её соседей; то есть за одну итерацию алгоритма происходит расширение "кольца огня" в ширину на единицу (отсюда и название алгоритма).

Более строго это можно представить следующим образом. Создадим очередь, в которую будут помещаться горящие вершины, а также заведём булевский массив used[], в котором для каждой вершины будем отмечать, горит она уже или нет (или иными словами, была ли она посещена).

Изначально в очередь помещается только вершина Х, и used[Х]=true, а для всех остальных вершин used[i]=false. Затем алгоритм представляет собой цикл: пока очередь не пуста, достать из её головы одну вершину, просмотреть все рёбра, исходящие из этой вершины, и если какие-то из просмотренных вершин ещё не горят, то поджечь их и поместить в конец очереди.

В итоге, когда очередь опустеет, обход в ширину обойдёт все достижимые из Х вершины, причём до каждой дойдёт кратчайшим путём.

Для взвешенного графа алгоритм немного усложняется. Вместо булевского массива used[] заведем массив длин путей path[], элементам которого изначально присвоим бесконечность. Длине пути в исходную вершину присвоим 0: path[Х]=0. Для расчета кратчайших путей придется постоянно проверять, можем ли мы попасть в очередную вершину за более короткий путь и, если да, обновлять значение минимального пути и добавлять эту вершину в очередь еще раз, чтобы заново пересчитать минимальные пути.

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

Приступим к реализации.

Граф будем хранить с помощью матрицы смежности (у нас достаточно много ребер).

Фрагмент кода:

int start = 0;
int end = 0;
Console.Write("Введите N=");
int n = Convert.ToInt32(Console.ReadLine());

int[,] graf = new int[n, n];

Console.Write("Введите M=");
int m = Convert.ToInt32(Console.ReadLine());

for (int i = 0; i < m; i++)
{
    Console.Write("Номер города, из которого идет дорога: ");
    start = Convert.ToInt32(Console.ReadLine());
    Console.Write("Номер города, в который идет дорога: ");
    end = Convert.ToInt32(Console.ReadLine());
    Console.Write("Длина дороги: ");
    int size = Convert.ToInt32(Console.ReadLine());
    graf[start, end] = size;
    graf[end, start] = size;
}

Console.Write("Введите X=");
start = Convert.ToInt32(Console.ReadLine());

Console.Write("Введите Y=");
end = Convert.ToInt32(Console.ReadLine());

int[] path = new int[n];
for (int i = 0; i < n; i++)
{
    path[i] = Int32.MaxValue;
}

Queue<int> list = new Queue<int>();
path[start] = 0;
list.Enqueue(start);
while (list.Count > 0)
{
    int u = list.Dequeue();
    for (int i = 0; i < n; i++)
    {
        if (graf[u, i] > 0)
        {
            if (path[u] + graf[u, i] < path[i])
            {
                path[i] = path[u] + graf[u, i];
                list.Enqueue(i);
            }
        }
    }
}

if (path[end] != Int32.MaxValue)
{
    Console.WriteLine("Ответ: "+path[end]); 
}
else
{
    Console.WriteLine("Дороги нет!"); 
}

Задание*: Попробуйте самостоятельно вывести в консоль кратчайший маршрут движения от города Х в город Y (список номеров городов, через которые надо проехать).

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

Итоги занятия.

1. Теория графов.

Сегодня мы начинаем говорить о теории графов. Это не структура данных и не метод решения задача. Графы – это способ представления и обработки данных в виде не просто множества объектов заданного класса, но и с учетом связей между ними.

Теория графов - один из обширнейших разделов дискретной математики, широко применяется в решении экономических и управленческих задач, в программировании, химии, конструировании и изучении электрических цепей, коммуникации, психологии, социологии, лингвистике, других областях знаний. Теория графов систематически и последовательно изучает свойства графов, о которых можно сказать, что они состоят из множеств точек и множеств линий, отображающих связи между этими точками. Основателем теории графов считается Леонард Эйлер (1707-1882), решивший в 1736 году известную в то время задачу о кёнигсбергских мостах.

Графы строят для того, чтобы отобразить отношения на множествах. Пусть, например, множество A = {a1, a2, ... an} - множество людей, а каждый элемент будет отображён в виде точки. Множество B = {b1, b2, ... bm} - множество связок (прямых, дуг, отрезков - пока не важно). На множестве A задано отношение знакомства между людьми из этого множества. Строим граф из точек и связок. Связки будут связывать пары людей, знакомых между собой. Естественно, число знакомых у одних людей может отличаться от числа знакомых у других людей, а некоторые вполне могут и не быть ни с кем знакомы (такие элементы будут точками, не соединёнными ни с одной другой). Вот и получился граф!

То, что мы сначала назвали "точками", следует называть вершинами графа, а то, что называли "связками" - рёбрами графа.

Теория графов не учитывает конкретную природу множеств A и B. Существует большое количество самых разных конкретных задач, при решении которых можно временно забыть о специфическом содержании множеств и их элементов. Эта специфика никак не сказывается на ходе решения задачи, независимо от её трудности! Например, при решении вопроса о том, можно ли из точки a добраться до точки b, двигаясь только по соединяющим точки линиям, неважно, имеем ли мы дело с людьми, городами, числами и т.д. Но, когда задача решена, мы получаем решение, верное для любого содержания, которое было смоделировано в виде графа. Не удивительно поэтому, что теория графов - один из самых востребованных инструментов при создании искусственного интеллекта: ведь искусственный интеллект может обсудить с собеседником и вопросы любви, и вопросы музыки или спорта, и вопросы решения различных задач, причем делает это без всякого перехода (переключения), без которого в подобных случаях не обойтись человеку.

А теперь строгие математические определения графа.

2. Основные понятия теории графов.

Графом называется система объектов произвольной природы (вершин) и связок (рёбер), соединяющих некоторые пары этих объектов.

Пусть V – (непустое) множество вершин, элементы v∈V – вершины. Граф G = G(V) с множеством вершин V есть некоторое семейство пар вида: e = (a, b), где a,b∈V, указывающих, какие вершины остаются соединёнными. Каждая пара e = (a, b) - ребро графа. Множество U - множество рёбер e графа. Вершины a и b – концевые точки ребра e.

Графы как структура данных. Широким применением теории графов в компьютерных науках и информационных технологиях обусловлено добавлением к вышеизложенным определениям понятия графа как структуры данных. В компьютерных науках и информационных технологиях граф определяется как нелинейная структура данных. Что же тогда - линейная структура данных и чем от них отличаются графы? Линейные структуры данных характеризуются тем, что связывают элементы отношениями типа "простого соседства". Линейными структурами данных являются, например, массивы, таблицы, списки, очереди, стеки, строки. В противоположность им нелинейные структуры данных - такие, в которых элементы располагаются на различных уровнях иерархии и подразделяются на три вида: исходные, порождённые и подобные. Итак, граф - нелинейная структура данных.

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

Ориентированные и неориентированные графы.

Графы, в которых все рёбра являются звеньями (порядок двух концов ребра графа не существенен), называются неориентированными.

Графы, в которых все рёбра являются дугами (порядок двух концов ребра графа существенен), называются ориентированными графами.

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

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

Граф заданного типа называют полным, если он содержит все возможные для этого типа рёбра (при неизменном множестве вершин). Так, в полном обыкновенном графе каждая пара различных вершин соединена ровно одним звеном.

Деревом называется связный граф без циклов. Любые две вершины дерева соединены лишь одним маршрутом:

Смежность вершин графа - это когда две вершины графа соединены ребром.

Зададимся вопросом: можно ли поместить слона в компьютер? Ответ: можно, если слона смоделировать в виде графа, в котором вершинами являются части его тела, а рёбра соединяют те части тела, которые соединены в слоне как биологическом объекте. При этом получившийся граф должен быть представлен в памяти компьютера в понятном компьютеру виде.

3. Способы представления графа в памяти компьютера.

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

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

Матрицы смежности

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

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

Списки инцидентности

Графы значительного объёма целесообразно хранить в памяти компьютера в форме списков инцидентности.

Список инцидентности одной вершины графа включает номера вершин, смежных с ней.

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

Преимущества и недостатки каждого способа.

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

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

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

Списки инцидентности целесообразнее использовать, когда:

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

Итоги занятия.

1. Хэш-таблицы.

Продолжаем говорить о структурах данных.

Сегодня мы поговорим о структуре, которая позволяет найти элемент за О(1). Напоминаем, что и в обычном массиве, и в динамическом списке эта операция осуществляется за О(n).

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

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

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

2. Коллизии.

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

Коллизия хэш-функции возникает тогда, когда двум значениям соответствует один ключ-значение. Коллизии существуют для большинства хэш-функций, но для «хороших» хэш-функций частота их возникновения близка к минимуму.

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

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

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

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

Технология сцепления элементов (метод цепочек) состоит в том, что элементы множества, которым соответствует одно и то же хэш-значение, связываются в цепочку-список. В позиции номер i хранится указатель на голову списка тех элементов, у которых хэш-значение ключа равно i; если таких элементов в множестве нет, в позиции i записан NULL.

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

3. Класс Dictionary.

В C# есть несколько классов для реализации хэш-таблиц. Рассмотрим один из самых популярных.

Словарь (dictionary) — это обобщенная версия Hashtable. Главное свойство dictionary— быстрый поиск с помощью ключей. Можно также добавлять и удалять элементы, наподобие того как это делается в структуре List, но без расходов производительности, связанных с необходимостью смещения последующих элементов в памяти.

В классе Dictionary<TKey, TValue> опреден ряд методов:

• Add() - добавляет в словарь пару "ключ-значение", определяемую параметрами key и value. Если ключ key уже находится в словаре, то его значение не изменяется, и генерируется исключение ArgumentException.
• ContainsKey() - возвращает логическое значение true, если вызывающий словарь содержит объект key в качестве ключа; а иначе — логическое значение false.
• ContainsValue() - возвращает логическое значение true, если вызывающий словарь содержит значение value; в противном случае — логическое значение false.
• Remove() - удаляет ключ key из словаря. При удачном исходе операции возвращается логическое значение true, а если ключ key отсутствует в словаре — логическое значение false.

Кроме того, класс Dictionary<TKey, TValue> определяет собственные свойства, помимо тех, что уже объявлены в интерфейсах, которые в нем реализуются. Эти свойства приведены ниже:

• Keys - получает коллекцию ключей.
• Values - получает коллекцию значений.

4. Рассмотрим на примере использование словарей.

Dictionary<int, string> countries = new Dictionary<int, string>(5);
countries.Add(1, "Russia");
countries.Add(3, "Great Britain");
countries.Add(2, "USA");
countries.Add(4, "France");
countries.Add(5, "China");

foreach (KeyValuePair<int, string> keyValue in countries)
{
    Console.WriteLine(keyValue.Key + " - " + keyValue.Value);
}

// получение элемента по ключу
string country = countries[4];
Console.WriteLine(country);

// изменение объекта
countries[4] = "Spain";

// удаление по ключу
countries.Remove(2);

Console.WriteLine();
foreach (KeyValuePair<int, string> keyValue in countries)
{
    Console.WriteLine(keyValue.Key + " - " + keyValue.Value);
}

Класс словарей также, как и другие коллекции, предоставляет методы Add и Remove для добавления и удаления элементов. Только в случае словарей в метод Add передаются два параметра: ключ и значение. А метод Remove удаляет не по индексу, а по ключу.

Так как в нашем примере ключами является объекты типа int, а значениями - объекты типа string, то словарь в нашем случае будет хранить объекты KeyValuePair<int, string>. В цикле foreach мы их можем получить и извлечь из них ключ и значение.

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

class Localization
{
    public Localization(string russian, string german)
    {
        Russian = russian;
        German = german;
    }
    
    public string Russian { get; set; }
    public string German { get; set; }
}

public static void Main(string[] args)
{
    Dictionary<string, Localization> words = new Dictionary<string, Localization>();
    words.Add("book", new Localization("Книга", "Buch"));
    words.Add("pen", new Localization("Ручка", "Griff"));
    words.Add("paper", new Localization("Бумага", "Papier"));

    foreach (KeyValuePair<string, Localization> keyValue in words)
    {
        // keyValue.Value представляет класс Localization
        Console.WriteLine(keyValue.Key + " - " + keyValue.Value.Russian);
    }

    // перебор ключей
    foreach (string key in words.Keys)
    {
        Console.WriteLine(key);
    }

    // перебор по значениям
    foreach (Localization word in words.Values)
    {
        Console.WriteLine(word.Russian);
    }
}

Здесь в качестве ключей выступают объекты типа string, а значениями – объекты Localization. Используя свойство Keys, мы можем получить ключи словаря, а свойство Values соответственно хранит все значения в словаре.

Для добавления необязательно применять метод Add(), можно использовать сокращенный вариант:

Dictionary<string, Localization > words = new Dictionary<string, Localization>();
Dictionary.Add("eraser", new Localization ("Стерка", "Radiergummi"));
Dictionary["eraser"] = new Localization ("Ластик", "Radiergummi");

Несмотря на то, что изначально в словаре нет ключа "eraser" и соответствующего ему элемента, то он все равно будет установлен. Если же он есть, то элемент по ключу "eraser" будет заменен на новый объект new Localization ("Ластик", "Radiergummi").

Инициализация словарей.

Инициализировать словари можно следующим образом:

Первый вариант:

Dictionary<string, string> countries = new Dictionary<string, string>
{
     {"Франция", "Париж"},
     {"Германия", "Берлин"},
     {"Великобритания", "Лондон"}
};

foreach(var pair in countries)
     Console.WriteLine("{0} - {1}", pair.Key, pair.Value);

Второй вариант:

Dictionary<string, string> countries = new Dictionary<string, string>
{
     ["Франция"]= "Париж",
     ["Германия"]= "Берлин",
     ["Великобритания"]= "Лондон"
};

Итоги занятия.