Как найти высоту бинарного дерева поиска - Исправление недочетов и поиск решений вместе с Examum.ru

Напишите эффективный алгоритм для вычисления высоты бинарного дерева. Высота или глубина бинарного дерева — это общее количество ребер или узлов на самом длинном пути от корневого узла до конечного узла.

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

Потренируйтесь в этой проблеме

Рекурсивное решение

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

Алгоритм может быть реализован следующим образом на C++, Java и Python:

C++

#include <iostream>

using namespace std;

// Структура данных для хранения узла бинарного дерева

struct Node

{

int key;

Node *left, *right;

Node(int key)

{

this->key = key;

this->left = this->right = nullptr;

}

};

// Рекурсивная функция для вычисления высоты заданного бинарного дерева

int height(Node* root)

{

// базовый случай: пустое дерево имеет высоту 0

if (root == nullptr) {

return 0;

}

// повторяем для левого и правого поддерева и учитываем максимальную глубину

return 1 + max(height(root->left), height(root->right));

}

int main()

{

Node* root = new Node(15);

root->left = new Node(10);

root->right = new Node(20);

root->left->left = new Node(8);

root->left->right = new Node(12);

root->right->left = new Node(16);

root->right->right = new Node(25);

cout << «The height of the binary tree is « << height(root);

return 0;

}

Скачать Выполнить код

результат:

The height of the binary tree is 3

Java

// Класс для хранения узла бинарного дерева

class Node

{

int key;

Node left = null, right = null;

Node(int key) {

this.key = key;

}

class Main

{

// Рекурсивная функция для вычисления высоты заданного бинарного дерева

public static int height(Node root)

{

// базовый случай: пустое дерево имеет высоту 0

if (root == null) {

return 0;

}

// повторяем для левого и правого поддерева и учитываем максимальную глубину

return 1 + Math.max(height(root.left), height(root.right));

}

public static void main(String[] args)

{

Node root = new Node(15);

root.left = new Node(10);

root.right = new Node(20);

root.left.left = new Node(8);

root.left.right = new Node(12);

root.right.left = new Node(16);

root.right.right = new Node(25);

System.out.println(«The height of the binary tree is « + height(root));

}

Скачать Выполнить код

результат:

The height of the binary tree is 3

Python

# Класс для хранения узла бинарного дерева.

class Node:

def __init__(self, key=None, left=None, right=None):

self.key = key

self.left = left

self.right = right

# Рекурсивная функция для вычисления высоты заданного бинарного дерева

def height(root):

# Базовый случай: пустое дерево имеет высоту 0

if root is None:

return 0

# повторяется для левого и правого поддерева и учитывает максимальную глубину

return 1 + max(height(root.left), height(root.right))

if __name__ == ‘__main__’:

root = Node(15)

root.left = Node(10)

root.right = Node(20)

root.left.left = Node(8)

root.left.right = Node(12)

root.right.left = Node(16)

root.right.right = Node(25)

print(‘The height of the binary tree is’, height(root))

Скачать Выполнить код

результат:

The height of the binary tree is 3

Временная сложность приведенного выше рекурсивного решения равна O(n), куда n это общее количество узлов в бинарном дереве. Вспомогательное пространство, необходимое программе, равно O(h) для стека вызовов, где h это высота дерева.

Итеративное решение

В итеративной версии выполните обход порядка уровней на дереве. Тогда высота дерева равна общему количеству уровней в нем. Ниже приведена программа на C++, Java и Python, которая демонстрирует это:

C++

#include <iostream>

#include <list>

using namespace std;

// Структура данных для хранения узла бинарного дерева

struct Node

{

int key;

Node *left, *right;

Node(int key)

{

this->key = key;

this->left = this->right = nullptr;

}

};

// Итерационная функция для вычисления высоты заданного бинарного дерева

// путем обхода дерева по уровням

int height(Node* root)

{

// пустое дерево имеет высоту 0

if (root == nullptr) {

return 0;

}

// создаем пустую queue и ставим в queue корневой узел

list<Node*> queue;

queue.push_back(root);

Node* front = nullptr;

int height = 0;

// цикл до тех пор, пока queue не станет пустой

while (!queue.empty())

{

// вычисляем общее количество узлов на текущем уровне

int size = queue.size();

// обрабатываем каждый узел текущего уровня и ставим их в queue

// непустые левый и правый потомки

while (size—)

{

front = queue.front();

queue.pop_front();

if (front->left) {

queue.push_back(front->left);

}

if (front->right) {

queue.push_back(front->right);

}

// увеличиваем высоту на 1 для каждого уровня

height++;

}

return height;

}

int main()

{

Node* root = new Node(15);

root->left = new Node(10);

root->right = new Node(20);

root->left->left = new Node(8);

root->left->right = new Node(12);

root->right->left = new Node(16);

root->right->right = new Node(25);

cout << «The height of the binary tree is « << height(root);

return 0;

}

Скачать Выполнить код

результат:

The height of the binary tree is 3

Java

import java.util.ArrayDeque;

import java.util.Queue;

// Класс для хранения узла бинарного дерева

class Node

{

int key;

Node left = null, right = null;

Node(int data) {

this.key = data;

}

class Main

{

// Итерационная функция для вычисления высоты заданного бинарного дерева

// путем обхода дерева по уровням

public static int height(Node root)

{

// пустое дерево имеет высоту 0

if (root == null) {

return 0;

}

// создаем пустую queue и ставим в queue корневой узел

Queue<Node> queue = new ArrayDeque<>();

queue.add(root);

Node front = null;

int height = 0;

// цикл до тех пор, пока queue не станет пустой

while (!queue.isEmpty())

{

// вычисляем общее количество узлов на текущем уровне

int size = queue.size();

// обрабатываем каждый узел текущего уровня и ставим их в queue

// непустые левый и правый потомки

while (size— > 0)

{

front = queue.poll();

if (front.left != null) {

queue.add(front.left);

}

if (front.right != null) {

queue.add(front.right);

}

// увеличиваем высоту на 1 для каждого уровня

height++;

}

return height;

}

public static void main(String[] args)

{

Node root = new Node(15);

root.left = new Node(10);

root.right = new Node(20);

root.left.left = new Node(8);

root.left.right = new Node(12);

root.right.left = new Node(16);

root.right.right = new Node(25);

System.out.println(«The height of the binary tree is « + height(root));

}

Скачать Выполнить код

результат:

The height of the binary tree is 3

Python

from collections import deque

# Класс для хранения узла бинарного дерева.

class Node:

def __init__(self, data, left=None, right=None):

self.key = data

self.left = left

self.right = right

# Итерационная функция для вычисления высоты заданного бинарного дерева

#, выполняя обход по порядку уровней в дереве

def height(root):

# Пустое дерево # имеет высоту 0

if root is None:

return 0

# создает пустую queue и ставит в queue корневой узел

queue = deque()

queue.append(root)

height = 0

# Цикл # до тех пор, пока queue не станет пустой

while queue:

# вычисляет общее количество узлов на текущем уровне

size = len(queue)

# обрабатывает каждый узел текущего уровня и ставит их в queue.

# непустые левый и правый потомки

while size > 0:

front = queue.popleft()

if front.left:

queue.append(front.left)

if front.right:

queue.append(front.right)

size = size — 1

# увеличивает высоту на 1 для каждого уровня

height = height + 1

return height

if __name__ == ‘__main__’:

root = Node(15)

root.left = Node(10)

root.right = Node(20)

root.left.left = Node(8)

root.left.right = Node(12)

root.right.left = Node(16)

root.right.right = Node(25)

print(‘The height of the binary tree is’, height(root))

Скачать Выполнить код

результат:

The height of the binary tree is 3

Временная сложность приведенного выше итеративного решения равна O(n), куда n это общее количество узлов в бинарном дереве. Вспомогательное пространство, необходимое программе, равно O(n) для структуры данных queue.

Спасибо за чтение.

Пожалуйста, используйте наш онлайн-компилятор размещать код в комментариях, используя C, C++, Java, Python, JavaScript, C#, PHP и многие другие популярные языки программирования.

Как мы? Порекомендуйте нас своим друзьям и помогите нам расти. Удачного кодирования

Источник

You were given the solution by mata, but I suggest you also look at your code and understand what it is doing:

    while self.right != None:
        self = self.right
        path = path +1

What will this do? it will find the right child, then its right child, and so on. So this checks only one path of the «rightmost» leaf.

This does the same for the left:

   while self.left != None:
        self = self.left
        path = path +1

The idea in recursion is that for each subproblem, you solve it using the exact same recipe for all other subproblems. So if you would apply your algorithm only to a subtree or a leaf, it would still work.

Also, a recursive definition calls itself (although you can implement this with a loop, but that is beyond the scope here).

Remeber the definition:

Recursion: see definition of Recursion.

Источник

Создатели шаблонов в C++ заложили основу целого направления для исследований и разработки: оказалось, что язык шаблонов C++ обладает полнотой по Тьюрингу, то есть метапрограммы (программы, предназначенные для работы на этапе компиляции) C++ в состоянии вычислить всё вычислимое. На практике мощь шаблонов чаще всего применяется при описании обобщенных структур данных и алгоритмов: STL (Standard Template Library) тому живой пример.

Однако, с приходом C++11 с его variadic-шаблонами, библиотекой type_traits, кортежами и constexpr‘ами метапрограммирование стало более удобным и наглядным, открыв дорогу к реализации многих идей, которые раньше можно было воплотить только с помощью расширений конкретного компилятора или сложных многоэтажных макросов.

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

Содержание

Немного теории
Разминка: операции с кортежами и превращение числа в класс
Бинарное дерево поиска
- Рекурсивное определение
  - Отношение порядка
- Высота
- Обход центрированный (in-order traversal)
- Поиск
- Вставка
- Обход в ширину (breadth-first traversal)
- Удаление?
Применение
Что потом?
Литература

Немного теории

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

Определения и не только:

Свободное дерево (дерево без выделенного корня) или просто дерево — ациклический неориентированный граф.

Дерево с корнем — свободное дерево, в котором выделена одна вершина, называемая корнем (root).

Узлы (nodes) — вершины дерева с корнем.

Родительский узел или родитель узла X — последний узел, предшествующий X на пути от корня R к этому узлу X. В таком случае узел X называется дочерним к описанному родительскому узлу Y. Корень дерева не имеет родителя.

Лист — узел, у которого нет дочерних узлов.

Внутренний узел — узел, не являющийся листом.

Степень узла X — количество дочерних узлов этого узла X.

Глубина узла X — длина пути от корня R к этому узлу X.

Высота узла (height) — длина самого длинного простого (без возвратов) нисходящего пути от узла к листу.

Высота дерева — высота корня этого дерева.

Упорядоченное дерево — дерево с корнем, в котором дочерние узлы каждого узла упорядочены (т.е. задано отображение множества дочерних узлов на множество натуральных чисел от 1 до k, где k — общее количество дочерних узлов этого узла). Простыми словами, каждому дочернему узлу присвоено имя: «первый», «второй», …, «k-тый».

Бинарное дерево (binary tree) — (рекурсивно) либо пустое множество (не содержит узлов), либо состоит из трёх непересекающихся множеств узлов: корневой узел, бинарное дерево, называемое левым поддеревом, и бинарное дерево, называемое правым поддеревом. Таким образом, бинарное дерево — это упорядоченное дерево, у которого каждый узел имеет степень не более 2 и имеет «левый» и/или/либо «правый» дочерние узлы.

Полностью бинарное дерево (full binary tree) — бинарное дерево, у которого каждый узел либо лист, либо имеет степень два. Полностью бинарное дерево можно получить из бинарного добавлением фиктивных дочерних листов каждому узлу степени 1.

Бинарное дерево поиска — связанная структура данных, реализованная посредством бинарного дерева, каждый узел которого может быть представлен объектом, содержащим ключ (key) и сопутствующие данные, ссылки на левое и правое поддеревья и ссылку на родительский узел. Ключи бинарного дерева поиска удовлетворяют свойству бинарного дерева поиска:

если X — узел, и узел Y находится в левом поддереве X, то Y.key ≤ X.key. Если узел Y находится в правом поддереве X, то X.key ≤ Y.key.

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

Обход дерева — формирование списка узлов, порядок определяется типом обхода.

Разминка: операции с кортежами и превращение числа в класс

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

template <class U, class V>
struct tuple_concat;

template <class Tuple, class T>
struct tuple_push;

Об операциях над типами:

Разумеется, ни о каких «конкатенации» и «добавлении» типов в «контейнеры типов» речи не идёт. Это общая и важная особенность мира времени компиляции: определенный тип (класс) никаким образом модифицировать уже невозможно, но возможно определить новый (или среди ранее определенных выбрать существующий) тип, имеющий необходимые нам свойства.

Стандарт C++11 вводит заголовочный файл type_traits (как часть библиотеки поддержки типов), содержащий коллекцию полезных метафункций. Все они являются шаблонами структур, и после инстанцирования определяют локально некий тип type или числовую константу value (или ничего, как в случае отключения перегрузки с использованием std::enable_if). Мы будем придерживаться тех же принципов проектирования метафункций.

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

template <template <class...> class T, class... Alist, class... Blist>
struct tuple_concat<T<Alist...>, T<Blist...>> { using type = T<Alist..., Blist...>; };

template <template <class...> class Tuple, class... Args, class T>
struct tuple_push<Tuple<Args...>,T> { using type = Tuple<Args..., T>; };

Примерный перевод на человеческий язык специализации tuple_concat:

Если в качестве аргументов шаблона выступают два класса, которые в свою очередь являются результатами инстанцирования одного и того же шаблона класса (T) с переменным числом аргументов, и они были инстанцированы с parameter pack’ами Alist и Blist, то определить локально псевдоним type как инстанцированую версию того же шаблона класса T с конкатенированным списком аргументов, т.е. T<Alist..., Blist...>.

О терминологии:

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

Звучит зловеще, но на практике всё проще, чем кажется: при попытке вызвать tuple_concat с двумя кортежами одного вида (например, с двумя std::tuple), внутри структуры определится тип того же кортежа со «сшитым» списком аргументов входных кортежей. Иные попытки инстанцирования просто не скомпилируются (компилятор не сможет вывести типы для определенной выше частичной специализации, а инстанцирование общего шаблона окажется невозможным ввиду отсутствия его тела). Пример:

using t1 = std::tuple<char,int>;
using t2 = std::tuple<float,double>;
using t3 = std::tuple<char,int,float,double>;

using conc = typename tuple_concat<t1,t2>::type;
// using err = typename tuple_concat<int,bool>::type; // ошибка

static_assert(std::is_same<t3,conc>::value, ""); // утверждение истинно, типы одинаковы

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

template <typename U, typename V>
using tuple_concat_t = typename tuple_concat<U,V>::type;

template <typename Tuple, typename T>
using tuple_push_t = typename tuple_push<Tuple,T>::type;

Эта удобная возможность появилась в языке в C++11 стандарте: она, например, позволяет для доступа к type вместо заковыристого typename tuple_concat<t1,t2>::type писать просто tuple_concat_t<t1,t2>.

О конкатенации:

Стандартный заголовок tuple содержит определение (не мета-)функции tuple_cat(), конструирующей кортеж посредством конкатенации неопределенного числа std::tuple‘ей, переданных в качестве аргументов. Внимательный читатель может заметить, что tuple_concat может быть проще реализована посредством вывода типа результата decltype(tuple_cat(...)), однако, во-первых, полученная выше реализация не ограничена типом кортежа std::tuple, а во-вторых, это было разминочным упражнением для постепенного погружения в более сложную арифметику типов.

Последние приготовления: не для дела, а для

~~души~~

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

/// Модно-молодёжно STL-like путём
template<size_t number>
struct num_t : std::integral_constant<size_t, number> {};

// ИЛИ классически определим внутренность руками
template<size_t number>
struct num_t { enum : size_t { value = number } };

Смысл у обоих определений один: инстанцирование шаблона с различными численными аргументами будет приводить к определению различных типов: num_t<0>, num_t<13>, num_t<42> и т.д. Не более чем для удобства наделим эту структуру статическим числовым значением value, что позволит нам явно получать назад число из аргумента шаблона (посредством доступа some_num_type::value) без прибегания к выводу типа.

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

Рекурсивное определение бинарного дерева поиска оказывается удобным для непосредственного воплощения в виде шаблона. Упрощенное определение

ДЕРЕВО : NIL | [ДЕРЕВО, ДАННЫЕ, ДЕРЕВО]

можно перефразировать как «дерево — ЭТО пустое множество ИЛИ множество из трёх элементов: дерево (т.н. левое поддерево), данные, дерево (т.н. правое поддерево)».

Помимо этого, как уже упоминалось, бинарное дерево поиска требует задания отношения порядка на множестве значений, хранящихся в узлах дерева (мы должны уметь как-то сравнивать и упорядочивать узлы, т.е. иметь операцию «меньше»). Каноничным подходом является разбиение данных узла на ключ и значение (ключи сравниваем, значения просто храним), но в нашей реализации в целях упрощения структуры без ограничения общности будем считать данные узла единым типом, для задания же отношения порядка воспользуемся специальным типом Comp (comparator, поговорим о нём далее).

/// Пустое множество
struct NIL {};

/// Узел
template<typename T, typename Left, typename Right, typename Comp>
struct node {
    using type  = T;        // node value
    using LT    = Left;     // left subtree
    using RT    = Right;    // right subtree
    using comp  = Comp;     // types comparator
};

/// Лист: узел без потомков (псевдоним шаблона)
template <typename T, typename Comp>
using leaf = node<T,NIL,NIL,Comp>;

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

Об отцах и детях:

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

Сама по себе ситуация не критичная и имеет обходное решение в виде разделения объявлений и определений типов:

template<...>
struct one {
    struct two;
    using three = one<two, ...>;
    struct two : one<three, ...> {};
};

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

Однако на практике работать с такими сущностями и создавать их оказывается очень, ОЧЕНЬ сложно. Обратная ссылка на родительский элемент производит интересный эффект: фактически наше «односвязное дерево» превращается в настоящий граф (вкусно!), который при любой модификации должен инстанцировать себя «единовременно», заново и полностью (грустно). Более глубокий анализ данной ситуации выходит за рамки настоящей статьи и входит в число моих дальнейших планов по исследованию возможностей метапрограммирования в C++.

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

Отношение порядка

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

struct sizeof_comp {
    template <typename U, typename V>
    struct lt : std::integral_constant<bool, (sizeof(U) < sizeof(V))> {}; // меньше

    template <typename U, typename V>
    struct eq : std::integral_constant<bool, (sizeof(U) == sizeof(V))> {}; // равно
};

Здесь всё должно быть прозрачно: lt — метафункция «меньше» для типов, eq — метафункция «равно». Использован подход, показанный ранее для определения типов чисел: наследование от std::integral_constant наделит инстанцированные lt и eq статическими булевыми значениями value.

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

struct num_comp {
    template <typename U, typename V>
    struct lt : std::integral_constant<bool, (U::value < V::value)> {};

    template <typename U, typename V>
    struct eq : std::integral_constant<bool, (U::value == V::value)> {};
};

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

О генерации компаратора посредством CRTP:

Ранее в теоретическом разделе упоминалось, что операции «меньше», вообще говоря, достаточно, чтобы интуитивно определить и операцию «равно». Используем подход аналогичный CRTP (Curiously recurring template pattern), чтобы определить полный компаратор на основе только компаратора, содержащего операцию (метафункцию) «меньше»:

/// Шаблон для базового класса всех сгенерированных компараторов
template <typename lt_traits>
struct eq_comp {
    template <typename U, typename V>
    struct lt : std::integral_constant<bool, lt_traits::template lt<U,V>::value> {};
    
    template <typename U, typename V>
    struct eq : std::integral_constant<bool, (!lt<U,V>::value && !lt<V,U>::value)> {};
};

/// Переписаный компаратор sizeof, наследование наделит его метафункцией eq_comp::eq
struct sizeof_comp : public eq_comp<sizeof_comp> {
    template <typename U, typename V>
    struct lt : std::integral_constant<bool, (sizeof(U) < sizeof(V))> {};
};

/// Переписаный компаратор num_t
struct num_comp : public eq_comp<num_comp> {
    template <typename U, typename V>
    struct lt : std::integral_constant<bool, (U::value < V::value)> {};
};

Размер определения уменьшился и появилась математическая подоплёка — разве это не прекрасно?

Теперь у нас есть всё для того, чтобы явно, «руками», определить первое дерево типов:

using t1 = node<
    num_t<5>,
    node<
        num_t<3>,
        leaf<num_t<2>>,
        leaf<num_t<4>>
    >,
    node<
        num_t<7>,
        NIL,
        leaf<num_t<8>>
    >
>;

Примечание: Здесь и далее в примерах по-умолчанию подразумевается сравнитель num_comp, явное указание его в списке аргументов шаблонов опускается. Вообще, после разработки операции insert нам не придётся строить деревья таким образом (явным определением).

Описанное дерево изображено на рисунке.

Об отладке на этапе компиляции:

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

Эта отдельная интересная тема для дискуссии и исследования — отладка метапрограмм. У нас нет ни стека вызовов, ни переменных, ни, чёрт возьми, банального printf/std::cout. Есть техники, позволяющие печатать внутри сообщений об ошибках компилятора удобочитаемые выведенные типы, и, в принципе, это достаточно полезная возможность проверки сгенерированных структур (например, после модификации дерева).

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

Но, как бы парадоксально это ни звучало, что делать, если программа скомпилировалось успешно? Здесь уже автор более свободен в выборе методов отладки. Тип результата метафункций наподобие определенных в type_traits можно просто печатать в виде typeid(t).name() (начиная с C++11 можно легально подсматривать в RTTI). Простые структуры данных можно выводить на экран специальными метафункциями с хвостовой рекурсией, для сложных придётся городить «принтеры», сопоставимые по сложности с операциями над самой структурой.

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

                  /--{2}  
         /--{3}--<
                  --{4}  
--{5}---<
         --{7}--
                  --{8}

Высота

Посмотрим на рекурсивную функцию вычисления высоты бинарного дерева:

/// Вход: T - дерево, выход: h - высота

ВЫСОТА(T): ЕСЛИ T == NIL ВЫВОД 0 ИНАЧЕ ВЫВОД 1 + MAX(ВЫСОТА(T.LEFT), ВЫСОТА(T.RIGHT))

Она прекрасна. Просто берём и переносим эту функцию на C++:

/// Объявление общего шаблона
template <typename Tree>
struct height;

/// Частичная специализация: "ЕСЛИ T == NIL"
template <>
struct height<NIL> : std::integral_constant<size_t, 0> {};

/// Определение общего шаблона (рекурсивное)
template <typename Tree>
struct height {
    static constexpr size_t value = 1 + max(
        height<typename Tree::LT>::value,
        height<typename Tree::RT>::value
    );
};

Примечание: мы сознательно пошли на небольшое упрощение, из-за которого вычисленная высота дерева будет на 1 больше её математического определения (высота пустого множества не определена). Читатель без труда сможет исправить при необходимости эту особенность, добавив ещё один уровень косвенности и явно вычитая 1 из результата вызова метафункции, однако тогда придётся запретить инстанцирование height для пустого дерева.

Код достаточно прост: при попытке вызова height с пустым множеством будет инстанцирована соответствующая специализация, содержащая статическое value = 0, в противном случае продолжится каскад инстанцирований, пока мы не наткнёмся на пустое поддерево (то есть тот же самый NIL), на котором рекурсия и остановится. Это характерная особенность реализации рекурсивных функций посредством шаблонов C++: мы обязаны специализировать дно рекурсии, иначе каскад инстанцирований либо не остановится (компилятор выдаст ошибку о превышении лимита вложенных инстанцирований), либо на одном из шагов произойдёт попытка доступа к несуществующему члену или значению в классе (без специализации описанная выше функция в определенный момент не смогла бы получить Tree::LT, когда Tree было бы равно пустому поддереву NIL).

В коде выше используется функция max. Она должна быть constexpr (или просто метафункцией, тогда её вызов немного изменится), пример простой и известной реализации:

template <typename T> constexpr T max(T a, T b) { return a < b ? b : a; }

Наконец, использование функции height:

static_assert(height<t1>::value == 3, "");

Скажем о «сложности» функции height: требуется n инстанцирований, где n — число узлов дерева; глубина инстанцирования равна h — т.е. высоте дерева.

Какая ещё сложность и зачем она здесь?!

Дело в том, что, хотя всю работу по рекурсивному вычислению делает компилятор, его мощь не безгранична: с лёгкой руки изобретателей шаблонов наделённый обязанностью решать проблему останова (!), компилятор всё-таки должен контролировать своё собственное состояние и не вдаваться в крайности, занимаясь майнингом биткоинов сумасшедшего метапрограммиста. А если серьёзно, компилятор сам должен уметь остановиться: для этого вводятся ограничения на глубину инстанцирований шаблонов, рекурсивных вызовов constexpr-функций и длину variadic-списков аргументов.

В документации к своему любимому компилятору читатель сможет найти конкретные значения: например, gcc-5.4 «из коробки» (без дополнительных опций) инстанцирует шаблоны не глубже 900 уровней. В свете вышесказанного это означает, что нельзя забывать об оптимизации метафункций (как бы дико это ни звучало). Например, вызов height вполне может отказаться компилироваться gcc, если дерево имеет высоту > 900. Можно даже ввести O-нотацию для описания сложности (хотя часто можно точно посчитать число и глубину инстанцирований), и она будет иметь вполне здравый смысл.

Например, в стандарте C++14 планируется ввести шаблон для генерации целочисленных последовательностей (std::integer_sequence): прямая рекурсивная реализация требует N инстанцирований для последовательности 0..N-1, однако существуют элегантные древоподобные решения, глубина рекурсии которых растёт со скоростью логарифма от длины последовательности. В конце концов, мы всегда можем реализовать любую функцию полным перебором, но компилятор этому точно не обрадуется (как и мы, час ждущие завершения компиляции 30-строчной программы или вынужденные читать 9000-страничные сообщения об ошибках).

Если превышение допустимой глубины инстанцирований может просто помешать компиляции, то количество инстанцирований (т.е. вызовов метафункций) прямо влияет на время компиляции: для сложных метапрограмм оно может оказать весьма велико. Здесь играет роль множество факторов (необходимость вывода типов, сопоставление частичных специализаций и т.д.), посему не стоит забывать, что компилятор — такая же программа, а механизм шаблонов — своего рода API к внутреннему кодогенератору компилятора, и пользоваться им надо учиться так же, как осваивать отдельный язык программирования — последовательно и аккуратно (и чтобы никаких «Курсов программирования для чайников за 24 часа»!).

Обход центрированный (in-order traversal)

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

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

/// Вход: T - дерево, выход: w - список данных из узлов in-order обхода

INORDER(T): ЕСЛИ T == NIL ВЫВОД {} ИНАЧЕ ВЫВОД INORDER(T.LEFT) + {T.KEY} + INORDER(T.RIGHT)

Операция «+» в данном случае обозначает конкатенацию списков. Да-да, это именно то, ради чего мы реализовывали конкатенацию кортежей, так как кортежи — это наши списки типов на этапе компиляции. И снова — просто берём и пишем код:

/// Объявление общего шаблона
template <typename Tree>
struct walk;

/// Частичная специализация: "ЕСЛИ T == NIL"
template <>
struct walk<NIL> { using type = std::tuple<>; };

/// Определение общего шаблона (рекурсивное)
template <typename Tree>
struct walk {
private:
    // обход левого поддерева
    using accL = typename walk<typename Tree::LT>::type;

    // добавляем корень
    using accX = tuple_push_t<accL, typename Tree::type>;

    // конкатенируем с обходом правого поддерева
    using accR = tuple_concat_t<accX, typename walk<typename Tree::RT>::type>;

public:
    // результат
    using type = accR;
};

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

Сложность функции walk: O(n) инстанцирований, где n — число узлов дерева (O-нотация использована для упрощения: аккуратный подсчёт даст примерно 3n вызовов метафункций с учётом конкатенаций). Приятно, что функции tuple_concat и tuple_push выполняют свою работу за 1 инстанцирование, так как они не рекурсивны (благодаря возможности вывода типов parameter pack‘ов). Глубина инстанцирований, как и в случае height, равна h — высоте дерева.

О читаемости кода:

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

Ещё одно замечание по написанию метафункций: читатель, возможно, обратил внимание на то, что для последних двух функций нет необходимости разделять объявление и определение общего шаблона. Это так, однако я придерживаюсь стандартизированного подхода: «от максимально частного к максимально общему». Многие шаблоны целиком работают на частичных специализациях, и в таком случае очень удобно оказывается описывать эти специализации с возрастающим уровнем общности: мысленно программист проходит тот же путь, какой проходит компилятор в попытках инстанцирования и вывода типов.

Поиск

Поиск по ключу является основной операцией в классических бинарных деревьях поиска (название говорит само за себя). Мы решили не разделять ключ и данные, поэтому для сравнения узлов будем применять введённый сравнитель Comp. Рекурсивный алгоритм поиска:

/// Вход: T - дерево, k - тип-ключ,
/// выход: N - узел, содержащий тип k` == k в терминах сравнителя

SEARCH(T,k): ЕСЛИ T == NIL ИЛИ k == T.KEY ВЫВОД T ИНАЧЕ ЕСЛИ k < T.KEY ВЫВОД SEARCH(T.LEFT, k) ИНАЧЕ ВЫВОД SEARCH(T.RIGHT, k)

Реализация внешне похожа на разработанные ранее:

/// Объявление общего шаблона
template <typename Tree, typename T>
struct search;

/// Специализация для пустого дерева
template <typename T>
struct search<NIL,T> { using type = NIL; };

/// Определение общего шаблона
template <typename Tree, typename T>
struct search {
    using Comp = typename Tree::comp;
    using type = typename std::conditional<
        Comp::template eq<T, typename Tree::type>::value,       // k == T.KEY ?
        Tree,                                                   // поиск завершен, иначе:
        typename std::conditional<
            Comp::template lt<T, typename Tree::type>::value,   // k < T.KEY ?
            typename search<typename Tree::LT, T>::type,        // тогда ищем в левом
            typename search<typename Tree::RT, T>::type         // иначе -- в правом
        >::type
    >::type;
};

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

Для сравнения типов используется сравнитель из корня дерева: Tree::comp, что логично: отношение порядка определяет как способ построения дерева, так и последующие операции (в том числе, поиск), вот почему было удобно поместить псевдоним сравнителя прямо внутрь шаблона дерева (node<>).
Для доступа к шаблону, зависящему от аргумента шаблона (Tree::comp::eq<...> и Tree::comp::lt<...>), необходимо использовать ключевое слово template.
Мы пошли по пути наименьшего сопротивления и использовали std::conditional — стандартную метафункцию, определяющую результирующий псевдоним в зависимости от булевой переменной (такой аналог тернарного оператора ?: для типов). Почему это может быть не очень хорошо — см. далее, однако из положительных моментов — большая наглядность.

Сложность такой реализации search — опять-таки O(n) инстанцирований, глубина — h (высота дерева). «Стоп!» — воскликнет удивленный читатель, — «а как же логарифмическая сложность поиска и всё такое?»

Тут-то и летят камни в сторону std::conditional и выявляется его принципиальное отличие от оператора ?:: тернарный оператор не вычисляет то выражение, которое не будет его результатом (например, мы можем с чистой совестью разыменовывать нулевой указатель в одном из двух выражений, которое отбросится при проверке этого указателя в первом аргументе оператора). std::conditional же инстанцирует все три аргумента (как обычная метафункция), именно поэтому одного только std::conditional недостаточно для остановки рекурсии, и мы всё ещё должны специализировать дно рекурсии.

Прямой результат — лишние инстанцирования, захватывающие всё дерево целиком от корня до листьев. Особым колдунством с добавлением ещё одного уровня косвенности можно-таки «отключить» на каждом шаге рекурсии инстанцирования по пути поддерева, в котором точно нет искомого узла (написав ещё пачку специализаций для этого уровня косвенности), и добиться заветной сложности O(h), однако, на мой взгляд, это задача для более глубокого исследования и в данном случае будет являться преждевременной оптимизацией.

Примеры применения (использованы шаблоны псевдонимов, больше примеров см. в репозитории):

using found3 = search_t<NIL, num_t<0>, num_comp>;   // в пустом дереве
using found4 = search_t<t1, num_t<5>, num_comp>;    // значение в корне
using found5 = search_t<t1, num_t<8>, num_comp>;    // значение в листе

static_assert(std::is_same<found3, NIL>::value, "");            // не найдено
static_assert(std::is_same<found4, t1>::value, "");             // само дерево
static_assert(std::is_same<found5, leaf<num_t<8>>>::value, ""); // лист

Это может показаться странным: мы ищем в дереве узел с типом… который фактически уже указан в качестве аргумента — зачем? На самом деле, ничего необычного в этом нет — мы ищем тип, равный аргументу в терминах сравнителя. Деревья STL (std::map) тоже хранят в узлах пары (std::pair), и первый элемент пары считается ключом, который, собственно, и участвует в сравнениях. Достаточно хранить в нашем дереве ту же std::pair и заставить сравнитель Comp сравнивать пары по первому типу в паре — и получим классический ассоциативный (мета-)контейнер! Мы ещё вернёмся к этой идее в конце статьи.

Вставка

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

/// Вход: T - дерево, k - тип-ключ для вставки,
/// выход: T' - новое дерево со вставленным элементом

INSERT(T,k): ЕСЛИ T == NIL ВЫВОД {NIL, k, NIL} ИНАЧЕ ЕСЛИ k < T.KEY ВЫВОД {INSERT(T.LEFT,k), T.KEY, T.RIGHT} ИНАЧЕ ВЫВОД {T.LEFT, T.KEY, INSERT(T.RIGHT,k)}

Поясним его работу: если дерево, в которое происходит вставка, пусто, то вставляемый элемент создаст новое дерево {NIL,k,NIL}, т.е. просто лист с этим элементом (дно рекурсии). Если же дерево не пусто, то мы должны рекурсивно проваливаться до пустого дерева (т.е. до момента, пока левое или правое поддеревья не окажутся пустыми), и в итоге сформировать в этом поддереве тот же лист {NIL,k,NIL} вместо NIL, по пути «подвешивая» себя в виде нового левого или правого поддерева. В мире типов изменять существующие типы мы не можем, но можем создавать новые — это и происходит на каждом шаге рекурсии. Реализация:

template <typename Tree, typename T, typename Comp = typename Tree::comp>
struct insert;

/// Дно рекурсии
template <typename T, typename Comp>
struct insert<NIL,T,Comp> { using type = leaf<T,Comp>; };

/// Основной шаблон
template <typename Tree, typename T, typename Comp>
struct insert {
    using type = typename std::conditional<
        Comp::template lt<T, typename Tree::type>::value, // k < T.KEY?
        node<typename Tree::type, // новое дерево {INSERT(T.LEFT,k), T.KEY, T.RIGHT}
            typename insert<typename Tree::LT, T, Comp>::type,
            typename Tree::RT,
        Comp>,
        node<typename Tree::type, // новое дерево {T.LEFT, T.KEY, INSERT(T.RIGHT,k)}
            typename Tree::LT,
            typename insert<typename Tree::RT, T, Comp>::type,
        Comp>
    >::type;
};

Для добавления элемента в пустое дерево надо явно указать компаратор Comp; если же дерево не пусто, компаратор берётся по-умолчанию из корня этого дерева*.

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

using t2 = leaf<num_t<5>, num_comp>;
using t3 = insert_t<t2, num_t<3>>;
using t4 = insert_t<t3, num_t<7>>;

static_assert(height<t4>::value == 2, ""); // первые 2 уровня

using t5 = insert_t<insert_t<insert_t<t4, num_t<2>>, num_t<4>>, num_t<8>>;

static_assert(std::is_same<t5, t1>::value, ""); // равно первоначальному дереву

В библиотеке есть реализация метафункции insert_tuple, позволяющая разом положить в дерево кортеж типов (под капотом это просто рекурсия insert по кортежу), пример:

using t6 = insert_tuple_t<NIL, std::tuple<
    num_t<5>,
    num_t<7>,
    num_t<3>,
    num_t<4>,
    num_t<2>,
    num_t<8>
>, num_comp>;
        
static_assert(std::is_same<t1, t6>::value, "");

Обход в ширину (breadth-first traversal)

Обход в ширину бинарного дерева (или поиск в ширину из теории графов) формирует список узлов в порядке «по уровням» — сначала выводит корень, затем узлы с глубиной 1, затем с глубиной 2 и т.д. Алгоритм такого обхода использует очередь узлов для дальнейшего вывода (а не стек), поэтому он плохо поддаётся «конвертации» в рекурсивный. Под спойлером далее интересующийся читатель найдёт обходное решение. Здесь отметим лишь тот полезный факт, что «разобранное» обходом в ширину дерево может быть собрано обратно в точно такое же последовательной вставкой элементов из кортежа результата обхода. На рисунке предствлен обход в ширину нашего тестового дерева:

Рекурсивный обход в ширину:

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

/// Вход: T - дерево, l - уровень для вывода,
/// выход: t - список узлов этого уровня

COLLECT_LEVEL(T,l): ЕСЛИ T == NIL ВЫВОД {} ИНАЧЕ ЕСЛИ l == 0 ВЫВОД {T.KEY} ИНАЧЕ ВЫВОД COLLECT_LEVEL(T.LEFT,l-1) + COLLECT_LEVEL(T.RIGHT,l-1)

Полную реализацию на шаблонах читатель может найти в репозитории. В отличие от всех рассмотренных ранее операций, обход в ширину будет иметь сложность O(nh) инстанцирований из-за наличия цикла по высоте (который, хоть и превратится в хвостовую рекурсию, будет содержать пересчёт collect_level для всего дерева на каждом шаге).

Удаление?

Удаление узла — задача нетривиальная. Классический подход рассматривает 3 случая (по количеству дочерних узлов), и в алгоритме используются понятия последующего и родительского узла. Без обратной ссылки на родительский узел (см. спойлер «Об отцах и детях»), эффективно реализовать алгоритм проблематично: каждая операция подъёма вверх по дереву должна будет иметь сложность O(n). Наивная реализация такого удаления приведёт к «комбинаторному взрыву» по количеству инстанцирований (сложность что-то около O(nⁿ)). Разработка метафункции удаления узла входит в дальнейшие планы по усовершенствованию библиотеки. См. UPD2 в конце статьи.

Применение

Переведём дух и наконец уделим внимание вопросу, зачем может понадобиться бинарное дерево поиска времени компиляции? Есть три ответа:

Неконструктивный:

*Картинка с троллейбусом*. Опустим.

Очевидный:

…для имеющих исследовательский интерес

Конструктивный:

Приведём примеры возможных применений подобной структуры:

Сортировка типов: симметричный обход дерева формирует кортеж со списком типов, отсортированным в терминах заданного компаратора. Определение пары вспомогательных шаблонов псевдонимов позволяет одной командой «отсортировать» заданный кортеж. Как самоцель для разработки дерева — не самое полезное применение (сложность — O(n²) инстанцирований), но как лёгкий естественный бонус — вполне имеет право на существование.
Плоская runtime структура данных: после проделанной работы не составит особого труда наделить каждый узел дерева не только статическими полями, но и данными-членами. После инстанцирования дерево превратится в подобие кортежа std::tuple — плоскую структуру данных. Разумеется, в runtime изменять его структуру уже будет нельзя, но доступ по типу и обходы всё ещё будут полезными операциями, так как будут разворачиваться на этапе компиляции без единой строчки машинного кода (как std::get в применении к std::tuple).
Ассоциативный контейнер в compile-time: в первом приближении такое дерево можно использовать как аналог std::map (или множества std::set) — если вспомнить, что даже строки (точнее, строковые литералы) особой магией можно превратить в типы (и даже выполнять типичные строковые операции — конкатенацию, поиск подстрок и т.д.), такое дерево может играть ту же роль в compile-time, какую его старшие братья играют в runtime реализациях самых разных алгоритмов. Примеры: деревья суффиксов, дерево алгоритма Хаффмана, синтаксические деревья. А ещё: чувствуете этот дивный аромат рефлексии?
Генерация иерархий: как упоминалось в примечании «Лирическое отступление», Александреску использовал шаблоны для генерации сложных иерархий наследования. Дерево само по себе уже является иерархической структурой, поэтому, думаю, оно может найти применение в аналогичных задачах.

Лирическое отступление:

Через книгу «Modern C++ Design: Generic Programming and Design Patterns Applied» (в России изданная под названием «Современное проектирование на С++», см. список литературы) известного исследователя и популяризатора шаблонного программирования Андрея Александреску красной нитью проходит мысль: «заставьте компилятор делать за вас как можно большую часть работы». Автор книги применял static_assert до того, как

~~это стало мейнстримом~~

он официально появился в стандарте C++11, разработал и исследовал концепцию стратегий (или политик, policy), которая сегодня применяется в существенной части STL, фактически в рамках стандарта C++98 реализовал кортежи («списки типов») и описал процесс создания с их помощью сложных иерархий наследований (меня в своё время крайне впечатлил тот факт, что на момент написания книги многие концепты, введенные Александреску и теоретически соответствовавшие стандарту, просто не компилировались большинством компиляторов того времени).

Собственно, это к слову об основной мотивации адептов метапрограммирования: перенести как можно большую часть работы в compile-time — правила мира времени компиляции гораздо строже, однако цена ошибки намного ниже (чаще всего программа всего лишь не скомпилируется, а не выстрелит в ногу после запуска), а хорошо отлаженные библиотеки шаблонов являются незаменимым подспорьем в разработке промышленного ПО (на низком уровне практически любой «велосипед», порожденный хотелками заказчика, может быть описан стандартным шаблоном с небольшим количеством предметно-ориентированных настроек).

В довершение хочу сказать несколько слов о задаче, сподвигнувшей к разработке дерева и написанию статьи. Существует несколько алгоритмов прямой конвертации регулярного выражения в ДКА (детерминированный конечный автомат), его распознающий, часть которых оперирует т.н. синтаксическим деревом, которое по своей природе «не более чем» бинарное. Таким образом, бинарное дерево поиска времени компиляции — составная часть (и просто интересная структура для реализации) compile-time парсера регулярных выражений (после компиляции и встраивания способного развернуться в плоский код своего ДКА), который, в свою очередь, станет частью другого проекта.

Что потом?

Шёпотом: Зима…

Если настоящая статья вызовет интерес и найдёт своего читателя, я с удовольствием продолжу тему метапрограммирования (и, возможно, не только) в следующих публикациях. Из вкусного — упоминавшаяся работа со строками времени компиляции, математика времени компиляции (например, ро-факторизация Полларда), std-совместимый контейнер (с итераторами — сам tutorial по разработке контейнеров должен быть интересен). Более того, на горизонте проект парсера регекспов и некоторые другие наработки нашей команды.

Конструктивная критика категорически приветствуется!

Литература

Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е. — М.: Вильямс, 2005. — 1296 с.
Александреску А. Современное проектирование на С++: Обобщенное программирование и прикладные шаблоны проектирования = Modern C++ Design: Generic Programming and Design Patterns Applied. — С. П.: Вильямс, 2008. — 336 с. — (С++ in Depth).
Саттер Г., Андрей Александреску. Стандарты программирования на С++. Серия «C++ In-Depth» = C++ Coding Standards: 101 Rules, Guidelines and Best Practices (C++ In-Depth). — М.: «Вильямс», 2014. — 224 с.
Готтшлинг П. Современный C++ для программистов, инженеров и ученых. Серия «C++ In-Depth» = Discovering Modern C++: A Concise Introduction for Scientists and Engineers (C++ In-Depth). — М.: «Вильямс», 2016. — 512 с.

→ Репозиторий

UPD:

Реабилитация std::conditional:

Пользователь izvolov сделал важное замечание о правильном использовании std::conditional. Исправленная версия search без дополнительных специализаций и сложностью O(h) инстанцирований:

template <typename Node, typename T, typename Comp>
struct search {
    using type = typename std::conditional<
        Comp::template eq<T, typename Node::type>::value,
        Node,
        typename search<typename std::conditional<
            Comp::template lt<T, typename Node::type>::value,
            typename Node::LT,
            typename Node::RT
        >::type, T, Comp>::type
    >::type;
};

Обновление в репозитории (+insert) в процессе.

UPD2:

Реализация remove и фикс insert и search за O(h):

Репозиторий обновлён, помимо упоминавшихся исправлений insert и search он содержит также реализацию remove со сложностью и глубиной O(h) инстанцирований (подход похож на исправленный insert). Интересным моментом реализации является использование SFINAE+decltype для диспетчеризации и отключения веток условий на этапе компиляции (сама эта техника заслуживает отдельной небольшой статьи в виду дикой неочевидности и мощности, см. пример). Вот полная реализация remove:

template <typename Tree, typename T>
struct remove {
private:
    enum : bool { is_less   = Tree::comp::template lt<T, typename Tree::type>::value };
    enum : bool { is_equal  = Tree::comp::template eq<T, typename Tree::type>::value };
    
    enum : size_t { children = children_amount<Tree>::value };
    
    using key = typename min_node_t<
        typename std::conditional<
            is_equal && children == 2,
            typename Tree::RT,
            leaf<typename Tree::type, typename Tree::comp>
        >::type
    >::type;
    
    using recursive_call = typename remove<
        typename std::conditional<
            is_less,
            typename Tree::LT,
            typename std::conditional<
                !is_equal || children == 2,
                typename Tree::RT,
                NIL
            >::type
        >::type,
        typename std::conditional<
            is_equal,
            key,
            T
        >::type
    >::type;
    
    static typename Tree::RT
    root_dispatcher(...);
    
    template <typename Bush>
    static typename std::enable_if<
        sizeof(typename Bush::LT::type), typename Bush::LT
    >::type
    root_dispatcher(Bush&&);
    
public:
    using type = typename std::conditional<
        is_equal && (children < 2),
        decltype(root_dispatcher(std::declval<Tree>())),
        node<
            key,
            typename std::conditional<
                is_less,
                recursive_call,
                typename Tree::LT
            >::type,
            typename std::conditional<
                !is_less,
                recursive_call,
                typename Tree::RT
            >::type,
            typename Tree::comp
        >
    >::type;
};

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

Источник

kation

3 / 3 / 1

Регистрация: 26.10.2014

Сообщений: 17

Вычисление высоты бинарного дерева поиска на С++

09.12.2015, 19:07. Показов 24848. Ответов 3

Метки нет (Все метки)

Никак не могу вывести нормально высоту дерева, уже второй день маюсь, подскажите пожалуйста, в чем проблема ?
Например : Высоту бинарного дерева с узлами f, e, a, c, d, f, b Выводит : 2, Хотя должно вывести : 5

C++

#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <cmath>
 
using namespace std;
 
 
struct Node
{
    Node *l,*r; 
    char x; 
    
};
 
 
 
 
void add(char x,Node *&MyTree) 
{
    if (NULL==MyTree)  
    {
        MyTree=new Node; 
        MyTree->x=x; 
        MyTree->l=MyTree->r=NULL; 
    }
    else
    {
                   if (x<MyTree->x)   //Если нововведенный элемент x меньше чем элемент x из семечка дерева, уходим влево
                      {
                          if (MyTree->l!=NULL) add(x,MyTree->l); 
                          else 
                          {
                              MyTree->l=new Node; 
                              MyTree->l->l=MyTree->l->r=NULL; 
                              MyTree->l->x=x; 
                          }
                      }
                 
                    if (x>=MyTree->x)   //Если нововведенный элемент x больше чем элемент x из семечка дерева, уходим вправо
                      {
                          if (MyTree->r!=NULL) add(x,MyTree->r); 
                          else 
                          {
                              MyTree->r=new Node;  
                              MyTree->r->l=MyTree->r->r=NULL; 
                              MyTree->r->x=x; 
                          }
                      }
        
    }
    }
 
//Обход в инфиксном порядке
 void Show(Node *&tree)
{
    if (NULL==tree)    return;   
   
 
    Show(tree->l); 
    
    cout<<tree->x<<endl;
    
    
    Show(tree->r); 
}
 
  /*void Show(Node *&tree) // Обход в прямом порядке
{
    if (NULL==tree)    return;    //Если дерева нет, выходим
   
    cout<<tree->x<<endl; //Посетили узел
    Show(tree->l); //Обошли левое поддерево   
    Show(tree->r); //Обошли правое поддерево   
}*/
 
 
 int lookup(Node *&tree)
{
    int h1=0,h2=0;
    if (NULL==tree)    {return 0; }  
    if(tree->l){h1=lookup(tree->l);}
    if(tree->r){h1=lookup(tree->r);}
    return(max(h1,h2)+1);
 }
 
 
 
void main()
{
 setlocale(LC_ALL,"Russian");
    int n,how_much; 
    char x;
    Node *MyTree=NULL; 
 cout << "Сколько узлов будет в дереве ? (Введите кол-во узлов (min : 2))" << endl;
 for(int menu=0;menu==0;)
 {
 cin >> n;
 if(n>1)
 {menu++;}
 else
 {cout << "Введено неправильное кол-во узлов. Попробуйте еще." << endl;}
 }
  for (int i=0;i<n;i++) 
  {
      cout<<"Vvedite element #"<< i+1 << " : "; 
      cin>>x; 
      add(x,MyTree); 
  }
 
  Show(MyTree); // Простой обход
 how_much=lookup(MyTree);
 
 cout << " Высота данного бинарного дерева : " << how_much << endl ;
 
 
  getch ();
  
}

Геомеханик

837 / 640 / 940

Регистрация: 26.06.2015

Сообщений: 1,409

09.12.2015, 20:25

Сообщение от kation

Хотя должно вывести : 5

Всё правильно, именно 5.

C++

#include <iostream>
 
struct Node {
    Node* l, *r;
    char  x;
};  
void Node_Add(Node*& p, char x);
void Node_Clear(Node* p);
int  Node_Height(const Node* p);
 
int main(void){
    char s[] = "feacdfb";
    Node* tr = NULL;
    for(const char* i = &s[0]; *i; ++i)
        Node_Add(tr, *i);
 
    std::cout << "height: " << Node_Height(tr) << std::endl;
    Node_Clear(tr);
    return 0;
}
 
//вставка
void Node_Add(Node*& p, char x){
    if(p == NULL){
        p = new (std::nothrow) Node();
        if(p != NULL){
            p->l = p->r = NULL;
            p->x = x;
        }
    } else if(x < p->x)
        Node_Add(p->l, x);
    else
        Node_Add(p->r, x);
}
 
//удаление всех
void Node_Clear(Node* p){
    if(p != NULL){
        if(p->l != NULL)
            Node_Clear(p->l);
        if(p->r != NULL)
            Node_Clear(p->r);
        delete p;
    }
}
 
//высота дерева
int Node_Height(const Node* p){
    int l, r, h = 0;
    if(p != NULL){
        l = Node_Height(p->l);
        r = Node_Height(p->r);
        h = ((l > r) ? l : r) + 1;
    }
    return h;
}

Пример работы кода

kation

3 / 3 / 1

Регистрация: 26.10.2014

Сообщений: 17

09.12.2015, 20:56

[ТС]

Ну, я и говорю что пять, просто мне интересно, почему у меня выводит именно два, а не пять ? Х)

Добавлено через 26 минут

Сообщение от Геомеханик

Всё правильно, именно 5.
C++

C++

#include <iostream>
struct Node {
 Node* l, *r;
 char x;
}; 
void Node_Add(Node*& p, char x);
void Node_Clear(Node* p);
int Node_Height(const Node* p);
int main(void){
 char s[] = "feacdfb";
 Node* tr = NULL;
 for(const char* i = &s[0]; *i; ++i)
 Node_Add(tr, *i);
std::cout << "height: " << Node_Height(tr) << std::endl;
 Node_Clear(tr);
 return 0;
}
//вставка
void Node_Add(Node*& p, char x){
 if(p == NULL){
 p = new (std::nothrow) Node();
 if(p != NULL){
 p->l = p->r = NULL;
 p->x = x;
 }
 } else if(x < p->x)
 Node_Add(p->l, x);
 else
 Node_Add(p->r, x);
}
//удаление всех
void Node_Clear(Node* p){
 if(p != NULL){
 if(p->l != NULL)
 Node_Clear(p->l);
 if(p->r != NULL)
 Node_Clear(p->r);
 delete p;
 }
}
//высота дерева
int Node_Height(const Node* p){
 int l, r, h = 0;
 if(p != NULL){
 l = Node_Height(p->l);
 r = Node_Height(p->r);
 h = ((l > r) ? l : r) + 1;
 }
 return h;
}

Ладно, хоть переписал под себя твой код и все заработало, спасибо :3

Может кому поможет сдать лабу, я поделюсь таким кодом (Просто пример выше переписал под динамику Х) )

C++

#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <iostream>
 
using namespace std;
 
struct Node {
    Node* l, *r;
    char  x;
};  
void Node_Add(Node*& p, char x);
void Node_Clear(Node* p);
int  Node_Height(const Node* p);
 
int main(void){
 
    Node* tr = NULL;
    
 setlocale(LC_ALL,"Russian"); // Моё
    int n,how_much; 
    char x;
 
 cout << "Сколько узлов будет в дереве ? (Введите кол-во узлов (min : 2))" << endl;
 for(int menu=0;menu==0;)
 {
 cin >> n;
 if(n>1)
 {menu++;}
 else
 {cout << "Введено неправильное кол-во узлов. Попробуйте еще." << endl;}
 }
 char *s = new char[n];
  int count=0;
     for(; count<n; count++)
     {
         cout << "Введите элемент #" << count+1 << " : ";
         cin >> s[count];
        Node_Add(tr, s[count]);
     }
 
    cout << "height: " << Node_Height(tr) << std::endl;
    Node_Clear(tr);
    delete []s;
    getch ();
    return 0;
}
 
//вставка
void Node_Add(Node*& p, char x){
    if(p == NULL){
        p = new (std::nothrow) Node();
        if(p != NULL){
            p->l = p->r = NULL;
            p->x = x;
        }
    } else if(x < p->x)
        Node_Add(p->l, x);
    else
        Node_Add(p->r, x);
}
 
//удаление всех
void Node_Clear(Node* p){
    if(p != NULL){
        if(p->l != NULL)
            Node_Clear(p->l);
        if(p->r != NULL)
            Node_Clear(p->r);
        delete p;
    }
}
 
//высота дерева
int Node_Height(const Node* p){
    int l, r, h = 0;
    if(p != NULL){
        l = Node_Height(p->l);
        r = Node_Height(p->r);
        h = ((l > r) ? l : r) + 1;
    }
    return h;
}

0 / 0 / 0

Регистрация: 19.11.2020

Сообщений: 124

11.04.2021, 13:05

с написать рекурсивную функцию которая определяет высоту дерева Т (На СиС++)

Источник

Автор оригинала: Pankaj Kumar.

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

Что такое сбалансированное бинарное дерево?

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

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

Как проверить, является ли бинарное дерево сбалансировано или нет?

Согласно определению высота левого поддерева и правого поддерева не должна превышать одного на любом узле.

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

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

Algorithm CheckBalancedBinaryTree:
Input: Root Node of the binary tree.
Output:True if binary tree is balanced and False otherwise.
Start.
0.If tree is empty, return True.
1. Check the height of left sub-tree.
2.Check the height of right sub-tree.
3.If difference in height is greater than 1 return False.
4.Check if left sub-tree is balanced.
5.Check if right sub-tree is balanced.
6. If left sub-tree is balanced and right sub-tree is also balanced, return True.
End

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

Как найти высоту сбалансированного бинарного дерева?

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

Если корень пуст, то высота дерева будет 0.
Если root не пустой, то высота дерева будет равна максимальной высоте левого подделка корневого и правого подделка корня, добавленного 1.

Имея в виду вышеуказанные точки, алгоритм нахождения высоты дерева:

Высота алгоритма (дерево):
Вход: root дерева
Выход: высота дерева
Начинать.
1. Если корень нет, возврат 0.
2.Нажмите высоту левого подделки .//Height(root.leftChild)
3.Вы высота правого поддерева .//Height(root.rightChild)
4.Видите максимальное значение в 2 и 3 и добавьте 1 к нему.
Конец

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

Программа найти высоту бинарного дерева

Ниже приведен код для поиска высоты бинарного дерева.

class BinaryTreeNode:
  def __init__(self, data):
    self.data = data
    self.leftChild = None
    self.rightChild=None
    
def insert(root,newValue):
    #if binary search tree is empty, make a new node and declare it as root
    if root is None:
        root=BinaryTreeNode(newValue)
        return root
    #binary search tree is not empty, so we will insert it into the tree
    #if newValue is less than value of data in root, add it to left subtree and proceed recursively
    if newValuehright:
            return hleft+1
        else:
            return hright+1
    
root= insert(None,15)
insert(root,10)
insert(root,25)
insert(root,6)
insert(root,14)
insert(root,20)
insert(root,60)
print("Printing the height of the binary tree.")
print(height(root))

Output:

Printing the height of the binary tree.
3

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

Программа для проверки, если бинарное дерево сбалансировано или нет

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

class BinaryTreeNode:
  def __init__(self, data):
    self.data = data
    self.leftChild = None
    self.rightChild=None
    
def insert(root,newValue):
    #if binary search tree is empty, make a new node and declare it as root
    if root is None:
        root=BinaryTreeNode(newValue)
        return root
    #binary search tree is not empty, so we will insert it into the tree
    #if newValue is less than value of data in root, add it to left subtree and proceed recursively
    if newValuehright:
            return hleft+1
        else:
            return hright+1

def CheckBalancedBinaryTree(root):
    #if tree is empty,return True
    if root==None:
        return True
    #check height of left subtree
    lheight= height(root.leftChild)
    rheight = height(root.rightChild)
    #if difference in height is greater than 1, return False
    if(abs(lheight-rheight)>1):
        return False
    #check if left subtree is balanced
    lcheck=CheckBalancedBinaryTree(root.leftChild)
    #check if right subtree is balanced
    rcheck=CheckBalancedBinaryTree(root.rightChild)
    #if both subtree are balanced, return True
    if lcheck==True and rcheck==True:
        return True

    
    
root= insert(None,15)
insert(root,10)
insert(root,25)
insert(root,6)
insert(root,14)
insert(root,20)
insert(root,60)
print("Printing True if binary tree is balanced:")
print(CheckBalancedBinaryTree(root))

Output:

Printing True if binary tree is balanced:
True

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

Заключение

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

Счастливое обучение!

Источник