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

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

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

1
2
3
4
public class Node<T extends Comparable> {
    T key;
    Node l,r;
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public Node<T> find(Node<T> 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, которая будет возвращать корень нового поддерева:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public Node<T> insert(Node<T> root, T x)
{
    if(root==null)
    {
        Node temp =  new Node<T>();
        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, хоть и работает правильно приводит к тому, что дерево вырождается в цепочку. Если с помощью этой функции вставлять ключи в возрастающем (убывающем) порядке, то получится цепочка, по этой причине используют более хитрые способы.
Таким образом исходный код бинарного дерева поиска:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class BinarySearchTree<T extends Comparable> {
    public Node<T> find(Node<T> 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<T> insert(Node<T> root, T x)
    {
        if(root==null) {
            Node temp =  new Node<T>();
            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 ведь не примитив у нас.

    • http://cybern.ru/ lordrp

      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++