균형 잡힌 트리를 만드는 중첩 세트를 추진합니다

StackOverflow https://stackoverflow.com/questions/1713367

  •  19-09-2019
  •  | 
  •  

문제

Propel의 NestedSet 기능을 사용하려고합니다. 그러나 트리가 생성 될 때 균형을 잡을 수 있도록 삽입하는 것에 대해 무언가를 놓치고 있습니다 (즉, 수평으로 채 웁니다).

이 요소가 있다고 말합니다.

       root
  r1c1      r1c2
r2c1 r2c2

R1C2의 첫 번째 자식으로 R2C3을 삽입하고 싶습니다 (즉, 3 행에서 시작하기 전에 2 행 2를 채우기).

이것에 대한 첫 번째 찌르기는이 기능을 만드는 것이 었습니다.

function where(User $root,$depth=0)
{
  $num = $root->getNumberOfDescendants();
  if ( $num < 2 )
    return $root;
  foreach($root->getChildren() as $d)
  {
    if ( $d->getNumberOfChildren() < 2 )
    {
      return $d;
    }
  }
  foreach($root->getChildren() as $d)
  {
    return where($d, $depth+1);
  }
}

그러나 이것은 R2C1에 어린이를 삽입하고 원하는대로 R1C2에 삽입됩니다.

다음에 사용 가능한 지점에서 트리에 입구를 삽입하는 방법이 있습니까?

티아 마이크

도움이 되었습니까?

해결책

알겠습니다. 감사합니다 http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/, 나는이 알고리즘이 내가 원하는 것을 할 것임을 발견했다.

function where($root)
{
  $num = $root->getNumberOfDescendants();
  if ( $num < 2 )
    return $root;

  $finder = DbFinder::from('User')->
    where('LeftId','>=',$root->getLeftId())->
    where('RightId','<=',$root->getRightId())->
    whereCustom('user.RightId = user.LeftId + ?',1,'left')->
    whereCustom('user.RightId = user.LeftId + ?',3,'right')->
    combine(array('left','right'),'or')->
    orderBy('ParentId');
    return $finder->findOne();
}

기본적 으로이 SQL을 실행합니다. 

SELECT u.*
FROM user u
WHERE u.LEFT_ID >= $left AND u.RIGHT_ID <= $right AND
  (u.RIGHT_ID = u.LEFT_ID+1 OR u.RIGHT_ID = u.LEFT_ID+3)
ORDER BY u.PARENT_ID
LIMIT 1

잎은 오른쪽 = 왼쪽+1이고, 1 명의 자식이있는 노드는 오른쪽 = 왼쪽+3입니다. u.parent_id의 순서를 추가하면 트리에서 가장 높은 노드를 찾을 수 있습니다. left_id 또는 right_id를 사용하는 경우 트리의 균형을 맞추지 않습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top