Бинарные деревья поиска (Реализация на Java)

Java   20 января 2013  Автор статьи:  

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

public class Node {
T key;
Node l,r;
}

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

public Node find(Node root, T x)
{
if(root==null)
return null;
if(root.key==x)
return root;
if(root.key.compareTo(x)==1){

return find(root.l, x);
}
else{
return find(root.l, x);
}
}

Очевидно, что данная функция возвращает null, если такого узла не существует.
Теперь необходимо реализовать простую операцию insert, которая будет возвращать корень нового поддерева:

public Node insert(Node root, T x)
{
if(root==null)
{
Node temp = new Node();
temp.key = x;
return temp;
}

if(root.key.compareTo(x)==1){

root.r = insert(root.r, x);
}
if(root.key.compareTo(x)==-1){

root.l = insert(root.l, x);
}
return root;
}

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

public class BinarySearchTree {
public Node find(Node root, T x)
{
if(root==null)
return null;
if(root.key==x)
return root;
if(root.key.compareTo(x)==1){

return find(root.r, x);
}
else{
return find(root.l, x);
}
}
public Node insert(Node root, T x)
{
if(root==null) {
Node temp = new Node();
temp.key = x;
return temp;
}

if(root.key.compareTo(x)==1){

root.r = insert(root.r, x);
}
if(root.key.compareTo(x)==-1){

root.l = insert(root.l, x);
}
return root;
}
}


Теория по бинарным деревьям поиска

  • Алексей

    if(root.key==x)

    return root;

    Не очень уверен, что всегда работать будет.
    key ведь не примитив у нас.

    • Node вот эта штука гарантирует нам то, что тип данных T сравним.

  • Alex

    if(root.key.compareTo(x)==1){
    return find(root.l, x);
    }
    else{
    return find(root.l, x);
    }
    поправьте код. У вас будет выполняться условие или нет — всё равно return find(root.l, x)

    • Alex

      А в целом — спасибо за статью. Просто и понятно

Научиться программировать

  • на Delphi

  • на Java

  • на C++