Splay Tree

Eu resolvi estudar essa estrutura de dados porque ela foi utilizada pelo Daniel Zerbino no Velvet e segundo ele:

"Although theoretically less efficient, they are much easier to implement and have proven in practice as efficient as other forms of binary search trees. This solution, although memory costly, proved robust even with very large datasets. The processing of reads was thus greatly accelerated and large datasets (up to 500.000.000 Illumina reads) could be hashed in a matter of hours instead of days."

Fonte: ZERBINO (2009, Genome assembly and comparison using de Bruijn graphs).

Vantagens

1. São mais fáceis de implementar que outras técnicas de árvores binárias (BST);
2. Requer menor espaço de memória que as Vermelha e Preto ou AVL (quando não for necessário informação de balanceamento).

 

Desvantagens

1. maior número de ajustes locais, durante a busca
2. Após o acesso a todos os elementos da árvore, a ordem reduz a uma lista encadeada O(n), o que corresponde ao pior caso do tempo de acesso.

Algumas curiosidades dessa estrutura:

1. Os nós mais acessados tendem a estar mais próximos da raiz, o que reduz o tempo médio de acesso.
2. Funciona com chaves repetidas e o tempo tende a O(log n).

Uma boa forma de visualizar a estrutura e as operações básicas (inserção, exclusão e busca) pode ser vista em: https://www.cs.usfca.edu/~galles/visualization/SplayTree.html

A avaliação em relação a complexidade temporal das operações (para uma árvore com n elementos):

Busca	tempo amortizado de O(logn)
Inserção	padrão das BST: O(logn)
Exclusão	semelhante as demais árvores: O(logn)

Na média, o tempo de busca, será semelhante as demais árvores, porém na prática pode ocorrer uma redução do tempo, quando a distribuição dos elementos consultados tendem a ter uma distribuição normal ao invés da distribuição aleatória que normalmente é considerada para análise desses algoritmos.

Segue uma implementação em Java do algoritmo:

//
//  Splay tree
//
public class SplayTree {

    private SplayNode root = null;

    public SplayTree() {
    }

    private SplayNode singleRotateWithLeft(SplayNode k2) {
        SplayNode k1;
        k1 = k2.left;
        k2.left = k1.right;
        k1.right = k2;
        return k1;
    }

    private SplayNode singleRotateWithRight(SplayNode k1) {
        SplayNode k2;
        k2 = k1.right;
        k1.right = k2.left;
        k2.left = k1;
        return k2;

    }

    private SplayNode splay(T value, SplayNode tree) {
        SplayNode header = new SplayNode();
        SplayNode leftTreeMax = header, rightTreeMin = header;
        if (tree == null) {
            return null;
        }
        header.left = null;
        header.right = null;
        leftTreeMax = header;
        rightTreeMin = header;
        while (!value.equals(tree.value)) {
            if (value.compareTo(tree.value) < 0) {
                if (tree.left == null) {
                    break;
                }
                if (value.compareTo(tree.left.value) < 0) {
                    tree = singleRotateWithLeft(tree);
                }
                if (tree.left == null) {
                    break;
                }
                rightTreeMin.left = tree;
                rightTreeMin = tree;
                tree = tree.left;
            } else {
                if (tree.right == null) {
                    break;
                }
                if (value.compareTo(tree.right.value) > 0) {
                    tree = singleRotateWithRight(tree);
                }
                if (tree.right == null) {
                    break;
                }
                leftTreeMax.right = tree;
                leftTreeMax = tree;
                tree = tree.right;
            }
        }
        leftTreeMax.right = tree.left;
        rightTreeMin.left = tree.right;
        tree.left = header.right;
        tree.right = header.left;
        return tree;
    }

    public void insert(T value) {
        SplayNode novo = null;
        if (root == null) {
            novo = new SplayNode();
            novo.value = value;
            novo.left = null;
            novo.right = null;
            this.root = novo;
            return;
        }
        root = splay(value, root);
        if (value.compareTo(root.value) < 0) {
            novo = new SplayNode();
            novo.value = value;
            novo.left = root.left;
            novo.right = root;
            root.left = null;
            this.root = novo;
        } else if (value.compareTo(root.value) > 0) {
            novo = new SplayNode();
            novo.value = value;
            novo.right = root.right;
            novo.left = root;
            root.right = null;
            this.root = novo;
        }
    }

    public void delete(T value) {
        if( this.root == null ) {
            return;
        }
        SplayNode noDel = splay(value, this.root);
        if (noDel.value.equals(value)) {
            if( noDel.left == null ) {
                root = noDel.right;
            } else {
                SplayNode x = root.right;
                root = root.left;
                splay(value,this.root);
                root.right = x;
            }
        }
    }

    public T find(T value) {
        SplayNode no = splay(value, this.root);
        if (no.value.equals(value)) {
            root = no;
            return (T) no.value;
        }
        return null;
    }

    static class SplayNode {
        T value = null;
        SplayNode left, right;

        @Override
        public String toString() {
            return String.format("%s [%s , %s]",value==null?"null":value,
                    left==null  ? "null" : left.value.toString(),
                    right==null ? "null" : right.value.toString() );
        }
    }
}

É um teste simples do uso da estrutura:

    public static void main(String[] args) {
        SplayTree st = new SplayTree();
        st.insert(1);
        st.insert(3);
        st.insert(2);
        st.insert(10);
        st.insert(15);
        st.insert(20);
        st.insert(9);

        internalShowTree(st);

        Integer v = st.find(10);
        System.out.printf("\n\nSearch 10 found %s\n", v == null ? " null " : v.toString());
        internalShowTree(st);

        System.out.println("Remove 10...");
        st.delete(10);
        internalShowTree(st);

        v = st.find(11);
        System.out.printf("\n\nSearch 11 found %s\n", v == null ? " null " : v.toString());

        internalShowTree(st);

    }

    private static void internalShowTree(SplayTree st) {
        Queue fila = new java.util.LinkedList();
        fila.add(st.root);
        while (!fila.isEmpty()) {
            SplayNode no = fila.poll();
            System.out.printf("No %s [left %s right %s]\n", no.value.toString(),
                    no.left != null ? no.left.value.toString() : "",
                    no.right != null ? no.right.value.toString() : "");
            if (no.left != null) {
                fila.add(no.left);
            }
            if (no.right != null) {
                fila.add(no.right);
            }
        }
    }