В этой статье мы поговорим о деревьях и в частности о двоичных (бинарных) деревьях в программировании:
- для чего нужны деревья;
- что называют деревом в программировании;
- закрепим теорию примером на языке java.
В статье о коллекциях в java я упоминал такое понятие как скорость вставки и поиска элемента в определенной структуре данных. Всем известно, что поиск элемента выполняется быстрее в массивах, чем в списках. Однако, вставка элемента в конец и в средину списка выполняется медленнее, чем в массиве. Если Вы этого не знали – будете знать. Конечно, не все так однозначно и просто как я написал в выше. Если интересна эта тема – можно поискать информацию на этот счет.
Такие структуры как деревья имеют преимущества как массивов, так и списков. Вставка и удаление в деревьях так же быстро как и в списках, а поиск работает как в массивах. Поэтому деревья заслужили уважение и широкое применение в информационных системах.
Дерево – одна из самых распространенных структур данных в программировании. Оно представляет собой древовидную структуру в виде корня и связанных узлов, соединенных ребрами.
Рисунок выше – пример дерева. Ребра это отношения между узлами. А если мы говорим на языке java – то ссылки. Узлы – это сущности или ближе к нашей теме – объекты.
Чтобы не плодить кучу слов с теорией я представлю Вам картинку с книги: Роберта Лафоре “Структуры данных и алгоритмы”, которая наглядно демонстрирует всю сущность деревьев.
В программировании, когда говорят о деревьях, то часто имеют ввиду именно двоичные деревья. Это те, в которых каждый узел имеет не более двух потомков. Если не понял – смотреть картинку выше. На ней изображено двоичное дерево. С картинки выше видно, что два потомка именуются левым и правым в зависимости от стороны в которой они расположены от родителя. Узлы размещаются в дереве не просто так. Помимо того, что каждый узел хранит данные у него есть ключ. У бинарного дерева ключ левого потомка меньше, чем у родителя, а правого – больше или равно родительскому.
При изучении деревьев часто встречается такое понятие как сбалансированность дерева. Дерево считается сбалансированным если имеет примерно одинаковое количество элементов относительно корня. Тоже самое касается и поддерева. На рисунке ниже представлен пример несбалансированного дерева.
Если дерево сбалансировано, операции с ним буду выполняться быстрее.
Теперь давайте попробуем сами написать реализацию этой замечательной структуры данных. Тем более, что на собеседованиях очень часто просят это сделать. Да и знать как это делается для себя будет очень полезно.
Для начала нужно определить, что мы будем хранить в узлах нашего дерева. В идеале – это должен быть дженерик (generics) или ссылка на некий объект, но для упрощения реализации ограничимся строковой переменной.
public int key; //ключ узла
public String data; //некоторые данные в узле
public Node leftChild; //левый потомок
public Node rightChild; //правый потомок
/**
* Метод который выводит на экран содержимое узла
*/
public void printNode(){
System.out.println("KEY " + key + " DATA: " + data);
}
}
Код выше очень простой. Он отражает все, что мы узнали об узлах. Теперь осталось создать класс, который будет представлять дерево. В нем будут методы поиска, вставки и вывода всех элементов в списке.
Node root;
/**
* Поиск элемента в дереве по ключу
* @param key
* @return
*/
public Node find(int key){
Node current = root;
while(current.key!=key){
if(current.key<key){
current = current.leftChild;
}else{
current = current.rightChild;
}
if(current==null){
return null;
}
}
return current;
}
/**
* Вставка в дерево. Суть таже что и поиск
* Только вместо вывода элемента к нему левым или правым потомком
* добавляем новый элемент
* @param key
* @param data
*/
public void insert(int key, String data){
Node node = new Node();
node.key = key;
node.data = data;
if(root==null){
root = node;
}else{
Node current = root;
Node prev = null;
while (true){
prev = current;
if(key<prev.key){
current = current.leftChild;
if(current==null){
prev.leftChild = node;
return;
}
}else{
current = current.rightChild;
if(current==null){
prev.rightChild = node;
return;
}
}
}
}
}
/**
* Вывод всех элементов дерева методом асиметричного обхода
* @param startNode
*/
public void print(Node startNode){
if(startNode != null){//условие сработает, когда мы достигним конца дерева и потомков не останется
print(startNode.leftChild);//рекурсивно вызываем левых потомков
startNode.printNode();//вызов метода принт
print(startNode.rightChild);//вызов правых
}
}
}
Теперь попробуем протестировать работу нашего приложения.
public static void main(String[] args) {
Tree tree = new Tree();
tree.insert(3, "John");
tree.insert(8, "T1000");
tree.insert(1, "Sara");
tree.insert(2, "T800");
Node findJohn = tree.find(3);
findJohn.printNode();
tree.print(findJohn);
}
}
Результат работы приложения:
Как видите, выводятся уже упорядоченные элементы. Это еще одна особенность деревьев.
Я сознательно упустил метод удаления элемента из дерева. Он довольно сложный и я не хотел делать материал обширным. Всю теорию и пример я взял из книги “Структуры данных и алгоритмы” Р. Лафоре. В ней Вы сможете найти очень подробное описание деревьев с полным примером кода на java. Данной статьи вполне достаточно чтобы понять деревья и быть готовым к вопросам по ним на собеседованиях. Как правило, спрашивают только вывод элементов дерева, который довольно простой. А в повседневной практике программирования пользуйтесь готовыми структурами данных: коллекциями и мапами.
Спасибо большое! Как всегда просто и понятно
ф-я find не рабочая,ищет только первые 3 узла
Исправленный
public Node find(int key){
Node current = root;
while(current.key!=key){
if(current.key<key){
current = current.rightChild;
}else{
current = current.leftChild;
}
if(current==null){
return null;
}
}
return current;
}
Смысловая ошибка в начале статьи “Всем известно, что поиск элемента выполняется быстрее в массивах, чем в списках. Однако, вставка элемента в конец и в средину списка выполняется медленнее, чем в массиве”.
Исходя из этого, массив всем хорош – и поиском и вставкой. А это не так.
статья не очень понравилась,а всё из-за описки. вот она:
Однако, вставка элемента в конец и в средину списка выполняется медленнее, чем в массиве.