Skip to content

Instantly share code, notes, and snippets.

@sampletext32

sampletext32/Structs.md

Last active January 23, 2021 21:00
Show Gist options
  • Save sampletext32/06d0e3e678970ef49bd4ec93a54ba647 to your computer and use it in GitHub Desktop.
Save sampletext32/06d0e3e678970ef49bd4ec93a54ba647 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
Structs.md
  1. Использование памяти переменными
  2. Структуры данных
  3. Алгоритмическая сложность
  4. Динамические массивы в C#
  5. Динамические массивы в Java
  6. Преимущества и недостатки динамического массива
  7. Узлы
  8. Стек. Преимущества и недостатки.
  9. Стек в C#
  10. Стек в Java
  11. Очередь. Преимущества и недостатки.
  12. Очередь в C#
  13. Очередь в Java
  14. Связанный список Преимущества и недостатки.
  15. Связанный список в C#
  16. Связанный список в Java
  17. Итератор
  18. Компаратор
  19. Паттерн стратегия
  20. Деревья
  21. Алгоритмы обходов древовидных структур, DFS.
  22. Алгоритмы обходов древовидных структур, BFS.
  23. Двоичное дерево поиска
  24. Куча
  25. Очередь с приоритетами

01. Использование памяти переменными

  • Компьютерная память - это любое физическое устройство, способное хранить информацию временно, как ОЗУ, или постоянно, как ПЗУ. Запоминающие устройства построены на интегральных схемах и используются операционными системами, программным и аппаратным обеспечением.
  • Термин «память», означающий как правило «постоянное запоминающее устройство» или «основную память», часто ассоциируется с адресуемой полупроводниковой памятью.

  • С точки зрения информатики, «память»:

    • непрерывная, пронумерованная (адресованная) последовательность байтов

    • хранилище для переменных и функций, созданных в программах

      • с быстрым произвольным доступом - одинаково быстрый доступ к любому адресу
      • адреса пронумерованы в шестнадцатеричном формате с префиксом 0x
      Address 0x0 0x1 0x2 ... 0x6afe4c ...
      Byte(binary) 00001101 00101010 01000101 ... 00000011 ...

  • Примитивный тип данных занимает последовательность байтов

    • byte - это 1 байт, 1 адрес: 
      byte number = 42; //предположим, что число
                  //находится по адресу 0x6afe4c
      Address ... 0x6afe4b 0x6afe4c ... ... ...
      Byte(binary) ... ... 00101010 ... ... ...

  • Остальные типы (кроме boolean) и массивы представляют собой последовательность байтов

    • Например, 4-байтовый int 
      int year = 2020; // предположим, что год находится по адресу 0x6afe4c
      Address ... 0x6afe4b 0x6afe4c 0x6afe4d 0x6afe4e 0x6afe4f ...
      Byte(binary) ... ... 11100100 00000111 00000000 00000000 ...

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

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

  • Хранение элементов требует потребления памяти:

    Data Structure Size
    int = 4 bytes
    float = 4 bytes
    Long = 8 bytes
    Int[] ~= (Array length) * 4 bytes
    List ~= (List size) * 8 bytes
    Dictionary<int, int[]> ~= (Dictionary size) * Entry bytes

Абстрактные структуры данных:

  • Абстрактная структура данных – абстракция, на основе которой объекты будут представляться как математические объекты вместе с набором операций, которые будут выполняться над ними без самой реализации 
    public interface IList<T> 
{ 
    void Add(T item); 
    int Count { get; } 
    bool Remove(T item); 
    void Clear(); 
}

Реализация структур данных в ЯП:

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

03. Алгоритмическая сложность

  • Алгоритмическая сложность – грубая оценка количества выполняемых шагов, в зависимости от размера входных данных

  • Измеряется с помощью асимптотической нотации: image

  • Частные случаи:

    Complexity Notation Description
    Constant O(1) n = 1 000 -> 1-2 operations
    Logarithmic O(log n) n = 1 000 -> 10 operations
    Linear O(n) n = 1 000 -> 1 000 operations
    Linearithmic O(n * log n) n = 1 000 -> 10 000 operations
    Quadratic O(n^2) n = 1 000 -> 1 000 000 operations
    Cubic O(n^3) n = 1 000 -> 1 000 000 000 operations
    Exponential O(n^n) n = 10 -> 10 000 000 000 operations

  • Сложность и скорость работы программы:

    Complexity 10 20 50 100 1000 10000 100000
    O(1) < 1 s < 1 s < 1 s < 1 s < 1 s < 1 s < 1 s
    O(log n) < 1 s < 1 s < 1 s < 1 s < 1 s < 1 s < 1 s
    O(n) < 1 s < 1 s < 1 s < 1 s < 1 s < 1 s < 1 s
    O(n*log n) < 1 s < 1 s < 1 s < 1 s < 1 s < 1 s < 1 s
    O(n^2) < 1 s < 1 s < 1 s < 1 s < 1 s 2 s 3-4 min
    O(n^3) < 1 s < 1 s < 1 s < 1 s 20 s 5 hours 231 days
    O(2^n) < 1 s < 1 s 260 days hangs hangs hangs hangs
    O(n!) < 1 s hangs hangs hangs hangs hangs hangs
    O(n^n) 3-4 min hangs hangs hangs hangs hangs hangs

Требование к памяти:

  • При оценке алгоритма стоит учитывать и потребление памяти, например:
    • Хранение элементов в матрице размером N на N
    • Заполнение матрицы - время выполнения O(n^2)
    • Получить элемент по индексу - время выполнения O(1)
    • Потребность в памяти O(n^2)

04. Динамические массивы в C#

  • List – реализация структуры данных «список»
    • Внутри – массив, который может динамически увеличиваться и уменьшаться при добавлении и удалении элементов
  • Хранит элементы внутри массива, если примитивный тип – значениями, если ссылочный – ссылками
  • Упрощенный пример: 
    public class List<T> : IAbstractList<T>
{
    private T[] items;
}
  • Поддерживаемые операции и их сложность:
    • Count, Get и Set через индексы - O(1)
    • Add(T item)
      • Амортизированная стоимость
      • Добавление n элементов требует O(n) времени
    • Insert(int index, T item)
      • Вставляет элемент по заданному индексу
    • Contains(T item)
      • Возвращает bool, присутствует ли элемент
    • IndexOf(T item)
      • Возвращает индекс элемента или -1
    • Remove(T item)
      • Удаляет элемент
    • RemoveAt(int index)
      • Удаляет элемент по индексу
    • ToArray()
      • Возвращает элементы как массив
    • Count
      • Возвращает количество элементов
    • Все выполняются за линейное время O(n)

05. Динамические массивы в Java

  • ArrayList – реализация структуры данных «список»
    • Внутри – массив, который может динамически увеличиваться и уменьшаться при добавлении и удалении элементов
  • Хранит элементы внутри массива, если примитивный тип – значениями, если ссылочный – ссылками
  • Упрощенный пример: 
    public class ArrayList<E> implements AbstractList<E> { 
    private Object[] elements; 
}
  • Поддерживаемые операции и их сложность:
    • size(), isEmpty(), get(), set() - O(1)
    • add()
      • Амортизированная стоимость
      • Добавление n элементов требует O(n) времени
    • add(int index, E element), contains(), indexOf(), remove(int index)
    • Все выполняются за линейное время O(n)

06. Преимущества и недостатки динамического массива

  • Амортизированная стоимость добавления

    • Если изначально размер массива равен 4, в него можно добавить 4 элемента и каждое добавление будет занимать константное время. Добавление же пятого элемента потребует создания нового массива размера 8, в который будут перенесены элементы старого, а затем добавлен новый элемент. Следующие три операции push при этом снова будут занимать константное время, после чего массив снова придётся удвоить.
    • В общем случае, если было произведено n+1 операций push в массив размера n, все эти операции будут исполнены за константное время, кроме последней, которая займёт O(n).
    • Но если рассмотреть среднее время добавления всех сложность составит O(1)

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

  • Каждый элемент после точки вставки должен быть скопирован на соседнее место во внутреннем массиве, и после завершения копирования пустота заполняется новым объектом

  • Поскольку необходимо перемещать каждый объект после точки вставки, то наилучшим случаем будет добавление элемента к концу. При этом нужно перемещать ноль элементов (однако внутренний массив всё равно требует расширения). Динамический массив лучше всего работает при добавлении элемента в конец, а не в середину.

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

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

07. Узлы

  • Узлы – концепция структур данных построенных на связанных списках.
    • Является инструментом реализации множества структур данных
  • Внутри себя узел хранит сам элемент и указатель на следующий узел
    • Также можно хранить и другие данные – например указатель на предыдущий узел
    public class Node<T> 
{ 
    public T Element { get; set; } // Обязательно 
    public Node<T> Next { get; set; } // Обязательно 
    public Node<T> Previous { get; set; } // Опционально 
}
  • В языках программирования есть так называемые связанные списки и другие структуры данных, которые используют узлы и могут быть реализованы примерно так: 
    public class LinkedList<T> : IAbstractList<T> 
{ 
    private Node<T> head; 
}

08. Стек. Преимущества и недостатки.

  • Стек – реализация структуры данных «LIFO» (Last In First Out) - последний пришел, первый ушел
  • Может быть реализован как через массив так и через связанный список
  • Достоинства:
    • Добавление элемента всегда работает за одно и тоже время(т.к. нет необходимости компировать весь стек, если вдруг кончится память),
  • Недостатки:
    • Расходуется немного больше памяти на узлы
    • Возможность перемещаться по стеку лишь в одном направлении, что затруднит поиск необходимого элемента, элементы списка могут располагаться в памяти разреженно, что оказывает негативный эффект на кэширование процессора.
  • Стек
    • В программах отмена последних действий (Undo)
    • История браузера
  • Оценка математических выражений
  • Реализация вызовов функций (методов)
  • Обход древовидных структур (алгоритм DFS)

09. Стек в C#

Стек в C# реализован как массив

  • Например: 
    public class Stack<T> : IAbstractStack<T>
{
    private Node<T> top;
    private int size;
}
    public void Push(T element)
{
    Node<T> newNode = new Node<T>(element);
    newNode.Next = top;
    top = newNode;
    this.size++;
}
    public T Pop()
{
    this.EnsureNonEmpty();
    T element = this.top.Element;
    Node<T> temp = this.top.Next;
    this.top.Next = null;
    this.top = temp;
    this.size--;
    return element;
}
  • Поддерживаемые операции:
    • Count, Push(T item), Pop(), Peek() – O(1)
    • Все остальные операции – линейное время O(n)
      • CopyTo(T[] array, int arrayIndex)
      • Contains(T item)

10. Стек в Java

Стек в Java реализован как массив (вектор)

В Java в основном существует 5 методов класса стека.

  • empty() - Проверяет, пуст ли стек
  • push() - Ставит элемент в верх стека
  • pop() - Удаляет объект из стека
  • peek() - Рассматривает объект стека, не удаляя его
  • search() - Поиск элемента для получения его индекса

11. Очередь. Преимущества и недостатки.

  • Очередь – реализация структуры данных «FIFO» - первый пришел, первый ушел

  • Может быть реализован как через массив так и через связанный список

  • Очередь

    • Планирование процессов операционной системы
    • Совместное использование ресурсов
    • Очередь документов принтера
    • Обход древовидных структур (алгоритм BFS)

12. Очередь в C#

Queue в C# реализован как массив

  • Пример:

    public class Queue<T> : IAbstractQueue<T>
{
    private Node<E> head;
    private int size;

    public Queue()
    {
    }
}
    public void Enqueue(T element)
{
    Node<T> newNode = new Node<T>(element);
    if (this.head == null)
    {
        this.head = newNode;
    }
    else
    {
        Node<T> current = this.head;
        while (current.next != null)
        {
            current = current.next;
        }
        current.next = newNode;
    }
    this.size++;
}

  • Поддерживаемые операции:

    • Count, Dequeue(), Peek() – O(1)
    • Enqueue(T item):
      • Если мы сохраним ссылку на этот узел – O(1)
      • Если нам придется «гоняться» за указателями на этот узел – O(n)

  • Все остальные операции – линейное время O(n)

    • Contains(T item), CopyTo(T[] array, int arrayIndex)

13. Очередь в Java

ArrayDequeue в Java реализован как массив

Обобщенный интерфейс Queue<E> расширяет базовый интерфейс Collection и определяет поведение класса в качестве однонаправленной очереди. Свою функциональность он раскрывает через следующие методы:

  • E element(): возвращает, но не удаляет, элемент из начала очереди. Если очередь пуста, генерирует исключение NoSuchElementException
  • boolean offer(E obj): добавляет элемент obj в конец очереди. Если элемент удачно добавлен, возвращает true, иначе - false
  • E peek(): возвращает без удаления элемент из начала очереди. Если очередь пуста, возвращает значение null
  • E poll(): возвращает с удалением элемент из начала очереди. Если очередь пуста, возвращает значение null
  • E remove(): возвращает с удалением элемент из начала очереди. Если очередь пуста, генерирует исключение NoSuchElementException

Интерфейс Deque появился в Java 6. Он расширяет Queue и описывает поведение двунаправленной очереди. Двунаправленная очередь может функционировать как стандартная очередь FIFO либо как стек LIFO.

Методы интерфейса Deque:

  • void addFirst(Е obj) - добавляет obj в голову двунаправленной очереди. Возбуждает исключение IllegalStateException, если в очереди ограниченной емкости нет места.
  • void addLast(Е obj) - добавляет obj в хвост двунаправленной очереди. Возбуждает исключение IllegalStateException, если в очереди ограниченной емкости нет места.
  • Е getFirst() - возвращает первый элемент двунаправленной очереди. Объект из очереди не удаляется. В случае пустой двунаправленной очереди возбуждает исключение NoSuchElementException.
  • Е getLast() - возвращает последний элемент двунаправленной очереди. Объект из очереди не удаляется. В случае пустой двунаправленной очереди возбуждает исключения NoSuchElementException.
  • boolean offerFirst(Е obj) - пытается добавить obj в голову двунаправленной очереди. Возвращает true, если obj добавлен, и false в противном случае. Таким образом, этот метод возвращает false при попытке добавить obj в полную двунаправленную очередь ограниченной емкости.
  • boolean offerLast(E obj) - пытается добавить obj в хвост двунаправленной очереди. Возвращает true, если obj добавлен, и false в против ном случае.
  • Е рор() - возвращает элемент, находящийся в голове двунаправленной очереди, одновременно удаляя его из очереди. Возбуждает исключение NoSuchElementException, если очередь пуста.
  • void push(Е obj) - добавляет элемент в голову двунаправленной очереди. Если в очереди фиксированного объема нет места, возбуждает исключение IllegalStateException.
  • Е peekFirst() - возвращает элемент, находящийся в голове двунаправленной очереди. Возвращает null, если очередь пуста. Объект из очереди не удаляется.
  • Е peekLast() - возвращает элемент, находящийся в хвосте двунаправленной очереди. Возвращает null, если очередь пуста. Объект из очереди не удаляется.
  • Е pollFirst() - возвращает элемент, находящийся в голове двунаправленной очереди, одновременно удаляя его из очереди. Возвращает null, если очередь пуста.
  • Е pollLast() - возвращает элемент, находящийся в хвосте двунаправленной очереди, одновременно удаляя его из очереди. Возвращает null, если очередь пуста.
  • Е removeLast() - возвращает элемент, находящийся в конце двунаправленной очереди, удаляя его в процессе. Возбуждает исключение NoSuchElementException, если очередь пуста.
  • Е removeFirst() - возвращает элемент, находящийся в голове двунаправленной очереди, одновременно удаляя его из очереди. Возбуждает исключение NoSuchElementException, если очередь пуста.
  • boolean removeLastOccurrence(Object obj) - удаляет последнее вхождение obj из двунаправленной очереди. Возвращает true в случае успеха и false если очередь не содержала obj.
  • boolean removeFirstOccurrence(Object obj) - удаляет первое вхождение obj из двунаправленной очереди. Возвращает true в случае успеха и false, если очередь не содержала obj.

14. Связанный список Преимущества и недостатки.

  • Связанный список - структура данных, где каждый элемент хранится в отдельном объекте – узле
  • Элементы не хранятся последовательно в памяти
  • Точкой входа/начала является ссылка на голову списка

15. Связанный список в C#

LinkedList в C# реализован как связанный список

  • Пример:

    public class SinglyLinkedList<T> : IAbstractLinkedList<T>
{
    private Node<E> head;
    private int size;
}
    public void AddLast(T element) {
    Node<T> newNode = new Node<T>(element);
    if (this.head == null)
        this.head = newNode;
    else
    {
        Node<E> current = this.head;
        while (current.next != null)
            current = current.next;
        current.next = newNode;
    }
    this.size++;
}
    public void AddFirst(T element)
{
    Node<T> newNode = new Node<T>(element);
    if (this.head != null)
    {
        newNode.next = this.head;
    }
    this.head = newNode;
    this.size++;
}

  • Поддерживаемые операции:

    • AddFirst(T item), RemoveFirst(), GetFirst(), Count – O(1)
    • А вот операции с последним элементом:
      • AddLast(), RemoveLast(), GetLast()
      • Зависит от того, храним (хитрим ☺) ли мы ссылку на последний узел или нет, может быть постоянным – O(1) или линейным – O(n)

  • Операции, проходящие по списку, будут выполняться за линейное время O(n)

16. Связанный список в Java

LinkedList в Java реализован как связанный список

  • Пример: 
    public class Node {
  // содержимое текущего элемента списка
  private int element;

  // указатель на следующий элемент списка
  private Node next;

  // вывод содержимого текущего элемента
  public int getElement(){
    return element;
  }

  // установка содержимого для текущего элемента списка
  public void setElement(int e){
    element = e;
  }

  // получение указателя на следующий элемент списка
  public Node getNext() {
    return next;
  }

  // установка следующего элемента списка
  public void setNext(Node n) {
    next = n;
  }
}

17. Итератор

IEnumerable<T>

  • Один из основных интерфейсов в .NET, предоставляющий простую итерацию по коллекции
  • Содержит один метод GetEnumerator(), возвращающий IEnumerator<T>
  • Класс, реализующий IEnumerable<T>, может быть использован в цикле foreach, который использует итератор для обхода коллекции
public interface IEnumerable<T> : IEnumerable 
{ 
    IEnumerator<T> GetEnumerator(); 
} 
public interface IEnumerable 
{ 
    IEnumerator GetEnumerator(); 
}

IEnumerator<T>

  • Обеспечивает последовательную итерацию (только вперед) по коллекции любого типа
  • Методы:
    • MoveNext() – перемещает «перечислитель» (enumerator) к следующему элементу коллекции.
    • Reset() – устанавливает «перечислитель» в исходное положение
  • Свойства
    • Current – возвращает элемент в коллекции в текущей позиции «перечислителя»
public interface IEnumerator<T> : IEnumerator 
{ 
    bool MoveNext(); 
    void Reset(); 
    T Current { get; } 
} 
public interface IEnumerator 
{ 
    bool MoveNext(); 
    void Reset(); 
    object Current { get; } 
}

yield return

  • Указывает, что элемент, в котором он появляется, является итератором
  • Упрощает реализацию IEnumerator
  • Возвращает один элемент в каждом цикле цикла
private readonly List<Book> books; 

public IEnumerator<Book> GetEnumerator() 
{ 
    for (int i = 0; i < this.books.Count; i++) 
        yield return this.books[i]; 
}

params

  • Принимает переменное число аргументов
  • В объявлении метода допускается только одно ключевое слово params
  • Всегда должен быть последним
PrintNames("Ivan", "Petr", "Vasya"); 

public void PrintNames(params string[] names) 
{ 
    foreach(var name in names)
        Console.WriteLine(name); 
}

18. Компаратор

IComparable<T>

  • Читается как «я сравнимый»
  • Предоставляет метод сравнения двух объектов определенного типа - CompareTo()
  • Задает порядок сортировки по умолчанию для конкретного типа объектов
class Point : IComparable<Point> 
{ 
    public int X { get; set; } 
    public int Y { get; set; } 
    
    public int CompareTo(Point otherPoint) 
    { 
        if (this.X != otherPoint.X) 
            return (this.X - otherPoint.X); 
        if (this.Y != otherPoint.Y) 
            return (this.Y – otherPoint.Y); 
        return 0; 
    } 
}

IComparer<T>

  • Читается как «я-компаратор» или «я сравниваю»
  • Предоставляет возможность настройки порядка сортировки коллекции
  • Предоставляет метод, который реализует конкретный тип для сравнения двух объектов данного типа
class Cat 
{ 
    public string Name { get; set; } 
}

class CatComparer : IComparer<Cat> 
{ 
    public int Compare(Cat x, Cat y) 
    { 
        return x.Name.CompareTo(y.Name); 
    } 
} 

IComparer<Cat> comparer = new CatComparer(); 
var catsByName = new SortedSet(comparer);

19. Паттерн стратегия

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

Структура

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

Применимость

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

Преимущества и недостатки

  • +:
    • Горячая замена алгоритмов на лету.
    • Изолирует код и данные алгоритмов от остальных классов.
    • Уход от наследования к делегированию.
    • Реализует принцип открытости/закрытости.
  • -:
    • Усложняет программу за счет дополнительных классов.
    • Клиент должен знать, в чем состоит разница между стратегиями, чтобы выбрать подходящую.

20. Деревья

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

Зачем нужны деревья?

  • Эффективные алгоритмы поиска
  • Деревья хранят данные не линейным способом, а упорядочивают их иерархически

Дерево как абстрактный тип данных

  • Дерево – широко используемый абстрактный тип данных, который имитирует иерархическую древовидную структуру, элементы которой имеют следующие свойства:
    • Значение элемента
    • Родитель элемента – null или другая ссылка на элемент дерева
    • Дочерние элементы – набор деревьев

21. Алгоритмы обходов древовидных структур, DFS.

  • Сначала рекурсивно посещаем всех потомков данного узла, а затем сам узел (использует стек)
  • Псевдокод алгоритма DFS: 
    DFS (node) { 
    foreach child c of node 
    {
        DFS(c); 
        print node;
    } 
}

22. Алгоритмы обходов древовидных структур, BFS.

  • Поиск в ширину (BFS) - первыми посещаем все узлы потомки, затем потомки потомков и т. д. (использует очередь)
  • Псевдокод алгоритма BFS:
BFS (node) { 
    queue <- node 
    while queue not empty 
    {
        v <- queue 
        print v 
    }
    foreach child c of v 
        queue <- c 
}

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

  • Абстрактный тип данных в виде дерева:
  • Каждый узел имеет не более двух дочерних узлов
  • Потомков называют левыми и правыми
  • Предка еще называют источником
  • Двоичные деревья наиболее распространенная форма деревьев среди абстрактных типов данных

Виды двоичных деревьев:

  • Полное - в котором каждый узел, кроме листьев, имеет двух потомков. Это также называется строго бинарным деревом.
  • Законченное двоичное дерево глубины n – это такое двоичное дерево, у которого каждый уровень 0 ... n-1 имеет полный набор узлов, и все листья уровня n расположены слева.
  • Совершенное двоичное дерево – полное дерево, где все листья находятся на одном уровне.

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

  • Двоичные деревья поиска отсортированные деревья:
  • Для каждого значения x
  • Элементы левого поддерева меньше x
  • Элементы правого поддерева больше x

Псевдо код поиска:

if node is not null 
if x < node.value -> go left 
else if x > node.value -> go right 
else if x == node.value -> return node

Псевдо код вставки:

Insert x in BST 
if node is null -> insert x 
else if x < node.value -> go left 
else if x > node.value -> go right 
else -> node exists
  • Node<T> - элемент дерева 
    public class Node<T>
{
    public T Value { get; set; }
    public Node<T> LeftChild { get; set; }
    public Node<T> RightChild { get; set; }
    public Node(T value, Node<T> leftChild, Node<T> rightChild)
    {
        this.Value = value;
        this.LeftChild = leftChild;
        this.RightChild = rightChild;
    }
}
  • IAbstractBinarySearchTree<T> - интерфейс дерева/поддерева 
    public interface IAbstractBinarySearchTree<T> where T: IComparable
{
    //Вставка элемента
    void Insert(T element);

    //Содержит ли дерево данный элемент?
    bool Contains(T element);

    //Поиск
    IAbstractBinarySearchTree<T> Search(T element);

    //Корень дерева/поддерева
    Node<T> Root { get; }

    //Дочерний элемент слева
    Node<T> LeftChild { get; }

    //Дочерний элемент справа
    Node<T> RightChild { get; }

    //Значение
    T Value { get; }
}
  • BinarySearchTree - класс реализации 
    public class BinarySearchTree<T> : IAbstractBinarySearchTree<T> where T : IComparable
{
    public BinarySearchTree(Node<T> root)
    {
        this.Root = root;
        this.LeftChild = root.LeftChild;
        this.RightChild = root.RightChild;
    }

    public Node<T> Root { get; private set; }
    public Node<T> LeftChild { get; private set; }
    public Node<T> RightChild { get; private set; }
    public T Value => this.Root.Value;
    public bool Contains(T element) { ... }
    public void Insert(T element) { ... }
    public IAbstractBinarySearchTree<T> Search(T element) { ... }
}
  • Вставка 
    while (childElement != null)
{
    parentElement = childElement;
    if (newElement.Value.CompareTo(childElement.Value) < 0)
    {
        childElement = childElement.LeftChild;
    }
    else if (newElement.Value.CompareTo(childElement.Value) > 0)
    {
        childElement = childElement.RightChild;
    }
    else
    {
        return;
    }
}
  • Поиск в BST 
    public IAbstractBinarySearchTree<T> Search(T element)
{
    var current = this.Root;
    while (current != null)
    {
        if (element.CompareTo(current.Value) < 0)
        {
            current = current.LeftChild;
        }
        else if (element.CompareTo(current.Value) > 0)
        {
            current = current.RightChild;
        }
        else
        {
            break;
        }
    }
    return new BinarySearchTree<T>(current);
}

24. Куча

  • Структура данных, построенная на деревьях
  • Хранится в виде массива
  • Min heap (предок <= потомку)
  • Max heap (предок >= потомку)

Двоичная куча:

  • Структура данных, построенная на двоичных деревьях
  • Свойства:
    • Значение в любой вершине не меньше/не больше, чем значения ее потомков
    • Расстояние до корня отличается не более чем на 1 слой
    • Последний слой заполняется слева направо «без дырок»

Реализация двоичной кучи через массив:

  • Предок (i) = (I – 1) / 2
  • Левый (i) = 2 * I + 1
  • Правый (i) = 2 * I + 2

Вставка в двоичную кучу

  • Для сохранения свойств кучи:
    • Вставляем новый элемент в конец
    • Вызываем heapify (продвижение, пока дочерний элемент больше родителя)
  • Вставка элемента в кучу 
    public class MaxHeap<T> : IAbstractHeap<T> where T : IComparable<T>
{
    // TODO: хранение элементов
    public void Add(T element)
    {
        this._elements.Add(element);
        this.HeapifyUp(this.Size - 1);
    }
}
  • Просмотр и вставка элемента в кучу 
    private void HeapifyUp(int index)
{
    int parentIndex = this.GetParentIndex(index);
    while (index > 0 && IsGreater(index, parentIndex)) {
        this.Swap(index, parentIndex);
        index = parentIndex;
        parentIndex = this.GetParentIndex(index);
    }
}
//TODO: Реализовать GetParentIndex(), IsGreater() и Swap()

25. Очередь с приоритетами

  • Структура данных, представляющая собой очередь или стек
    • Каждый элемент хранится с учетом приоритета
    • Элемент с высоким приоритетом хранится перед элементом с низким
    • Элементы с равным:
      • Хранятся в порядке вставки или иначе
  • Сохраняет определенный порядок элементов
  • Элементы с более высоким приоритетом перемещаются в начало очереди
  • Элементы с более низким приоритетом перемещаются в конец очереди
  • Структура данных, поддерживающая:
  • Add(T Element)/Insert(element)
  • Dequeue()/Pull() -> max/min element
  • Peek() -> max/min element

В C# и Java приоритет как правило передается компаратором

  • IComparable<T> в C# и Comparable<T> в Java

    • class PriorityQueue<T> where T : IComparable<T> { … }
    • class PriorityQueue<T extends Comparable<T>> { … }

  • Не отсортированный динамический массив

    • 2 4 1 3 5

  • Отсортированный динамический массив

    • 1 2 3 4 5

  • Сложность:

    Операция Вставка Удаление Просмотр
    Не отсортированный O(1) O(N) O(N)
    Сортированный O(N) O(1) O(1)
    Цель O(logN) O(logN) O(logN)

Очередь с приоритетами. Max Heap. Dequeue – удаление из очереди.

  • Для сохранения свойств кучи:

    • Сохраняем первый элемент
    • Меняем местами первый и последний
    • Удаляем последний
    • Heapify (вниз) для первого элемента (спуск, пока дочерний элемент меньше большего потомка)
    • Возвращаем элемент

  • Удаление элемента – возврат 25

  • Удаление из очереди

    public T Dequeue()
{
    this.ValidateIfNotEmpty();
    T element = this._elements[0];
    this.Swap(0, this.Size – 1)
    this._elements.RemoveAt(this.Size - 1);
    this.HeapifyDown(0);
    return element;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment