Olá pessoal, postei há pouco tem um gerador de referência cruzada que usa essa estrutura de árvores ( http://www.vivaolinux.com.br/script/Gerador-de-referencia-cruzada-de-texto ).

Resolvi postar aqui separadamente a estrutura da SplayTree em Python caso alguém necessite para outra aplicação.

Obs.: Desenvolvido em Python 3.1.

• Download splay_tree.zip
• Enviar nova versão

Esconder código-fonte

# -*- coding: utf-8 -*-
"""
Authors: Ewerton Lima, Fernando Rocha
Date: 07/12/2009
Version: 1.0
"""
from splay_tree_node import Node

class SplayTree(object):
    """Implementa uma árvore binária de busca do tipo SplayTree."""

    slots = ("__raiz", "__qtde")


    def __init__(self):
        self.__raiz = None
        self.__qtde = 0


    def __len__(self):
        return self.__qtde


    @property
    def raiz(self):
        '''
           Retorna valor do nó que está na raiz da árvore.
        '''
        return self.__raiz.dado

    @property
    def altura(self, pont=None):
        '''
           Retorna a altura da árvore.
        '''
        if not pont:
            pont = self.__raiz
        def altura_aux(pont):
            '''
               Método auxiliar do 'altura'.
            '''
            if not pont:
                return 0
            else:
                altura_dir = altura_aux(pont.dir) + 1
                altura_esq = altura_aux(pont.esq) + 1
                return altura_dir if altura_dir > altura_esq else altura_esq
        return altura_aux(pont)


    def remover_tudo(self):
        '''
           Apaga a árvore inteira, setando o ponteiro da raíz para valor nulo.
        '''
        self._raiz = None


    def esta_vazia(self):
        '''
           Verifica se a árvore está vazia ou se contém elementos.
           Retorna True quando vazia e False para qualquer outro caso.
        '''
        return self.__raiz == None


    def rotacionar_esquerda(self, pont=None, pont_ante=None):
        '''
           Rotaciona para a esquerda um nó representado por ponteiro
           com o parâmetro 'pont' e o seu nó pai representado por ponteiro
           usando o parâmetro 'pont_ante'.
        '''
        if pont_ante == self.__raiz:
            pont_temp = pont.esq
            pont.esq = pont_ante
            pont.pai = pont_ante.pai
            pont_ante.pai = pont
            pont_ante.dir = pont_temp
            if pont_temp:
                pont_temp.pai = pont_ante
            self.__raiz = pont
        else:
            pont_temp = pont.esq
            pont.esq = pont_ante
            pont.pai = pont_ante.pai
            pont_ante.pai = pont
            pont_ante.dir = pont_temp
            if pont_temp:
                pont_temp.pai = pont_ante
            if pont.pai.dado > pont.dado:
                pont.pai.esq = pont
                self.rotacionar_direita(pont, pont.pai)
            else:
                pont.pai.dir = pont
                self.rotacionar_esquerda(pont, pont.pai)


    def rotacionar_direita(self, pont=None, pont_ante=None):
        '''
           Rotaciona para a direita um nó representado por ponteiro
           com o parâmetro 'pont' e o seu nó pai representado por ponteiro
           usando o parâmetro 'pont_ante'.
        '''
        if pont_ante == self.__raiz:
            pont_temp = pont.dir
            pont.dir = pont_ante
            pont.pai = pont_ante.pai
            pont_ante.pai = pont
            pont_ante.esq = pont_temp
            if pont_temp:
                pont_temp.pai = pont_ante
            self.__raiz = pont
        else:
            pont_temp = pont.dir
            pont.dir = pont_ante
            pont.pai = pont_ante.pai
            pont_ante.pai = pont
            pont_ante.esq = pont_temp
            if pont_temp:
                pont_temp.pai = pont_ante
            if pont.pai.dado > pont.dado:
                pont.pai.esq = pont
                self.rotacionar_direita(pont, pont.pai)
            else:
                pont.pai.dir = pont
                self.rotacionar_esquerda(pont, pont.pai)


    def splay(self, pont):
        '''
           Faz o procedimento de Splay, baseando-se no ponteiro do elemento
           sobre o qual objetiva-se fazer o splay. Verifica qual é a
           necessidade de rotação do nó (para esquerda ou para direita)
           e faz a rotação.
        '''
        pont_ante = pont.pai
        if not (pont and pont_ante):
            return
        if pont == pont_ante.dir:
            self.rotacionar_esquerda(pont, pont_ante)
        else:
            self.rotacionar_direita(pont, pont_ante)
            
            
    def inserir(self, dado):
        '''
           Insere o elemento na árvore obedecendo às propriedades de
           uma árvore binária de busca, fazendo ainda o splay no final.
           Mantém assim as propriedades de uma SplayTree.
        '''
        nodo = Node(dado)
        if not self.__raiz:
            self.__raiz = nodo
        else:
            pont = self.__raiz
            pont_ante = self.__raiz
            while pont:
                pont_ante = pont
                if pont.dado > dado:
                    pont = pont.esq
                else:
                    pont = pont.dir
            if pont_ante.dado > dado:
                pont_ante.esq = nodo
            else:
                pont_ante.dir = nodo
            nodo.pai = pont_ante
        self.__qtde += 1
        self.splay(nodo)


    def antecessor(self, pont):
        '''Baseando-se no ponteiro representado pelo parâmetro 'pont',
           retorna o ponteiro para maior elemento da subárvore da esquerda,
           caso exista e também o ponteiro de seu nó pai.
        '''
        antecessor = pont.esq
        pont_ante = pont
        while antecessor.dir:
            pont_ante = antecessor
            antecessor = antecessor.dir
        return antecessor, pont_ante


    def remover(self, objetivo, pont=None, pont_ante=None):
        '''
           Utiliza os ponteiros 'pont' e 'pont_ante' para efetuar a remoção de
           determinado elemento. Caso não tenha os ponteiros, pode ser
           passado o valor do elemento no parâmetro 'objetivo'. Neste caso,
           será feita a busca pelos ponteiros na árvore, obedecendo às
           propriedades de uma árvore binária de busca, fazendo ainda o
           splay no final. Mantém assim as propriedades de uma SplayTree.
        '''
        if not pont:
            pont = self.buscar_sem_splay(objetivo)
            pont_ante = pont.pai
        if pont:

            #Caso em que é folha
            if not (pont.esq or pont.dir):
                if pont_ante.dir == pont:
                    pont_ante.dir = None
                else:
                    pont_ante.esq = None
                self.splay(pont)
            #Caso em que não existe o filho da direita
            elif not pont.dir:
                pont.dado = pont.esq.dado
                self.remover(objetivo, pont.esq, pont)
            #Caso em que não existe o filho da esquerda
            elif not pont.esq:
                pont.dado = pont.dir.dado
                self.remover(objetivo, pont.dir, pont)
            #Caso em que existem ambos os filhos
            else:
                antecessor, pont_ante = self.antecessor(pont)
                pont.dado = antecessor.dado
                self.remover(objetivo, antecessor, pont_ante)
            self.__qtde -= 1


    def buscar(self, objetivo):
        '''
           Faz a busca do valor representado pelo parâmetro 'objetivo',
           baseando-se nas propriedades de uma árvore binária de busca,
           fazendo ainda o splay do nó no final, se este for encontrado.
           Mantém assim as propriedades de uma SplayTree.
           Retorna o ponteiro do nó (que será a raiz após o splay).
           Se não for encontrado o elemento retornará None.
        '''
        pont = self.__raiz
        if pont:
            while pont and pont.dado != objetivo:
                if pont.dado > objetivo:
                    pont = pont.esq
                else:
                    pont = pont.dir
        if pont:
            self.splay(pont)
            return pont
        else:
            return None


    def buscar_sem_splay(self, objetivo):
        '''
           Faz a busca do valor representado pelo parâmetro 'objetivo',
           baseando-se nas propriedades de uma árvore binária de busca,
           NÃO faz o splay do nó no final. Mais utilizado dentro da classe.
           Retorna o ponteiro do nó buscado ou None se não for encontrado.
        '''
        pont = self.__raiz
        if pont:
            while pont and pont.dado != objetivo:
                if pont.dado > objetivo:
                    pont = pont.esq
                else:
                    pont = pont.dir
        if pont:
            return pont
        else:
            return None


    def caminhar(self, tipo=1, funcao=None):
        '''
           Faz o caminhamento em todos os itens da árvore e executa a função
           especificada no parâmetro funcao. Para o parâmetro "tipo" são
           válidas três opções:
           1. Em ordem
           2. Pré-ordem
           3. Pós-ordem
        '''
        if not funcao:
            funcao = self.print_dado

        def caminhar_aux(pont, tipo, func):
            '''
               Método auxiliar do 'caminhar'.
            '''
            if pont:
                if tipo == 2:
                    func(pont)
                caminhar_aux(pont.esq, 1, func)
                if tipo == 1:
                    func(pont)
                caminhar_aux(pont.dir, 1, func)
                if tipo == 3:
                    func(pont)

        caminhar_aux(self.__raiz, tipo, funcao)


    def print_dado(self, pont):
        '''
           Imprime o dado do ponteiro representado pelo parâmetro 'pont'.
        '''
        print(pont.dado)

Calcula quantos dias uma pessoa viveu

Gerador de CPF em Python

SnakeSQL - Crie consultas SQL facilmente

Just Do It - XML Generic Editor

QFacil 0.2... Qemu Facil

Nenhum comentário foi encontrado.