이진 트리 순회... 무한 계층형 트리

배움이 짧아 트리를 쭈욱 파고 들다가, 이진 트리 순회라는 것을 알게 되었습니다.

배우진 않았지만, 늘상 사용하던 알고리즘의 하나였는데요. 자세히 보니까 mysql between 을 활용해서

계층형 트리 구조를 만들수 있는 것을 알게 되었습니다.

between 은 " 필드 between min and max " 으로만 알고 있었는데 group by 와 만나면 mysql 로

계층형 트리 구조를 구현할 수 있게 되더군요.

---- 테이블 구조

CREATE TABLE nested_category (
        category_id INT AUTO_INCREMENT PRIMARY KEY,
        name VARCHAR(20) NOT NULL,
        lft INT NOT NULL,
        rgt INT NOT NULL
);

INSERT INTO nested_category VALUES(1,'ELECTRONICS',1,20),(2,'TELEVISIONS',2,9),(3,'TUBE',3,4),
 (4,'LCD',5,6),(5,'PLASMA',7,8),(6,'PORTABLE ELECTRONICS',10,19),(7,'MP3 PLAYERS',11,14),(8,'FLASH',12,13),
 (9,'CD PLAYERS',15,16),(10,'2 WAY RADIOS',17,18);

---- 출력

SELECT CONCAT( REPEAT(' ', COUNT(parent.name) - 1), node.name ) AS name
FROM nested_category AS node,
        nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name, node.lft /* < 이 부분이 중요 네임이 중복 시 하위 출력이 안됨 */
ORDER BY node.lft

---- 하위 추가

LOCK TABLE nested_category WRITE;

SELECT @myRight := rgt FROM nested_category
WHERE category_id = ;

UPDATE nested_category SET rgt = rgt + 2 WHERE rgt > @myRight;
UPDATE nested_category SET lft = lft + 2 WHERE lft > @myRight;

INSERT INTO nested_category(name, lft, rgt) VALUES('GAME CONSOLES', @myRight + 1, @myRight + 2);

UNLOCK TABLES;

---- 자식 추가

LOCK TABLE nested_category WRITE;

SELECT @myLeft := lft FROM nested_category

WHERE category_id = ;

UPDATE nested_category SET rgt = rgt + 2 WHERE rgt > @myLeft;
UPDATE nested_category SET lft = lft + 2 WHERE lft > @myLeft;

INSERT INTO nested_category(name, lft, rgt) VALUES('FRS 22', @myLeft + 1, @myLeft + 2);

UNLOCK TABLES;

---- 노드 삭제

LOCK TABLE nested_category WRITE;

SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1
FROM nested_category
WHERE category_id = ;

DELETE FROM nested_category WHERE lft BETWEEN @myLeft AND @myRight;

UPDATE nested_category SET rgt = rgt - @myWidth WHERE rgt > @myRight;
UPDATE nested_category SET lft = lft - @myWidth WHERE lft > @myRight;

UNLOCK TABLES;

위 기능을 서핑을 통해서 찾아 봤습니다. 유용할것 같아서 가져와 봤습니다.

위 기능으로 계층형 무한 복사, 이동, 추가 가 가능할 것 같습니다.

5천개의 트리가 있을때 select 가 느릴것 같은데, 속도면에서는 어떨지 모르겠네요.

소스 출처 : https://hmjkor.tistory.com/472