집 > 기사 > 백엔드 개발 > 무한분류 좌우값 구현 알고리즘

무한분류 좌우값 구현 알고리즘

WBOY원래의: 2016-07-29 09:14:401133검색

1. 소개

제품 분류, 다단계 트리 구조 포럼, 메일링 목록 및 기타 여러 곳에서 이러한 문제에 직면하게 됩니다. 다단계 구조 데이터를 저장하는 방법은 무엇입니까? PHP 애플리케이션에서 백엔드 데이터 저장소는 일반적으로 많은 양의 데이터를 저장하고 효율적인 데이터 검색 및 업데이트 서비스를 제공할 수 있는 관계형 데이터베이스입니다. 그러나 관계형 데이터의 기본 형태는 평면 구조인 교차 테이블입니다. 관계형 데이터베이스에 다단계 트리 구조를 저장하려면 합리적인 변환 작업을 수행해야 합니다. 다음으로 제가 보고 들은 것과 몇 가지 실제 경험에 대해 이야기해 보겠습니다.
플랫 데이터베이스에 계층적 데이터를 저장하는 데는 기본적으로 두 가지 일반적인 설계 방법이 있습니다.
* 인접 목록 모델
* 수정된 선주문 트리 순회 알고리즘

2. 모델

여기에서는 간단한 음식 디렉토리를 예제 데이터로 사용합니다.
우리의 데이터 구조는 다음과 같습니다.

<code>Food
<span>|</span><span>|---Fruit</span><span>|    |</span><span>|    |---Red</span><span>|    |    |</span><span>|    |    |--Cherry</span><span>|    |</span><span>|    +---Yellow</span><span>|          |</span><span>|          +--Banana</span><span>|</span>
+---Meat
      <span>|--Beef</span>
      +--Pork</code>

영어가 엉망인 PHP 매니아를 처리하기 위해

<code>Food  : 食物
Fruit : 水果
Red   : 红色
<span>Cherry:</span> 樱桃
<span>Yellow:</span> 黄色
<span>Banana:</span> 香蕉
Meat  : 肉类
Beef  : 牛肉
Pork  : 猪肉</code>

3. 구현

1. 인접 목록 모델

이 모델은 자주 사용되며 많은 튜토리얼과 책에서 소개되었습니다. 이 노드의 부모 노드를 나타내기 위해 각 노드에 부모 속성을 추가하여 플랫 테이블을 통해 전체 트리 구조를 설명합니다. 이 원칙에 따라 예제의 데이터는 다음 표로 변환될 수 있습니다.
코드는 다음과 같습니다.

<code><span>+-----------------------+</span><span>|   parent |    name    |
+-----------------------+</span>
|          |    Food    |
|   Food   |   Fruit    |
|   Fruit  |    Green   |
|   Green  |    Pear    |
|   Fruit  |    Red     |
|   Red    |    Cherry  |
|   Fruit  |    Yellow  |
|   Yellow |    Banana  |
|   Food   |    Meat    |
|   Meat   |    Beef    |
<span>|   Meat   |    Pork    |
+-----------------------+</span></code>

Pear는 Green의 하위 노드이고 Green은 Fruit의 하위 노드임을 알 수 있습니다. 루트 노드 'Food'에는 상위 노드가 없습니다. 이 문제를 간단하게 설명하기 위해 이 예에서는 레코드를 나타내는 데 이름만 사용됩니다. 실제 데이터베이스에서는 각 노드를 식별하기 위해 숫자 ID를 사용해야 합니다. 데이터베이스 테이블 구조는 아마도 id, parent_id, name, 설명과 같아야 합니다.
이러한 테이블을 사용하면 데이터베이스를 통해 전체 다단계 트리 구조를 저장할 수 있습니다.

다단계 트리를 표시합니다. 이러한 다단계 구조를 표시하려면 재귀 함수가 필요합니다.
코드는 다음과 같습니다.

<code><span><span><?php</span><span>// $parent is the parent of the children we want to see</span><span>// $level is increased when we go deeper into the tree,</span><span>//        used to display a nice indented tree</span><span><span>function</span><span>display_children</span><span>(<span>$parent</span>, <span>$level</span>)</span> {</span><span>// 获得一个 父节点 $parent 的所有子节点</span><span>$result</span> = mysql_query(<span>"
        SELECT name
        FROM tree
        WHERE parent = '"</span> . <span>$parent</span> . <span>"'
        ;"</span>
    );
    <span>// 显示每个子节点</span><span>while</span> (<span>$row</span> = mysql_fetch_array(<span>$result</span>)) {
        <span>// 缩进显示节点名称</span><span>echo</span> str_repeat(<span>'  '</span>, <span>$level</span>) . <span>$row</span>[<span>'name'</span>] . <span>"\n"</span>;
        <span>//再次调用这个函数显示子节点的子节点</span>
        display_children(<span>$row</span>[<span>'name'</span>], <span>$level</span>+<span>1</span>);
    }
}
<span>?></span></span></code>

전체 구조의 루트 노드(Food)에서 이 함수를 사용하면 Food가 루트 노드이자 상위 노드이므로 전체 다단계 트리 구조를 인쇄할 수 있습니다. 비어 있으므로 다음과 같이 호출하십시오: display_children(",0). 전체 트리의 내용이 표시됩니다:

<code>Food
    Fruit
        <span>Red</span>
            Cherry
        <span>Yellow</span>
            Banana
    Meat
        Beef
        Pork</code>

과일 부분에서는 다음을 호출할 수 있습니다: display_children('Fruit ',0);

거의 동일한 방법을 사용하여 루트 노드에서 모든 노드까지의 경로를 알 수 있습니다. 예를 들어 Cherry의 경로는 "Food >입니다. ;; Fruit >; Red". 경로의 경우 가장 깊은 수준인 "Cherry"에서 시작하여 상위 노드 "Red"를 쿼리하여 경로에 추가한 다음 Red의 상위 노드를 쿼리하여 추가해야 합니다. 최상위 수준 "Food"까지의 코드는 다음과 같습니다.

<code><span><span><?php</span><span>// $node 是那个最深的节点</span><span><span>function</span><span>get_path</span><span>(<span>$node</span>)</span> {</span><span>// 查询这个节点的父节点</span><span>$result</span> = mysql_query(<span>"
        SELECT parent
        FROM tree
        WHERE name = '"</span> . <span>$node</span> .<span>"'
        ;"</span>
    );
    <span>$row</span> = mysql_fetch_array(<span>$result</span>);
    <span>// 用一个数组保存路径</span><span>$path</span> = <span>array</span>();
    <span>// 如果不是根节点则继续向上查询</span><span>// (根节点没有父节点)</span><span>if</span> (<span>$row</span>[<span>'parent'</span>] != <span>''</span>) {
        <span>// the last part of the path to $node, is the name</span><span>// of the parent of $node</span><span>$path</span>[] = <span>$row</span>[<span>'parent'</span>];
        <span>// we should add the path to the parent of this node</span><span>// to the path</span><span>$path</span> = array_merge(get_path(<span>$row</span>[<span>'parent'</span>]), <span>$path</span>);
    }
    <span>// return the path</span><span>return</span><span>$path</span>;
}
<span>?></span></span></code>

"Cherry"에 이 함수를 사용하는 경우: print_r(get_path('Cherry')) , 다음과 같은 배열을 얻게 됩니다:

<code><span>Array</span> (
    [<span>0</span>] => Food
    [<span>1</span>] => Fruit
    [<span>2</span>] => Red
)</code>

원하는 형식으로 인쇄하는 방법은 귀하에게 달려 있습니다.

단점:
이 방법은 매우 간단하고 이해하기 쉽고 사용하기 쉽습니다. 그러나 몇 가지 단점이 있습니다. 주된 이유는 실행 속도가 매우 느리기 때문이며, 각 노드마다 데이터베이스 쿼리가 필요하기 때문에 데이터 양이 많을 경우 트리를 완성하기 위해 많은 쿼리가 필요합니다. 또한, 재귀 작업이 필요하기 때문에 각 재귀 수준마다 일정량의 메모리를 점유해야 하므로 공간 활용 효율성이 상대적으로 낮습니다.

2. 선주문 트리 순회 알고리즘

이제 재귀 계산을 사용하지 않는 또 다른 빠른 방법을 살펴보겠습니다. 이것이 수정된 선주문 트리 순회 알고리즘입니다.
이 방법은 위의 방법에 비해 노출도가 낮고, 처음 사용 시에는 이해하기 쉽지 않습니다. 그러나 이 방법은 재귀 쿼리 알고리즘을 사용하지 않기 때문에 쿼리 효율성이 더 높습니다.

먼저 다음과 같이 종이에 다단계 데이터를 그리고, 루트 노드인 Food의 왼쪽에 1을 쓰고, 계속해서 트리를 내려가서 Fruit의 왼쪽에 2를 쓰고 계속해서 전진합니다. 전체 트리의 가장자리를 따라 왼쪽과 오른쪽에 숫자를 각 노드에 표시합니다. 마지막 숫자는 Food 오른쪽에 표시된 18입니다. 아래 그림에서 숫자로 표시된 전체 다층 구조를 볼 수 있습니다. (모르겠어요? 손가락으로 숫자를 가리키며 1부터 18까지 세어보면 이해가 됩니다. 그래도 모르면 다시 세면서 손가락 움직임에 주의하세요.)
이 숫자는 각 노드 사이의 관계를 나타냅니다. "Red"의 숫자는 3과 6이며, 이는 "Food" 1~18의 하위 노드입니다. 마찬가지로 왼쪽 값이 2보다 크고 오른쪽 값이 11보다 작은 모든 노드가 "Fruit" 2-11의 자손 노드임을 알 수 있습니다.
다음은 코드입니다.

<code><span>1</span> Food <span>18</span><span>|</span>
            +------------------------------+
            <span>|                              |</span><span>2</span> Fruit <span>11</span><span>12</span> Meat <span>17</span><span>|                              |</span>
    +-------------+                 +------------+
    <span>|             |                 |            |</span><span>3</span> Red <span>6</span><span>7</span> Yellow <span>10</span><span>13</span> Beef <span>14</span><span>15</span> Pork <span>16</span><span>|             |</span><span>4</span> Cherry <span>5</span><span>8</span> Banana <span>9</span></code>

이렇게 하면 왼쪽 값과 오른쪽 값을 통해 전체 트리 구조를 데이터베이스에 저장할 수 있습니다. 계속하기 전에 아래의 컴파일된 데이터 테이블을 살펴보겠습니다.
코드는 다음과 같습니다.

<code><span>+----------+</span>------------<span>+-----+</span>-----+
<span>|  parent  |    name    | lft | rgt |
+----------+------------+-----+-----+</span>
|          |    Food    | 1   | 18  |
|   Food   |   Fruit    | 2   | 11  |
|   Fruit  |    Red     | 3   |  6  |
|   Red    |    Cherry  | 4   |  5  |
|   Fruit  |    Yellow  | 7   | 10  |
|   Yellow |    Banana  | 8   |  9  |
|   Food   |    Meat    | 12  | 17  |
|   Meat   |    Beef    | 13  | 14  |
<span>|   Meat   |    Pork    | 15  | 16  |
+----------+------------+-----+-----+</span></code>

注意：由于”left”和”right”在 SQL中有特殊的意义，所以我们需要用”lft”和”rgt”来表示左右字段。另外这种结构中不再需要”parent”字段来表示树状结构。也就是说下面这样的表结构就足够了。
以下是代码：

<code><span>+------------+</span>-----<span>+-----+</span><span>|    name    | lft | rgt |
+------------+-----+-----+</span>
|    Food    | 1   | 18  |
|    Fruit   | 2   | 11  |
|    Red     | 3   |  6  |
|    Cherry  | 4   |  5  |
|    Yellow  | 7   | 10  |
|    Banana  | 8   |  9  |
|    Meat    | 12  | 17  |
|    Beef    | 13  | 14  |
<span>|    Pork    | 15  | 16  |
+------------+-----+-----+</span></code>

好了我们现在可以从数据库中获取数据了，例如我们需要得到”Fruit”项下的所有所有节点就可以这样写查询语句：

<code><span><span>SELECT</span> * <span>FROM</span> tree <span>WHERE</span> lft BETWEEN <span>2</span><span>AND</span><span>11</span>;</span></code>

这个查询得到了以下的结果。
以下是代码：

<code><span>+------------+</span>-----<span>+-----+</span><span>|    name    | lft | rgt |
+------------+-----+-----+</span>
|    Fruit   | 2   | 11  |
|    Red     | 3   |  6  |
|    Cherry  | 4   |  5  |
|    Yellow  | 7   | 10  |
<span>|    Banana  | 8   |  9  |
+------------+-----+-----+</span></code>

看到了吧，只要一个查询就可以得到所有这些节点。为了能够像上面的递归函数那样显示整个树状结构，我们还需要对这样的查询进行排序。用节点的左值进行排序：

<code><span><span>SELECT</span> * <span>FROM</span> tree <span>WHERE</span> lft BETWEEN <span>2</span><span>AND</span><span>11</span><span>ORDER</span><span>BY</span> lft <span>ASC</span>;</span></code>

剩下的问题如何显示层级的缩进了。
以下是代码：

<code><span><span><?php</span><span><span>function</span><span>display_tree</span><span>(<span>$root</span>)</span> {</span><span>// 得到根节点的左右值</span><span>$result</span> = mysql_query(<span>"
        SELECT lft, rgt
        FROM tree
        WHERE name = '"</span> . <span>$root</span> . <span>"'
        ;"</span>
    );
    <span>$row</span> = mysql_fetch_array(<span>$result</span>);
    <span>// 准备一个空的右值堆栈</span><span>$right</span> = <span>array</span>();
    <span>// 获得根基点的所有子孙节点</span><span>$result</span> = mysql_query(<span>"
        SELECT name, lft, rgt
        FROM tree
        WHERE lft BETWEEN '"</span> . <span>$row</span>[<span>'lft'</span>] . <span>"' AND '"</span> . <span>$row</span>[<span>'rgt'</span>] .<span>"'
        ORDER BY lft ASC
        ;"</span>
    );
    <span>// 显示每一行</span><span>while</span> (<span>$row</span> = mysql_fetch_array(<span>$result</span>)) {
        <span>// only check stack if there is one</span><span>if</span> (count(<span>$right</span>) > <span>0</span>) {
            <span>// 检查我们是否应该将节点移出堆栈</span><span>while</span> (<span>$right</span>[count(<span>$right</span>) - <span>1</span>] < <span>$row</span>[<span>'rgt'</span>]) {
                array_pop(<span>$right</span>);
            }
        }
        <span>// 缩进显示节点的名称</span><span>echo</span> str_repeat(<span>'  '</span>,count(<span>$right</span>)) . <span>$row</span>[<span>'name'</span>] . <span>"\n"</span>;
        <span>// 将这个节点加入到堆栈中</span><span>$right</span>[] = <span>$row</span>[<span>'rgt'</span>];
    }
}
<span>?></span></span></code>

如果你运行一下以上的函数就会得到和递归函数一样的结果。只是我们的这个新的函数可能会更快一些，因为只有2次数据库查询。
要获知一个节点的路径就更简单了，如果我们想知道Cherry 的路径就利用它的左右值4和5来做一个查询。

<code><span>SELECT</span> name <span>FROM</span> tree <span>WHERE</span> lft < <span>4</span><span>AND</span> rgt >; <span>5</span><span>ORDER</span><span>BY</span> lft <span>ASC</span>;</code>

这样就会得到以下的结果：
以下是代码：

<code><span>+------------+</span><span>|    name    |
+------------+</span>
|    Food    |
|    Fruit   |
<span>|    Red     |
+------------+</span></code>

那么某个节点到底有多少子孙节点呢？很简单，子孙总数=(右值-左值-1)/2

<code>descendants = (<span>right</span> – <span>left</span> - <span>1</span>) / <span>2</span></code>

不相信？自己算一算啦。
用这个简单的公式，我们可以很快的算出”Fruit 2-11”节点有4个子孙节点，而”Banana 8-9”节点没有子孙节点，也就是说它不是一个父节点了。
很神奇吧？虽然我已经多次用过这个方法，但是每次这样做的时候还是感到很神奇。
这的确是个很好的办法，但是有什么办法能够帮我们建立这样有左右值的数据表呢？这里再介绍一个函数给大家，这个函数可以将name和parent结构的表自动转换成带有左右值的数据表。
以下是代码：

<code><span><?php</span><span><span>function</span><span>rebuild_tree</span><span>(<span>$parent</span>, <span>$left</span>)</span> {</span><span>// the right value of this node is the left value + 1</span><span>$right</span> = <span>$left</span>+<span>1</span>;
    <span>// get all children of this node</span><span>$result</span> = mysql_query(<span>"
        SELECT name
        FROM tree
        WHERE parent = '"</span> . <span>$parent</span> . <span>"'
        ;"</span>
    );
    <span>while</span> (<span>$row</span> = mysql_fetch_array(<span>$result</span>)) {
        <span>// recursive execution of this function for each</span><span>// child of this node</span><span>// $right is the current right value, which is</span><span>// incremented by the rebuild_tree function</span><span>$right</span> = rebuild_tree(<span>$row</span>[<span>'name'</span>], <span>$right</span>);
    }
    <span>// we've got the left value, and now that we've processed</span><span>// the children of this node we also know the right value</span>
    mysql_query(<span>"
        UPDATE tree
        SET
            lft = '"</span> . <span>$left</span> . <span>"',
            rgt= '"</span> . <span>$right</span> . <span>"'
        WHERE name = '"</span> . <span>$parent</span> . <span>"'
        ;"</span>
    );
    <span>// return the right value of this node + 1</span><span>return</span><span>$right</span> + <span>1</span>;
}
<span>?></span></code>

当然这个函数是一个递归函数，我们需要从根节点开始运行这个函数来重建一个带有左右值的树

<code><span>rebuild_tree(<span>'Food'</span>,<span>1</span>)</span>;</code>

这个函数看上去有些复杂，但是它的作用和手工对表进行编号一样，就是将立体多层结构的转换成一个带有左右值的数据表。

那么对于这样的结构我们该如何增加，更新和删除一个节点呢？
增加一个节点一般有两种方法：
第一种，保留原有的name 和parent结构，用老方法向数据中添加数据，每增加一条数据以后使用rebuild_tree函数对整个结构重新进行一次编号。
第二种，效率更高的办法是改变所有位于新节点右侧的数值。举例来说：我们想增加一种新的水果”Strawberry”（草莓）它将成为”Red”节点的最后一个子节点。首先我们需要为它腾出一些空间。”Red”的右值应当从6改成8，”Yellow 7-10 “的左右值则应当改成 9-12。依次类推我们可以得知，如果要给新的值腾出空间需要给所有左右值大于5的节点（5 是”Red”最后一个子节点的右值）加上2。所以我们这样进行数据库操作：

<code><span><span>UPDATE</span> tree <span>SET</span> rgt = rgt + <span>2</span><span>WHERE</span> rgt > <span>5</span>;</span><span><span>UPDATE</span> tree <span>SET</span> lft = lft + <span>2</span><span>WHERE</span> lft > <span>5</span>;</span></code>

这样就为新插入的值腾出了空间，现在可以在腾出的空间里建立一个新的数据节点了，它的左右值分别是6和7

<code><span><span>INSERT</span><span>INTO</span> tree <span>SET</span> lft=<span>6</span>, rgt=<span>7</span>, name=<span>'Strawberry'</span>;</span></code>

再做一次查询看看吧！怎么样？很快吧。

四、结语

好了，现在你可以用两种不同的方法设计你的多级数据库结构了，采用何种方式完全取决于你个人的判断，但是对于层次多数量大的结构我更喜欢第二种方法。如果查询量较小但是需要频繁添加和更新的数据，则第一种方法更为简便。
另外，如果数据库支持的话你还可以将rebuild_tree()和腾出空间的操作写成数据库端的触发器函数，在插入和更新的时候自动执行，这样可以得到更好的运行效率，而且你添加新节点的SQL语句会变得更加简单。

http://www.cnblogs.com/guowei1027/archive/2009/12/14/1623507.html

以上就介绍了无限分类左右值实现算法，包括了方面的内容，希望对PHP教程有兴趣的朋友有所帮助。

성명：

이전 기사：PHP跨域Ajax解决方案다음 기사：PHP错误：iconv Detected an illegal character

무한분류 좌우값 구현 알고리즘

관련 기사