수정된 순서화된 트리 검색(Modified Preorder Tree Traversal)

이 번에는, 트리를 저장하는 다른 방법에 대해 살펴 보겠다. 재귀호출은 느려질 수 있으므로, 이번에는 재귀적인 방법은 사용하지 않기로 하겠다. 우리는 데이터베이스 쿼리를 최소화할 것이다. 되도록이면 각 액티비티에 한번의 쿼리를 사용할 것이다.

우 리는 트리를 가로접근법으로 시작할 것이다. 최상위(root)노드에서 시작해 왼쪽에 1을 쓴다. 그리고, Fruit의 왼쪽에 2를 쓴다. 이 방법으로 각 노드의 좌,우측에 숫자를 써내려간다. 맨 마지막 번호는 "Food"노드의 맨 오른쪽에 쓰여질 것이다. 아래 그림에서 전체 숫자와 순서에 따른 화살표를 확인 할 수 있다.



보 시다시피, 이 숫자들은 각 노드간의 연관을 가리킨다. "Red"노드는 숫자 3과 6을 가지고 있다. 그러므로, 숫자 1과 18을 가진 "Food"노드의 자손이다. 같은 방법으로 노드의 왼쪽값이 "2"보다 크고 오른쪽 값이 "11"보다 작은 노드는 "Fruit" 노드의 자손이라고 할 수 있다. 트리구조는 이제 왼쪽값과 오른쪽값으로 저장될 수 있다. 이런 방법으로 트리를 조회하고 노드를 세는것을 "수정된 순서화 트리 검색(modified preorder tree traversal)" 알고리즘이라 부른다.

계속 진행하기 전에, 이 값들이 테이블에 어떻게 저장되는지 보자.



데 이터베이스에서 "left"와 "right"는 특별한 의미를 가지므로 "lft", "rgt"로 컬럼명을 구분했다. 또한, 이제 더이상 "parent" 컬럼이 필요없음도 함께 주목하자. 이제 트리 구조를 구현하기 위한 lft 와 rgt 값을 저장했다.

트리 조회하기
왼쪽값과 오른쪽값으로 트리를 검색하려면, 먼저 조회하고자 하는 상위 노드부터 알아야 한다. 예를들어 "Fruit"서브트리의 경우, 당신은 외쪽값이 2와 11사이인 노드들만 가져와야 한다. 

SELECT * from tree WHERE lft BETWEEN 2 AND 11;

이것은 다음을 리턴할 것이다.



모 든 트리를 한번의 쿼리로 가져왔다. 만약, 테이블에서 행을 추가하거나 삭제했다면 테이블이 올바른 순서로 정렬되어있지 않을것이므로 이 트리를 앞서했던 재귀함수와 같이 출력하려면 ORDER BY절을 쿼리에 추가해야 한다. 그러므로, 왼쪽값을 기준으로 정렬하도록 한다.

SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;

이제 남은 문제는 왼쪽에 들여쓰기를 하는것 뿐이다.

트 리와 같이 보이기 위해서, 자식은 그의 부모보다 더 들여쓰면 된다. 이것은 오른쪽값의 스택을 유지하면 가능하다. 노드의 자식에 다다를때 마다 노드의 오른쪽 값을 스택에 추가한다. 당신은 노드의 오른쪽값은 항상 부모노드의 오른쪽 값보다 작다는것을 알 수 있다. 그러므로, 현재노드의 오른쪽값과 스택의 마지막 오른쪽 노드값을 비교하면, 당신이 아직 부모의 자식노드를 출력하고 있는지 알수 있다. 노드의 출력이 끝났을때, 스택으로부터 오른쪽값을 삭제한다. 만약, 당신이 스택의 요소를 세어보면 현재노드의 레벨을 알수있을 것이다.

<?php
function display_tree($root) {
// retrieve the left and right value of the $root node
$result = mysql_query('SELECT lft, rgt FROM tree '.
'WHERE title="'.$root.'";');
$row = mysql_fetch_array($result);

// start with an empty $right stack
$right = array();

// now, retrieve all descendants of the $root node
$result = mysql_query('SELECT title, lft, rgt FROM tree '.
'WHERE lft BETWEEN '.$row['lft'].' AND '.
$row['rgt'].' ORDER BY lft ASC;');

// display each row
while ($row = mysql_fetch_array($result)) {
// only check stack if there is one
if (count($right)>0) {
// check if we should remove a node from the stack
while ($right[count($right)-1]<$row['rgt']) {
array_pop($right);
}
}

// display indented node title
echo str_repeat(' ',count($right)).$row['title']."\n";

// add this node to the stack
$right[] = $row['rgt'];
}
}
?>

이 코드를 실행해보면 재귀적함수를 사용했을때와 같은 결과를 볼 수 있을 것이다. 우리의 새로운 함수는 더 빠르며, 재귀적이지 않고 단 두번의 쿼리만 사용한다.

노드의 경로
이 새로운 알고리즘으로 특정노드의 경로를 가져오는 새로운 방법도 찾을 수 있다. 이 경로를 얻기 위해서 우리는 모든 조상의 리스트를 필요로 한다. 

우리의 새로운 테이블 구조는 더 많은 일을 필요로 하지 않는다. 예를들어, 4-5를 갖는 "Cherry"노드의 경우, 노드의 왼쪽값이 4보다 작고, 오른쪽값이 5보다 큰값을 찾으면 된다. 

SELECT title FROM tree WHERE lft < 4 AND rgt > 5 ORDER BY lft ASC;

이 쿼리에서 정렬을 위해 ORDER BY절을 반드시 사용함을 주목하라. 이 쿼리는 다음을 리턴한다.

+-------+
| title |
+-------+
| Food |
| Fruit |
| Red |
+-------+

이제 이 값들을 "Cherry"와 연결하기만 하면 된다.

자손의 갯수
노드의 왼쪽값과 오른쪽값만 알려준다면, 몇개의 자손을 가지고 있는지 간단한 산술식으로 알아낼 수 있다.
각 자손은 노드의 오른쪽값을 2씩 증가시키므로, 자손의 숫자는 아래와 같이 계산될 수 있다:

자손수 = (오른쪽값 - 왼쪽값 - 1) / 2

이 간단한 식으로 나는 2-11의 "Fruits"노드가 4개의 자손노드를 가졌으며, 8-9인 "Banana"노드는 자식을 가지지 않은 노드임을 알 수 있다.

자동 트리 검색
지금까지 이 테이블로 할수있는 간단한 것들 몇가지를 보았다. 이제 우리가 어떻게 이 테이블을 자동을로 생성할 수 있는지 배워보겠다. 이제 우리를 위해 이 모든 카운팅과 트리조회를 수행하는 수크립트가 필요하다.

근접리스트를 수정된 순서화 트리검색 테이블로 변환하기 위한 스크립트를 작성하자.

<?php
function rebuild_tree($parent, $left) {
// the right value of this node is the left value + 1
$right = $left+1;

// get all children of this node
$result = mysql_query('SELECT title FROM tree '.
'WHERE parent="'.$parent.'";');
while ($row = mysql_fetch_array($result)) {
// recursive execution of this function for each
// child of this node
// $right is the current right value, which is
// incremented by the rebuild_tree function
$right = rebuild_tree($row['title'], $right);
}

// we've got the left value, and now that we've processed
// the children of this node we also know the right value
mysql_query('UPDATE tree SET lft='.$left.', rgt='.
$right.' WHERE title="'.$parent.'";');

// return the right value of this node + 1
return $right+1;
}
?>

이 것은 재귀함수이다. 당신은 반드시 이것을 rebuild_tree('Food',1); 과 같이 시작해야 한다. 함수는 "Food"노드의 모든 자식을 검색할 것이다. 더이상 자식이 없으면, 이것은 왼쪽과 오른쪽값을 설정한다. 왼쪽값에 값이 주어지면 오른쪽 값은 왼쪽값에 1을 더한다. 자식이 있을경우 반복하여 마지막 오른쪽 값을 리턴한다. 이 값이 "Food"노드의 오른쪽 값이 된다.

재귀는 이것을 이해하기 매우 복잡한 함수로 구현한다. 하지만, 이 함수는 이 섹션의 맨 처음에 구현했던것과 같은 결과를 달성한다. 이것은 트리를 조회하면서 노드를 하나씩 추가한다. 이 함수를 실행한 후에, 당신은 왼쪽과 오른쪽값이 그대로임을 볼 수 있을 것이다 (빠른 확인법: 최상위노드의 오른쪽값은 전체노드수의 2배이다).

노드 추가
트 리에 노드를 어떻게 추가할 것인가? 거기에는 두가지 방법이 있다: 테이블에 부모컬럼을 유지하고 단지 rebuild_tree()함수를 재실행하는것 -- 간단하지만 고상하지 않은 함수이다. 또는, 새로운 노드의 오른편에서 부터 모든 노드의 왼쪽과 오른쪽값을 갱신하는 것이다.

첫번째 방법은 단순하다. 당신은 근접 리스트 방법은 갱신에만 사용하고, 수정된 순서화 트리 검색 알고리즘을 조회를 위해 사용한다. 만약, 당신이 새로운 노드를 추가하려면 단지 테이블에 추가하고 부모컬럼을 설정하기만 하면 된다. 그리고 단순히 rebuild_tree() 함수를 재호출하는 것이다. 이것은 쉽다. 하지만, 큰 트리구조에서는 매우 비효율적이다.

두번째 방법은 새로운 노드의 오른쪽에 있는 노드의 왼쪽값과 오른쪽값을 변경하여 추가, 삭제하는것이다. 예를들어 보자. 우리는 새로운 과일종인 "Strawberry"를 "Red"의 마지막 자손에 추가하고 싶다. 먼저, 우리는 약간의 공간을 확보해야 한다. "Red"의 오른쪽 값은 6에서 8로 변경되어야 하며, 7-10인 "Yellow"노드는 9-12로 변경되어야 한다. "Red"노드를 갱신한다는 것은 왼쪽과 오른쪽값이 5보다 큰값들에 2를 더해야 함을 의미한다.

우리는 다음 쿼리를 사용할 것이다.

UPDATE tree SET rgt=rgt+2 WHERE rgt>5;
UPDATE tree SET lft=lft+2 WHERE lft>5;

이제 우리는"Strawberry"노드를 새로은 공간에 추가할수 있다. 이 노드는 왼쪽에 6, 오른쪽에 7을 가진다.

INSERT INTO tree SET lft=6, rgt=7, title='Strawberry';

display_tree()함수를 실행하면, 새로운 "Strawberry"노드가 추가된 것을 볼 수 있을 것이다.

Food
Fruit
Red
Cherry
Strawberry
Yellow
Banana
Meat
Beef
Pork

단점
수 정된 순서화된 트리조회 알고리즘(modified preorder tree traversal algorithm)은 이해하기 약간 어려워 보인다. 이것은 분명히 근접리스트방법 보다 덜 간단하다. 하지만, 한번 당신이 왼쪽과 오른쪽 속성을 사용하게 되면, 당신은 근접리스트방법으로 했던 모든것을 이 테크닉으로 할수 있음이 명확해 질것이다. 그리고, 수정된 순서화 트리조회 알고리즘은 훨씬 빠른다. 트리를 갱신하는데는 쿼리를 더해 느려지지만 노드를 조회하는것은 단지 하나우 쿼리로 할 수 있다.

결론
이제 당신은 데이터베이스테 트리를 저장하는 두가지 방법과 친숙해 졌다. 나는 수정된 순서화 트리 조회를 좀 더 선호하지만 당신은 때에 따라 근접리스트 방법이 더 나을수도 있다. 그 결정은 당신의 몫으로 남겨두겠다.

마 지막 조언: 이미 언급한바와 같이 나는 노드의 제목(title)으로 노드를 참조하는것을 추천하지 않는다. 당신은 반드시 데이터베이스 일반화의 기본적인 규칙을 따라야 한다. 나는 예제가 읽기 편하게 하기 위해 숫자형태의 구분값을 사용하지 않았을 뿐이다.

원문주소 : http://www.sitepoint.com/print/hierarchical-data-database
번역 : 이원찬