Что такое высота бинарного дерева

3-й семестр / Лекция 2 — Бинарное дерево

TNode – тип узла Tdata – тип информационной части узла Операции //Создание бинарного дерева CreateBinTree T); //левое поддерево дерева Т LeftTree( T) //правое поддерево дерева Т RightTree(T) //Количество листьев Leaves(T); // Номер уровня узла n Level(n); // Количество узлов в дереве Т CountNodes(T); //Высота дерева Т height(T); //Прямой обход дерева Т PreOrderTree(T); // Обратный обход дерева Т PostOrderTree(T); // Симметричный обход дерева Т InOrderTree(T); //Вывод дерева на монитор Print(T); // Определения пустого дерева Empty(T); //Нахождение родителя узла n Parent(n); Root(T); date(n); End. Основные понятия 1. Путь в дереве. Путь от узла Х до узла У (У есть потомок Х) это последовательность узлов, начинающаяся в Х и заканчивающаяся в У, в которой каждый

элемент (кроме последнего) представляет родительский узел для следующего элемента последовательности. Пример 2. Путь в дереве от узла А к узлу С. Последовательность из элементов – узлов А, В, С. 2. Лист дерева. Лист – это узел, у которого нет поддеревьев. Количество листьев в дереве можно подсчитать рекурсивно: 0 если деревоТ пусто Leaves 1 если деревоТ лист Leaves ( LeftTree ( T )) Leaves ( RightTree ( T )) иначе 3. Высота бинарного дерева. Неформально высота дерева это количество ветвей между корневым узлом и наиболее удаленным листом. Ветвь – это линия, соединяющая корень дерева с его поддеревом. Высоту дерева можно подсчитать рекурсивно Hight ( T ) 1 если Т пусто 1 max( Hight ( LeftTree ( T )), Hight ( RightTree ( T ))) иначе Высота равна -1 устанавливается для пустого дерева, так как у дерева, состоящего из одного узла высота равна 0. Высота дерева равна максимальному уровню, который есть в дереве. 4. Уровень узла. Уровень, на котором находится узел можно рассчитать рекурсивно: level ( n ) 0 если n корень 1 level ( Parent ( n )) иначе 7. Определение количества узлов в бинарном дереве. Количество узлов бинарного дерева Т можно определить рекурсивно:

CountNodes(T) 0 если деревоТ пусто 1 CountNodes(LeftTree ( T) ) CountNodes(RightTree ( T) ) иначе

8. Теорема о двоичном дереве 1) В любом двоичном дереве количество листьев ≤ количеству узлов (Leaves(T) ≤CountNodes(T). Равенство (Leaves(T) = CountNodes(T) возможно только в случае, если дерево состоит из одного узла – корня. 2) Для раздваивающегося двоичного дерева справедлива формула Leaves(T)=(CountNodes(T)+1)/2.0 3) Для любого непустого бинарного дерева справедлива формула Leaves(T) ≤(CountNodes(T)+1)/2.0 А следовательно, справедлива формула (CountNodes(T)+1)/2.0≤2 heigh(T) Формула 2 heigh(T) определяет количество возможных листьев в дереве высотой heigh(T). 4) Если дерево полное, то справедлива зависимость (CountNodes(T)+1)/2.0=2 heigh(T) . Тогда можно вывести формулы определения количества узлов в дереве через его высоту и высоту через количество узлов: Количество узлов CountNodes(T)=2 heigh(T) *2-1 Высота дерева heigh(T)=Log 2 (CountNodes(T)+1)/2.0). Таким образом, высота дерева логарифмически зависит от количества узлов. 1. Виды двоичных деревьев 1.1.Раздваивающееся бинарное дерево. Бинарное дерево Т называется раздваивающимся деревом, если: оно пустое дерево либо оба его поддерева являются пустыми либо оба поддерева являются непустыми раздваивающимися деревьями.

А	А
	В	С	В	С
Д			Е	Д	Е
	F	G		F	G
Раздваивающееся дерево			Нераздваивающееся дерево

Рис.2. Раздваивающееся и не раздваивающееся деревья 1.2. Полное бинарное дерево. Определение 1. Полное дерево – это раздваивающееся дерево, все листья которого находятся на одном уровне. Определение 2. Бинарное дерево Т называется полным деревом, если: оно пустое дерево либо оба его поддерева имеют одинаковую высоту, и оба являются полными.

А

А

В

С

В

С

Д

Е

L

M

Д

Е

L

M

F

G

К

N

J O

P

R

F

G К

N

J O

P

Полное дерево

Неполное дерево

Рис. 3.Полное и неполное деревья Для полных деревьев можно по количеству узлов рассчитать высоту и по высоте определить количество узлов. Пример 3. Определения высоты дерева по количеству узлов в полном дереве. Пусть, полное бинарное дерево, представленное на рис. 3 имеет 15 узлов. На каждом i-ом уровне располагается 2 i узлов, тогда: на нулевом
уровне 2 0 , на первом уровне 2 1 , на втором 2 2 , на третьем 2 3 , всего 15 узлов, т.е. высота дерева равна максимальному уровню, т.е. 3. Пример 4. Определение количества узлов полного бинарного дерева по его высоте. Пусть дерево имеет высоту 3. Тогда количество его узлов будет равно сумме членов геометрической прогрессии: 1+2 1 +2 2 +2 3 т.е. вычисляется по формуле

q n	1	где nколичество членов геометрической прогрессии, тогда в
S n b 1 q
	1

нашем примере n=4, b1, это первый член прогрессии, q – шаг геометрической последовательности, в примере q=2. Следовательно количество узлов в дереве равно 15. 1.3.Законченное бинарное дерево. Это полное дерево до уровня Heigh(Т)-1 (высота -1), а все листья на нижнем уровне располагаются ближе к левому краю дерева.

А
А	А
	В	В	С
В		С	С
	Д			Е	L	M
Д	Е	L	M	Д	Е	L
				F	К	N J	O
F	G	К	N	J	O	F	G	К	N	J O
						2)
1)	3)

Рис. 4. Дерево 1 – законченное дерево, деревья 2 и 3 не являются законченными Дерево 2 не является законченным деревом, так как оно неполное до уровня Heigh(Т)-1 (у узла С нет правого поддерева). Дерево 3, так же не является законченным, так как узлы K, N, J, O не являются максимально приближенными к левому краю дерева. Узлам законченного дерева можно присвоить индексы. Корневой узел будет иметь индекс 0, тогда для любого узла с индексом i, который имеет дочерние узлы индекс левого дочернего вычисляется по формуле 2i+1, а правого 2i+2.

0
1	2
3	4	5	6
7	8	9	10	11	12

Рис.5. Индексированное законченное дерево Так как узлы дерева можно индексировать, то его можно хранить в одномерном массиве. Например, дерево 1 с рисунка 4, можно представить массивом

A	B	C	D	E	L	M	F	G	K	N	J	O
0	1	2	3	4	5	6	7	8	9	10	11	12

9. Идеально сбалансированное бинарное дерево Бинарное дерево называется идеально сбалансированным, если для каждой его вершины количество вершин в левом и правом поддереве различаются не более чем на 1. Пусть требуется построить бинарное дерево с n узлами и минимальной высотой (максимально «ветвистое» и «низкое»). Такие деревья имеют большое практическое значение, так как их использование сокращает машинное время, требуемое на выполнение различных алгоритмов. Рис.6. Примеры идеально сбалансированных бинарных деревьев Алгоритм построения идеально сбалансированного дерева при известном числе вершин n лучше всего формулируется с помощью рекурсии. При этом необходимо лишь учесть, что для достижения минимальной

высоты при заданном числе вершин, нужно располагать максимально возможное число вершин на всех уровнях, кроме самого нижнего. Это можно сделать очень просто, если распределять все поступающие в дерево вершины поровну слева и справа от каждой вершины. Суть алгоритма взять одну вершину в качестве корня. построить левое поддерево с nl = n DIV 2 вершинами тем же способом. построить правое поддерево с nr = n-nl-1 вершинами тем же способом. Реализация алгоритма создания бинарного сбалансированного дерева приведена в примере #include «stdafx.h» #include «iostream» using namespace std; class Bin < private : struct Node < int data; Node *left; Node *right; >; typedef Node * Tree ; Tree Root; int n; public : Bin( int n1 ); void createtree( Tree & T , int n ); void out( Tree & T , int i ); void print(); const static int l=5; >; Bin ::Bin( int n1 ) < n= n1 ; Root=0; createtree(Root,n); >void Bin ::createtree( Tree & T , int n ) < int nl,nr,x; if ( n !=0) < T = new Node ; T ->left=0; T ->right=0; cin >> x; T ->data=x; nl= n /2; nr= n -nl-1; Bin ::createtree( T ->left,nl); Bin ::createtree( T ->right,nr); >

> struct TNode < int data; TNode *left; TNode *right; >; void Bin ::out( Tree & T , int i ) < if ( T ) < out( T ->left, i +1); for ( int k=0; kdata right, i +1); > > void Bin ::print() < out(Root,0); >int main() < Bin B(7); B.print(); cin.get(); return 0; >10. Бинарное дерево выражений Выражение, содержащее бинарные операции можно представить как бинарное дерево, в котором внутренние узлы будут хранить операции, а листья операнды. Например, выражение (a+b)*(c-d/e) можно представить дерево Т, в корневом узле которого будет находиться операция *, правое поддерево будет представлять правый операнд (правая скобка), а левое поддерево – правый операнд (левая скобка).

*
+	—
a	b	c	/
d	e

Рис.7. Дерево выражения (a+b)*(c-d/e)

Если операнды – числа, то дерево можно использовать для вычисления значения выражения. Если операнды — переменные, то в узел операнда записывается ссылка на ячейки переменных. Дерево выражений можно использовать при вычислении значения выражения. При этом необходимо учитывать приоритетность операций и правило: сначала надо вычислить значение выражения левого поддерева, затем правого, а затем выполнить операцию, находящуюся в корне. Алгоритмы обхода бинарного дерева Обход дерева – это алгоритм, который позволяет осуществить доступ ко всем узлам дерева, только один раз. Над данными узла можно выполнять операции. Обход формирует список пройденных узлов. Алгоритмы обхода методом в “глубину” Обход в прямом порядке бинарного дерева посетить корневой узел обойти в прямом порядке левое поддерево обойти в прямом порядке правое поддерево Примечание. В алгоритмах обхода используется процедурный параметр, который определяет алгоритм обработки значения узла дерева T- visit. void Pereorder (BinTree T) < if (! Empty(T))< Visit(Root(T)); Pereorder(LeftTree(T),visit); Pereorder(RightTree(T),visit); >> Обход бинарного дерева в симметричном порядке обойти в симметричном порядке левое поддерево посетить корневой узел обойти в симметричном порядке правое поддерево

Анализ деревьев поиска¶

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

Но какова вероятная высота двоичного дерева? Ответ на этот вопрос зависит от того, как в него добавлялись ключи. Если это происходило в произвольном порядке, то высота будет примерно \(\log_2\) , где \(n\) — количество узлов в дереве. Это происходит от того, что при случайном распределении ключей около половины из них окажется меньше корня, а остальные — больше. Вспомните: двоичное дерево имеет один корень, потом уровень с двумя узлами, потом с четыремя и так далее. Количество узлов на каждом конкретном уровне — \(2^d\) , где \(d\) — его глубина. Общее число узлов в идеально сбалансированном двоичном дереве равно \(2^-1\) , где \(h\) представляет собой высоту дерева.

Идеально сбалансированное дерево имеет одинаковое количество узлов в левом и правом поддеревьях. Для него производительность put в наихудшем случае будет \(O(\log_2)\) , где \(n\) — общее количество узлов. Отметьте обратное отношение вычислений по сравнению с предыдущим абзацем. Итак, \(\log_2\) даст нам высоту дерева и максимальное число сравнений, которое потребуется put , чтобы найти подходящее место для вставки нового узла.

К сожалению, остаётся вероятность сконструировать дерево поиска с высотой, равной \(n\) . Это случится, если вставлять ключи в отсортированном порядке. Пример такого дерева приведён на рисунке 6. В этом случае производительность метода put равна \(O(n)\) .

Рисунок 6: Перекошенное двоичное дерево будет иметь низкую производительность.

После того, как мы разобрались, что производительность метода put ограничена высотой дерева, возможно, вы сумеете догадатьсяоб ограничениях остальных методов — get, in, и del . Поскольку get ищет в дереве ключ, то в наихудшем случае искомое окажется в самом низу. На первый взгляд случай del кажется более сложным, поскольку здесь требуется искать преемника для проведения операции удаления. Но вспомните: ограничение для его поиска при наихудшим сценарии — тоже высота дерева, что означает простое дублирование работы. Это константный фактор, так что он не меняет наихудший случай.

readers online now | | Back to top

© Copyright 2014 Brad Miller, David Ranum. Created using Sphinx 1.2.3.

Что такое высота бинарного дерева

По книге Laszlo
«Вычислительная геометрия и компьютерная графика на С++»

Двоичные деревья представляют эффективный способ поиска. Двоичное дерево представляет собой структурированную коллекцию узлов. Коллекция может быть пустой и в этом случае мы имеем пустое двоичное дерево. Если коллекция непуста, то она подразделяется на три раздельных семейства узлов: корневой узел n (или просто корень), двоичное дерево, называемое левым поддеревом для n, и двоичное дерево, называемое правым поддеревом для n. На рис. 1а узел, обозначенный буквой А, является корневым, узел В называется левым потомком А и является корнем левого поддерева А, узел С называется правым потомком А и является корнем правого поддерева А.

Рис. 1: Двоичное дерево с показанными внешними узллами (а) и без них (б)

Двоичное дерево на рис. 1а состоит из четырех внутренних узлов (обозначенных на рис. кружками) и пяти внешних (конечных) узлов (обозначены квадратами). Размер двоичного дерева определяется числом содержащихся в нем внутренних узлов. Внешние узлы соответствуют пустым двоичным деревьям. Например, левый потомок узла В — непустой (содержит узел D), тогда как правый потомок узла В — пустое дерево. В некоторых случаях внешние узлы обозначаются каким-либо образом, в других — на них совсем не ссылаются и они считаются пустыми двоичными деревьями (на рис. 16 внешние узлы не показаны).

Основанная на генеалогии метафора дает удобный способ обозначения узлов внутри двоичного дерева. Узел р является родителем (или предком) узла n, если n — потомок узла р. Два узла являются братьями, если они принадлежат одному и тому же родителю. Для двух заданных узлов n₁ и n_k таких, что узел n_k принадлежит поддереву с корнем в узле n₁, говорят, что узел n_k является потомком узла n₁, а узел n₁ — предком узла n_k. Существует уникальный путь от узла n₁ вниз к каждому из потомков n_k, a именно: последовательность узлов n₁ и n₂. n_k такая, что узел n_i является родителем узла n_i+1 для i = 1, 2. k-1. Длина пути равна числу ребер (k-1), содержащихся в нем. Например, на рис. 1а уникальный путь от узла А к узлу D состоит из последовательности А, В, D и имеет длину 2.

Глубина узла n определяется рекурсивно:

< 0	если n — корневой узел
глубина (n) =
< 1 + глубина (родителя (n))	в противном случае

Глубина узла равна длине уникального пути от корня к узлу. На рис. 1а узел А имеет глубину 0, а узел D имеет глубину, равную 2.

Высота узла n также определяется рекурсивно:

< 0	если n — внешний узел
высота (n) =
< 1 + max( высота(лев(n)), высота(прав(n)) )	в противном случае

где через лев(n) обозначен левый потомок узла n и через прав(n) — правый потомок узла n. Высота узла n равна длине самого длинного пути от узла n вниз до внешнего узла поддерева n. Высота двоичного дерева определяется как высота его корневого узла. Например, двоичное дерево на рис. 1а имеет высоту 3, а узел D имеет высоту 1.

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

template class TreeNode < protected: TreeNode *_lchild; TreeNode *_rchild; Т val; public: TreeNode(T); virtual ~TreeNode(void); friend class SearchTree; // возможные пополнения friend class BraidedSearchTree; // структуры >;

Элементы данных _lchild и _rchild обозначают связи текущего узла с левым и правым потомками соответственно, а элемент данных val содержит сам элемент.

Конструктор класса формирует двоичное дерево единичного размера — единственный внутренний узел имеет два пустых потомка, каждое из которых представлено нулем NULL:

template TreeNode::TreeNode(T v) : val(v), _lchild(NULL), _rchild (NULL)

Деструктор ~TreeNode рекурсивно удаляет оба потомка текущего узла (если они существуют) перед уничтожением самого текущего узла:

template TreeNode::~TreeNode(void)

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

Рис. 2: Три двоичных дерева поиска с одним и тем же набором элементов

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

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

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

Определим шаблон нового класса SearchTree для представления двоичного дерева поиска. Класс содержит элемент данных root, который указывает на корень двоичного дерева поиска (объект класса TreeNode) и элемент данных cmp, который указывает на функцию сравнения.

template class SearchTree < private: TreeNode *root; int (*) (T,T) cmp; TreeNode*_findMin(TreeNode *); void _remove(T, TreeNode * &); void _inorder(TreeNode *, void (*) (T) ); public: SearchTree (int(*) (Т, Т) ); ~SearchTree (void); int isEmpty (void); Т find(T); Т findMin(void); void inorder (void(*) (T) ); void insert(T); void remove(T); T removeMin (void); >;

Для упрощения реализации предположим, что элементами в дереве поиска являются указатели на объект заданного типа, когда шаблон класса SearchTree используется для создания действительного класса. Параметр Т передается в виде типа указателя.

Конструкторы и деструкторы

Конструктор SearchTree инициализирует элементы данных cmp для функции сравнения и root для пустого дерева поиска:

template SearchTree::SearchTree (int (*с) (Т, Т) ) : cmp(с), root (NULL)

Дерево поиска пусто только, если в элементе данных root содержится нуль (NULL) вместо разрешенного указателя:

template int SearchTree::isEmpty (void)

Деструктор удаляет все дерево путем обращения к деструктору корня:

template SearchTree::~SearchTree (void)

Поиск

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

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

template T SearchTree::find (T val) < TreeNode *n = root; while (n) < int result = (*cmp) (val, n->val); if (result < 0) n = n->_lchild; else if (result > 0) n = n->_rchild; else return n->val; > return NULL; >

Этот алгоритм поиска можно сравнить с турниром, в котором участвуют некоторые кандидаты. В начале, когда мы начинаем с корня, в состав кандидатов входят все элементы в дереве поиска. В общем случае для каждого узла n в состав кандидатов входят все потомки n. На каждом этапе производится сравнение val с n->val. Если val меньше, чем n->val, то состав кандидатов сужается до элементов, находящихся в левом поддереве, а элементы в правом поддереве n, как и сам элемент n->val, исключаются из соревнования. Аналогичным образом, если val больше, чем n->val, то состав кандидатов сужается до правого поддерева n. Процесс продолжается до тех пор, пока не будет обнаружен элемент val или не останется ни одного кандидата, что означает, что элемент val не существует в дереве поиска.

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

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

template T SearchTree::findMin (void) < TreeNode*n = _findMin (root); return (n ? n->val : NULL); > template TreeNode *SearchTree::_findMin (TreeNode *n) < if (n == NULL) return NULL; while (n->_lchild) n = n->_lchild; return n; >

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

Симметричный обход

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

Компонентная функция inorder служит в качестве ведущей функции. Она обращается к собственной компонентной функции _inorder, которая выполняет симметричный обход от узла n и применяет функцию visit к каждому достигнутому узлу.

template void SearchTree::inorder (void (*visit) (Т) ) < _inorder (root, visit); >template void SearchTree::inorder (TreeNode *n, void(*visit) (T) < if (n) < _inorder (n->_lchild, visit); (*visit) (n->val); _inorder (n->_rchild, visit); > >

При симметричном обходе каждого из двоичных деревьев поиска, показанных на рис. 2, узлы посещаются в возрастающем порядке: 2, 3, 5, 7, 8. Конечно, при симметричном обходе любого двоичного дерева поиска все его элементы посещаются в возрастающем порядке. Чтобы выяснить, почему это так, заметим, что при выполнении симметричного обхода в некотором узле n элементы меньше, чем n->val посещаются до n, поскольку они принадлежат к левому поддереву n, а элементы больше, чем n->val посещаются после n, поскольку они принадлежат правому поддереву n. Следовательно, узел n посещается в правильной последовательности. Поскольку n — произвольный узел, то это же правило соблюдается для каждого узла.

Компонентная функция inorder обеспечивает способ перечисления элементов двоичного дерева поиска в отсортированном порядке. Например, если а является деревом поиска SearchTree для строк, то эти строки можем напечатать в лексикографическом порядке одной командой а.inorder(printstring). Для этого функция обращения printstring может быть определена как:

void printstring(char *s)

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

Включение элементов

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

Компонентная функция insert включает элемент val в это двоичное дерево поиска:

Рис. 3: Включение элемента в двоичное дерево поиска

template void SearchTree::insert(T val) < if (root == NULL) < root = new TreeNode(val); return; > else < int result; TreeNode*p, *n = root; while (n) < p = n; result = (*cmp) (val, p->val); if (result < 0) n = p->_lchild; else if (result > 0) n = p->_rchild; else return; > if (result < 0) p->_lchild = new TreeNode(val); else p-> rchild = new TreeNode(val); > >

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

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

Рис. 4: Три ситуации, возникающие при удалении элемента из двоичного дерева поиска

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

1. Узел n имеет пустой левый потомок. В этом случае ссылка на n (записанная в предке n, если он есть) заменяется на ссылку на правого потомка n.
2. У узла n есть непустой левый потомок, но правый потомок пустой. В этом случае ссылка вниз на n заменяется ссылкой на левый потомок узла n.
3. Узел n имеет два непустых потомка. Найдем последователя для n (назовем его m), скопируем данные, хранящиеся в m, в узел n и затем рекурсивно удалим узел m из дерева поиска.

Очень важно проследить, как будет выглядеть результирующее двоичное дерево поиска в каждом случае. Рассмотрим случай 1. Если подлежащий удалению узел n, является левым потомком, то элементы, относящиеся к правому поддереву n будут меньше, чем у узла р, предка узла n. При удалении узла n его правое поддерево связывается с узлом р и элементы, хранящиеся в новом левом поддереве узла р конечно остаются меньше элемента в узле р. Поскольку никакие другие ссылки не изменяются, то дерево остается двоичным деревом поиска. Аргументы остаются подобными, если узел n является правым потомком, и они тривиальны, если n — корневой узел. Случай 2 объясняется аналогично. В случае 3 элемент v, записанный в узле n, перекрывается следующим большим элементом, хранящимся в узле m (назовем его w), после чего элемент w удаляется из дерева. В получающемся после этого двоичном дереве значения в левом поддереве узла n будут меньше w, поскольку они меньше v. Более того, элементы в правом поддереве узла n больше, чем w, поскольку (1) они больше, чем v, (2) нет ни одного элемента двоичного дерева поиска, лежащего между v и w и (3) из них элемент w был удален.

Заметим, что в случае 3 узел m должен обязательно существовать, поскольку правое поддерево узла n непустое. Более того, рекурсивный вызов для удаления m не может привести к срыву рекурсивного вызова, поскольку если узел m не имел бы левого потомка, то был бы применен случай 1, когда его нужно было бы удалить.

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

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

Рис. 5: Последовательность операций удаления элемента: (а) и (б) — Случай 1: удаление из двоичного дерева элемента 8; (б) и (в) — Случай 2: удаление элемента 5; (в) и (г) — Случай 3: удаление элемента 3

template void SearchTree::remove(Т val) < _remove(val, root); >template void SearchTree::_remove(Т val, TreeNode * &n) < if (n == NULL) return; int result = (*cmp) (val, n->val); if (result < 0) _remove(val, n->_lchild); else if (result > 0) _remove (val, n->_rchild); else < // случай 1 if (n->_lchild == NULL) < TreeNode*old = n; n = old->_rchild; delete old; > else if (n->_rchild == NULL < // случай 2 TreeNode *old = n; n = old->_lchild; delete old; > else < // случай 3 TreeNode *m = _findMin(n->_rchild); n->val = m->val; remove(m->val, n->_rchild); > > >

Параметр n (типа ссылки) служит в качестве псевдонима для поля ссылки, которое содержит ссылку вниз на текущий узел. При достижении узла, подлежащего удалению (old), n обозначает поле ссылки (в предке узла old), содержащее ссылку вниз на old. Следовательно команда n=old->_rchild заменяет ссылку на old ссылкой на правого потомка узла old.

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

template Т SearchTree::removeMin (void)

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

template void heapSort (T s[], int n, int(*cmp) (T,T) ) < SearchTreet(cmp); for (int i = 0; i

Также доступна реализация двоичного дерева на Си с базовыми функциями. Операторы typedef T и compGT следует изменить так, чтобы они соответствовали данным, хранимым в дереве. Каждый узел Node содержит указатели left, right на левого и правого потомков, а также указатель parent на предка. Собственно данные хранятся в поле data. Адрес узла, являющегося корнем дерева хранится в укзателе root, значение которого в самом начале, естественно, NULL. Функция insertNode запрашивает память под новый узел и вставляет узел в дерево, т.е. устанавливает нужные значения нужных указателей. Функция deleteNode, напротив, удаляет узел из дерева (т.е. устанавливает нужные значения нужных указателей), а затем освобождает память, которую занимал узел. Функция findNode ищет в дереве узел, содержащий заданное значение.

Высота двоичного дерева в C/C++

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

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

Поскольку листовые узлы, соответствующие максимальной глубине, равны 40 и 50, чтобы найти высоту, мы просто находим количество ребер от корневого узла до любого из этих двух узлов, что равно 3.

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

Логика для нахождения высоты двоичного дерева в C++

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

Мы будем использовать рекурсию по дереву, чтобы найти высоту. (Концепции см. в статье Википедии)

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

Теперь мы можем применить определение высоты к поддеревьям.

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

Поскольку высота дерева равна максимальной высоте поддерева + 1, мы продолжаем делать это, пока поддерево не станет NULL , а его высота равна 0.

В этот момент наша функция окончательно завершится, и

Давайте напишем функцию tree_height() , которая вычисляет высоту.

// Find height of a tree, defined by the root node int tree_height(Node* root) < if (root == NULL) return 0; else < // Find the height of left, right subtrees left_height = tree_height(root->left); right_height = tree_height(root->right); // Find max(subtree_height) + 1 to get the height of the tree return max(left_height, right_height) + 1; > 

Строка №3 оценивает условие завершения, когда размер поддерева равен 0 или когда корневой узел имеет значение NULL .

Строки 7 и 8 рекурсивно находят высоту левого и правого поддеревьев.

И, наконец, строка 11 возвращает максимальное значение из двух, возвращая высоту дерева.

Реализация на С/С++

Ниже приведена полная программа, показывающая, как строится двоичное дерево, а затем показана логика определения высоты в tree_height() .

#include #include typedef struct Node Node; // Define the Tree Node here struct Node < int value; // Pointers to the left and right children Node* left, *right; >; Node* init_tree(int data) < // Creates the tree and returns the // root node Node* root = (Node*) malloc (sizeof(Node)); root->left = root->right = NULL; root->value = data; return root; > Node* create_node(int data) < // Creates a new node Node* node = (Node*) malloc (sizeof(Node)); node->value = data; node->left = node->right = NULL; return node; > void free_tree(Node* root) < // Deallocates memory corresponding // to every node in the tree. Node* temp = root; if (!temp) return; free_tree(temp->left); free_tree(temp->right); if (!temp->left && !temp->right) < free(temp); return; >> int tree_height(Node* root) < // Get the height of the tree if (!root) return 0; else < // Find the height of both subtrees // and use the larger one int left_height = tree_height(root->left); int right_height = tree_height(root->right); if (left_height >= right_height) return left_height + 1; else return right_height + 1; > > int main() < // Program to demonstrate finding the height of a Binary Tree // Create the root node having a value of 10 Node* root = init_tree(10); // Insert nodes onto the tree root->left = create_node(20); root->right = create_node(30); root->left->left = create_node(40); root->left->right = create_node(50); // Find the height of the tree int height = tree_height(root); printf("Height of the Binary Tree: %d\n", height); // Free the tree! free_tree(root); return 0; > 

Все права защищены. © Linux-Console.net • 2019-2023