3

Como construir uma função mysql ou consulta recursiva para trazer o último descendente de um lado específico de uma árvore binária?

Satisfazendo uma árvore binária, cada nó pode ter apenas dois ramos, um a esquerda e outro a direita.

Como fazer para pegar em uma consulta o último descendente de um ramo do lado direito?

Por exemplo:

           a 
     b           c
  d     e     f     g
 h     j k         z x

Neste conjunto de dados, o último descendente de "a", á direita é a letra "x", e na esquerda a letra "h". Para chegar até 'h', passou por 'b' e 'd', partindo de 'a' e 'lft'.

O último descendente de "b" á direita é a letra "k", a esquerda é a letra "h".

Assim como, o último descendente de "e" á direita é a letra "k", mas a esquerda é a letra "j".

Cada letra(nó) desta árvore tem a estrutura normal de uma árvore em conjuntos aninhados ou Nested Set Model, para satisfazer outras necessidades do sistema.

Ou seja, os campos id, parent_id, left, right.

E além destes, o campo tipo enum: growth_to('lft','rgt'), para indicar se o filho foi criado a esquerda ou a direita.

Por exemplo:

b.growth_on = lft
c.growth_on = rgt

Com relação a seu pai("a"), o nó "b" cresceu para esquerda, e o nó "c" para direita.

Eu preciso criar uma função recursiva mysql aonde eu informe o id do pai, e o lado(lft ou rgt) que eu quero buscar o ultimo descendente e ele me retorne a letra correspondente e suas propriedades, ou até mesmo somente o id.

Eu sei que eu poderia controlar o posicionamento do nó abaixo de seu pai, apenas movendo os indices corretos, porém quando um nó tem apenas um filho, eu necessito saber se ele é da direita ou esquerda, mesmo que existindo um só, ele precisa possuir um "lado".

Eu penso que a lógica seria, criar uma condição recursiva dentro da função mysql.

Para buscar o último nó descendente de "a" á direita, informaria o id de "a" e growth_on = 'lft'

Então dentro de um loop: (que é a parte que eu não sei fazer com funções mysql)

where children.parent_id = a.id && children.growth_on = 'lft'
8
  • 3
    Você realmente precisa fazer isso no MySQL? E por que nessa exata representação (ela pode ser trivialmente convertida em outras, veja esse artigo)? Acredito que você acabará com uma solução razoavelmente complexa e com baixa performance. Eu traria isso para uma linguagem de programação. Se forem muitos dados utilizaria um bando de dados baseado em grafos (e.g. Neo4j). Commented 28/12/2014 às 16:02
  • Eu já uso o Nested Set Model, ou "conjuntos aninhados", mas os meios normais, consideram que a árvore cresce equilibradamente, o que no meu caso, pode não ocorrer, digamos que "b" possa ter 34 filhos, enquanto "c", nenhum, então para este problema não imagino como resolver usando os meios normais. Alterar tipo de banco de dados não é uma opção no momento, realmente preciso de uma função mysql ou query recursiva, que atravesse a linha dos descendentes do lado selecionado. Commented 28/12/2014 às 16:06
  • @MarceloAymone eu concordo com a parte que o Anthony fala sobre fazer o trabalho usando uma linguagem de programação, no seu caso acho que deve ser PHP.
    – Syzoth
    Commented 29/12/2014 às 21:10
  • O que me incomoda nesta solução, é que teria que trazer toda a árvore para realizar a operação, se tiver mais de 100 níveis, ficaria absurdamente grande para calcular. Commented 29/12/2014 às 21:14
  • 1
    A falta que um "connect by" faz ...
    – Motta
    Commented 30/12/2014 às 0:31

1 Resposta 1

1

O seguinte procedure recebe a ID do nó inicial, o "lado" que você quer checar e te retorna a id do último descendente encontrado, ou do próprio nó inicial caso este não possua descendentes no lado especificado :

DELIMITER //
CREATE PROCEDURE find_leaf(IN n_id VARCHAR(10), IN side VARCHAR(10), OUT child VARCHAR(10))
BEGIN
  IF side = 'left' THEN
    SET child = (SELECT leftN FROM node WHERE id=n_id);
  ELSE
    SET child = (SELECT rightN FROM node WHERE id=n_id);
  END IF;

  IF child IS NOT NULL THEN
    CALL find_leaf(child, side, child);
  ELSE 
    SET child = n_id;
  END IF;
END //

Você pode ver o procedure funcionando aqui http://sqlfiddle.com/#!2/be812/3

Note que essa não é a melhor solução possível, apenas um esboço (funcional) da ideia. Além disso recursão de procedures é desabilitada por default no mysql (e não é possível em funções, apenas procedures), logo a invocação deve ser algo similar a isso:

SET max_sp_recursion_depth=255; -- habilita recursão, 255 é o nível máximo permitido
CALL find_leaf('a', 'rigth', @leaf);
SELECT @leaf;
CALL find_leaf('e', 'left', @leaf);
SELECT @leaf;

Obs: o schema que utilizei pode estar um pouco diferente do seu, mas deve ser simples adaptar:

CREATE TABLE node(
id VARCHAR(10) PRIMARY KEY, 
parent_id VARCHAR(10) DEFAULT NULL, 
leftN VARCHAR(10) DEFAULT NULL, 
rightN VARCHAR(10) DEFAULT NULL,
growth_on ENUM('left', 'right') DEFAULT NULL
) ENGINE=INNODB;

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .