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'