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

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

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

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

Где key — это ключ по которому у нас и строится дерево, l — указатель на левого сына, а r указатель на правого, size — это количество сыновей.
Рассмотрим две функции size — возвращает 0, если корня не существует и возвращает количество сыновей, если корень существует, а вторая функция updateSize — пересчитывает количество сыновей у вершины.

1
2
3
4
5
6
7
8
9
public int size(Node<T> v)
{
    return (v!=null)? v.size : 0;
}

public void updateSize(Node<T> v)
{
    if(v!=null) v.size = size(v.l) + size(v.r)+1;
}

Теперь напишем функции поворота дерева в право и влево:

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
public Node<T> rotateRight(Node<T> p)
{
    if(p==null || p.l==null)
    {
        return p;
    }
    Node<T> q = p.l;
    p.l = q.r;
    q.r = p;
    updateSize(p);
    updateSize(q);
    return q;
}

public Node<T> rotateLeft(Node<T> p)
{
    if(p==null || p.r==null)
    {
        return p;
    }
    Node<T> q = p.r;
    p.r = q.l;
    q.l = p;
    updateSize(p);
    updateSize(q);
    return q;
}

Теперь рассмотрим операцию вставки в корень:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public Node<T> insertAsRoot(Node<T> root, T x)
{
    if(root==null)
    {
        Node<T> temp = new Node<T>();
        temp.key = x;
        return temp;
    }
    if(x.compareTo(root.key)==-1){//root.key>x
        root.l = insertAsRoot(root.l,x);
        root = rotateRight(root);
    }
    else {
        root.r = insertAsRoot(root.r, x);
        root = rotateLeft(root);
    }
    updateSize(root);
    return root;
}

Теперь напишем операцию слияния двух поддеревьев:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public Node<T> merge(Node<T> p, Node<T> q){
    if(p==null) {
        return q;
    }

    if(q==null){
        return p;
    }

    if(r.nextInt(p.size+q.size)<p.size) {
        p.r= merge(p.r,q);
        updateSize(p);
        return p;
    }
    else{
        q.l = merge(p,q.l);
        updateSize(q);
        return q;
    }
}

Напишем функция удаления:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public Node<T> remove(Node<T> root, T x){
    if(root==null)
        return root;
    if(root.key==x)
    {
        return merge(root.l,root.r);
    }
    else
    {
        if(x.compareTo(root.key)<0)
        {
            root.l=remove(root.l,x);
        }
        else{
            root.r = remove(root.r,x);
        }
        updateSize(root);
        return root;
    }
}

Функция вставки:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public Node<T> insert(Node<T> root, T x)
{
    if(root==null)
    {
        Node temp =  new Node<T>();
        temp.key = x;
        return temp;
    }
    if(r.nextInt(root.size+1)==0)
    {
        return insertAsRoot(root,x);
    }
    if(root.key.compareTo(x)==-1){//x>key

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

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

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

  • на Delphi

  • на Java

  • на C++