Java глубина несбалансированное бинарное дерево

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

Бонусное упражнение: этот эскиз наивного кода пересекает дерево слишком много раз при вычислении высот. Можете ли вы сделать это более эффективным?

Супер бонусное упражнение: предположим, что дерево сильно разбалансировано. Например, миллион узлов на одной стороне и три на другой. Есть сценарий, в котором этот алгоритм выдувает стек? Можете ли вы исправить реализацию так, чтобы она никогда не сносила стек, даже если ей дано сильно несбалансированное дерево?

ОБНОВЛЕНИЕ: Donal Fellows указывает в своем ответе, что есть различные определения "сбалансированного", который можно выбрать. Например, можно взять более строгое определение "сбалансированной по высоте" и потребовать, чтобы длина пути до ближайшего пустого дочернего элемента находилась в пределах одного пути до самого дальнего пустого дочернего элемента. Мое определение менее строгое, и поэтому допускает больше деревьев.

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

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

Источник

Бинарное дерево — двоичное дерево поиска. Основные операции с бинарными деревьями (C#, Java)

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

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

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

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

Основные операции с бинарным деревом

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

Пример сбалансированного бинарного дерева (лучший случай):

Пример несбалансированного бинарного дерева (худший случай): Добавление элемента в дерево

При добавлении элемента x в дерево проверяем значение текущего узла.

• Если значение добавляемого элемента x меньше значения текущего узла, спускаемся к левому поддереву. Если его не существует, то создаем его и присваиваем значение x . Если существует, то обозначим левое поддерево как текущий узел и повторим сначала.
• Если значение добавляемого элемента x больше или равно значению текущего узла, спускаемся к правому поддереву. Если его не существует, то создаем его и присваиваем значение x . Если существует, то обозначим правое поддерево как текущий узел и повторим сначала.

Пример добавления элемента в двоичное дерево

Создадим бинарное дерево с корневым элементом 33 и добавим в него элементы в следующей последовательности: 5, 35, 1, 20, 99, 17, 18, 19, 31, 4. Получим бинарное дерево такого вида:

Поиск элемента в бинарном дереве

Поиск начинаем с родительского элемента. Допустим, мы ищем значение 18 (обозначим его за x ). Алгоритм поиска будет иметь следующий вид:

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

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

Удаление листьев

Если удаляемый элемент является листом, то просто удаляем у его родителя ссылку на этот элемент (например на значение 31). Удалим его.

Удаление узла, имеющего левое поддерево, но не имеющее правого поддерева

После удаления 31 элементом, имеющим левое поддерево, но не имеющим правого поддерева является элемент 20. Удалим его из дерева:

1. Указываем, что родителем элемента 17 теперь будет элемент 5.
2. Указываем, что правым потомком элемента 5 теперь является элемент 17.

После удаления значений 31 и 20 дерево приобретает такой вид:

Удаление узла, имеющего правое поддерево, но не имеющее левого поддерева

1. Удалим элемент 17. Присвоим его правому поддереву в качестве родителя элемент 5.
2. Элементу 5 укажем, что его правым поддеревом теперь является элемент 18.

Получим следующую картину:

Удаляем узел, имеющий поддеревья с обеих сторон

Первый случай

Правое поддерево не имеет потомка.

Чтобы иметь возможность рассмотреть этот случай, добавим элемент 34 в дерево: Удалим элемент 35. Для этого:

1. Правому поддереву (99) присвоим в качестве родителя элемент 33;
2. Ему же в качестве левого поддерева присваиваем элемент 34;
3. Элементу 34 указываем нового родителя — 99;
4. Родителю удаляемого элемента (33) указываем, что его правым поддерево теперь является элемент 99.

Второй случай

Правое поддерево имеет своих потомков.

Удаляем элемент 5. Первым потомком (одновременно самым левым — минимальным в его поддереве) элемента 5 является элемент 18:

1. Элементу 18 в качестве левого узла присвоим элемент 1;
2. Элементу 1 присвоим 18 как родителя;
3. Элементу 33 (родителю удаляемого элемента) укажем в качестве левого дочернего узла элемент 18;
4. Элементу 18 указываем в качестве родителя элемент 33 (родитель удаляемого элемента).

Дерево приобретает такой вид:

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

В своем коде я использовал нерекурсивный механизм удаления.

Существуют и другие механизмы удаления. Визуализировать свое дерево вы можете на ресурсе usfca.edu. Вы заметите, что алгоритм удаления там отличается от описанного выше.

Код класса дерева на Java в моем исполнении имеет следующий вид:

package main; import java.util.ArrayList; import java.util.List; public class Tree> < private T val; private Tree left; private Tree right; private Tree parent; private ListlistForPrint = new ArrayList<>(); public T val() < return val; >public Tree left() < return left; >public Tree right() < return right; >public Tree parent() < return parent; >public Tree(T val, Tree parent) < this.val = val; this.parent = parent; >public void add(T. vals) < for(T v : vals)< add(v); >> public void add(T val) < if(val.compareTo(this.val) < 0)< if(this.left==null)< this.left = new Tree(val, this); >else if(this.left != null) this.left.add(val); > else < if(this.right==null)< this.right = new Tree(val, this); >else if(this.right != null) this.right.add(val); > > private Tree _search(Tree tree, T val) < if(tree == null) return null; switch (val.compareTo(tree.val))< case 1: return _search(tree.right, val); case -1: return _search(tree.left, val); case 0: return tree; default: return null; >> public Tree search(T val) < return _search(this, val); >public boolean remove(T val) < //Проверяем, существует ли данный узел Treetree = search(val); if(tree == null) < //Если узла не существует, вернем false return false; >Tree curTree; //Если удаляем корень if(tree == this) < if(tree.right!=null) < curTree = tree.right; >else curTree = tree.left; while (curTree.left != null) < curTree = curTree.left; >T temp = curTree.val; this.remove(temp); tree.val = temp; return true; > //Удаление листьев if(tree.left==null && tree.right==null && tree.parent != null) < if(tree == tree.parent.left) tree.parent.left = null; else < tree.parent.right = null; >return true; > //Удаление узла, имеющего левое поддерево, но не имеющее правого поддерева if(tree.left != null && tree.right == null) < //Меняем родителя tree.left.parent = tree.parent; if(tree == tree.parent.left)< tree.parent.left = tree.left; >else if(tree == tree.parent.right) < tree.parent.right = tree.left; >return true; > //Удаление узла, имеющего правое поддерево, но не имеющее левого поддерева if(tree.left == null && tree.right != null) < //Меняем родителя tree.right.parent = tree.parent; if(tree == tree.parent.left)< tree.parent.left = tree.right; >else if(tree == tree.parent.right) < tree.parent.right = tree.right; >return true; > //Удаляем узел, имеющий поддеревья с обеих сторон if(tree.right!=null && tree.left!=null) < curTree = tree.right; while (curTree.left != null) < curTree = curTree.left; >//Если самый левый элемент является первым потомком if(curTree.parent == tree) < curTree.left = tree.left; tree.left.parent = curTree; curTree.parent = tree.parent; if (tree == tree.parent.left) < tree.parent.left = curTree; >else if (tree == tree.parent.right) < tree.parent.right = curTree; >return true; > //Если самый левый элемент НЕ является первым потомком else < if (curTree.right != null) < curTree.right.parent = curTree.parent; >curTree.parent.left = curTree.right; curTree.right = tree.right; curTree.left = tree.left; tree.left.parent = curTree; tree.right.parent = curTree; curTree.parent = tree.parent; if (tree == tree.parent.left) < tree.parent.left = curTree; >else if (tree == tree.parent.right) < tree.parent.right = curTree; >return true; > > return false; > private void _print(Tree node) < if(node == null) return; _print(node.left); listForPrint.add(node.val); System.out.print(node + " "); if(node.right!=null) _print(node.right); >public void print() < listForPrint.clear(); _print(this); System.out.println(); >@Override public String toString() < return val.toString(); >>

Поработать с классом можно следующим образом:

public static void main(String[] args) < //Создадим дерево с корневым элементом 33 Treetree = new Tree<>(33, null); tree.add(5, 35, 1, 20, 4, 17, 31, 99, 18, 19); //Распечатаем элементы дерева tree.print(); //Удалим корень tree.remove(33); tree.remove(17); tree.print(); //Проверяем элементы дерева System.out.println(tree); System.out.println(tree.left()); System.out.println(tree.left().left()); System.out.println(tree.right().left()); >

К слову, на Java такой код особого смысла писать нет, т.к. там существуют классы TreeSet и TreeMap, представляющие собой деревья.

На C# код класса бинарного дерева может иметь такой вид:

/* * User: Николай Разиов * Date: 29.10.2018 */ using System; using System.Collections.Generic; namespace Trees < public class BinaryTreewhere T : IComparable  < private BinaryTreeparent, left, right; private T val; private List listForPrint = new List(); public BinaryTree(T val, BinaryTree parent) < this.val = val; this.parent = parent; >public void add(T val) < if(val.CompareTo(this.val) < 0)< if(this.left==null)< this.left = new BinaryTree(val, this); > else if(this.left != null) this.left.add(val); > else< if(this.right==null)< this.right = new BinaryTree(val, this); > else if(this.right != null) this.right.add(val); > > private BinaryTree _search(BinaryTree tree, T val) < if(tree == null) return null; switch (val.CompareTo(tree.val))< case 1: return _search(tree.right, val); case -1: return _search(tree.left, val); case 0: return tree; default: return null; >> public BinaryTree search(T val) < return _search(this, val); >public bool remove(T val) < //Проверяем, существует ли данный узел BinaryTreetree = search(val); if(tree == null) < //Если узла не существует, вернем false return false; >BinaryTree curTree; //Если удаляем корень if(tree == this) < if(tree.right!=null) < curTree = tree.right; >else curTree = tree.left; while (curTree.left != null) < curTree = curTree.left; >T temp = curTree.val; this.remove(temp); tree.val = temp; return true; > //Удаление листьев if(tree.left==null && tree.right==null && tree.parent != null) < if(tree == tree.parent.left) tree.parent.left = null; else < tree.parent.right = null; >return true; > //Удаление узла, имеющего левое поддерево, но не имеющее правого поддерева if(tree.left != null && tree.right == null) < //Меняем родителя tree.left.parent = tree.parent; if(tree == tree.parent.left)< tree.parent.left = tree.left; >else if(tree == tree.parent.right) < tree.parent.right = tree.left; >return true; > //Удаление узла, имеющего правое поддерево, но не имеющее левого поддерева if(tree.left == null && tree.right != null) < //Меняем родителя tree.right.parent = tree.parent; if(tree == tree.parent.left)< tree.parent.left = tree.right; >else if(tree == tree.parent.right) < tree.parent.right = tree.right; >return true; > //Удаляем узел, имеющий поддеревья с обеих сторон if(tree.right!=null && tree.left!=null) < curTree = tree.right; while (curTree.left != null) < curTree = curTree.left; >//Если самый левый элемент является первым потомком if(curTree.parent == tree) < curTree.left = tree.left; tree.left.parent = curTree; curTree.parent = tree.parent; if (tree == tree.parent.left) < tree.parent.left = curTree; >else if (tree == tree.parent.right) < tree.parent.right = curTree; >return true; > //Если самый левый элемент НЕ является первым потомком else < if (curTree.right != null) < curTree.right.parent = curTree.parent; >curTree.parent.left = curTree.right; curTree.right = tree.right; curTree.left = tree.left; tree.left.parent = curTree; tree.right.parent = curTree; curTree.parent = tree.parent; if (tree == tree.parent.left) < tree.parent.left = curTree; >else if (tree == tree.parent.right) < tree.parent.right = curTree; >return true; > > return false; > private void _print(BinaryTree node) < if(node == null) return; _print(node.left); listForPrint.Add(node.val); Console.Write(node + " "); if(node.right!=null) _print(node.right); >public void print() < listForPrint.Clear(); _print(this); Console.WriteLine(); >public override string ToString() < return val.ToString(); >> >

Код примерно такой же, только для C# он будет гораздо полезнее.

Исходники проектов можно взять здесь:

Источник