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

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

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

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

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

public int size(Node v)
{
return (v!=null)? v.size : 0;
}

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

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

public Node rotateRight(Node p)
{
if(p==null || p.l==null)
{
return p;
}
Node q = p.l;
p.l = q.r;
q.r = p;
updateSize(p);
updateSize(q);
return q;
}

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

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

public Node insertAsRoot(Node root, T x)
{
if(root==null)
{
Node temp = new Node();
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;
}

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

public Node merge(Node p, Node q){
if(p==null) {
return q;
}

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

if(r.nextInt(p.size+q.size)
Напишем функция удаления:

public Node remove(Node 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; } }

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

public Node insert(Node root, T x)
{
if(root==null)
{
Node temp = new Node();
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++