Làm thế nào để bạn sắp xếp một cây được lưu trữ bằng cách sử dụng mô hình tập hợp lồng nhau?

Question

Khi tôi đề cập đến mô hình tập lồng nhau, tôi có nghĩa là những gì được mô tả here.

Tôi cần phải xây dựng một hệ thống mới. Kể từ khi mô hình tập lồng nhau được tối ưu hóa cho lần đọc thay vì viết, tôi quyết định sử dụng nó. Thật không may trong quá trình nghiên cứu và thử nghiệm các bộ lồng nhau của tôi, tôi đã gặp phải vấn đề về cách hiển thị cây phân cấp với các nút được sắp xếp. Ví dụ nếu tôi có hệ thống phân cấp:

root 
    finances 
     budgeting 
      fy08 
    projects 
     research 
     fabrication 
     release 
    trash 

Tôi muốn điều đó được sắp xếp sao cho nó sẽ hiển thị như sau:

root 
    finances 
     budgeting 
      fy08 
    projects 
     fabrication 
     release 
     research 
    trash 

Chú ý rằng việc chế tạo xuất hiện trước nghiên cứu. Dù sao, sau một tìm kiếm dài, tôi thấy câu trả lời như "lưu trữ cây trong một mảng đa chiều và sắp xếp nó" và "đặt cây và quay trở lại vào mô hình tập hợp lồng nhau của bạn" (Tôi đang ẩn dụ ..). .). Dù bằng cách nào, các giải pháp đầu tiên là một sự lãng phí khủng khiếp của RAM và CPU, đó là cả hai nguồn tài nguyên rất hữu hạn ... Giải pháp thứ hai chỉ trông giống như rất nhiều mã đau đớn.

Bất kể, tôi đã có thể tìm ra cách để (sử dụng mô hình bộ lồng nhau):

1. Bắt đầu một cây mới trong SQL
2. Chèn một nút như một đứa trẻ của nút khác trong cây
3. Chèn một nút sau nút anh chị em trong cây
4. Kéo toàn bộ cây có cấu trúc phân cấp từ SQL
5. Kéo một cây con từ một nút cụ thể (bao gồm gốc) trong phân cấp có hoặc không có giới hạn chiều sâu
6. Tìm phụ huynh của bất kỳ nút trong cây

Vì vậy, tôi đã tìm # 5 và # 6 có thể được sử dụng để thực hiện sắp xếp tôi muốn, và nó cũng có thể được sử dụng để xây dựng lại cây theo thứ tự sắp xếp như tốt.

Tuy nhiên, bây giờ tôi đã xem xét tất cả những điều này tôi đã học được để làm tôi thấy rằng # 3, # 5 và # 6 có thể được sử dụng cùng nhau để thực hiện chèn được sắp xếp. Nếu tôi đã sắp xếp chèn nó luôn luôn được sắp xếp. Tuy nhiên, nếu tôi thay đổi tiêu chí sắp xếp hoặc tôi muốn một thứ tự sắp xếp khác, tôi sẽ quay lại hình vuông.

Có thể đây chỉ là giới hạn của mô hình tập hợp lồng nhau không? Việc sử dụng nó có ức chế việc phân loại truy vấn đầu ra không?

Answer 1

Tôi nghĩ đây thực sự là một hạn chế của mô hình tập hợp lồng nhau. Bạn không thể dễ dàng sắp xếp các nút con trong nút cha tương ứng của chúng, bởi vì thứ tự của tập kết quả là cần thiết để tái tạo lại cấu trúc cây.

Tôi nghĩ đó có lẽ là cách tiếp cận tốt nhất để giữ cho cây được sắp xếp khi chèn, cập nhật hoặc xóa các nút. Điều này thậm chí làm cho các truy vấn rất nhanh, đó là một trong những mục tiêu chính của cấu trúc dữ liệu này. Nếu bạn thực hiện các thủ tục lưu trữ cho tất cả các hoạt động, nó rất dễ sử dụng.

Bạn cũng có thể đảo ngược thứ tự sắp xếp của cây được phân loại. Bạn chỉ cần sử dụng ORDER BY node.rgt DESC thay vì ORDER BY node.lft ASC.

Nếu bạn thực sự cần hỗ trợ tiêu chí sắp xếp khác, bạn có thể triển khai bằng cách thêm chỉ mục thứ hai lft và rgt vào mỗi nút và giữ nó được sắp xếp theo các tiêu chí khác trên mỗi lần chèn/cập nhật/xóa.

Answer 2

Vâng, đó là giới hạn của mô hình tập lồng nhau, vì các tập lồng nhau là một đại diện được sắp xếp trước của một hệ thống phân cấp. Việc đặt hàng trước này là lý do để đọc nhanh. Mô hình kề, cũng được mô tả trên trang bạn liên kết đến, cung cấp cho việc phân loại và lọc linh hoạt nhất nhưng có tác động hiệu suất đáng kể.

Cách tiếp cận ưa thích của tôi để chèn và di chuyển trong bộ lồng nhau là xử lý nhánh bị ảnh hưởng như trong mô hình kề: Lấy danh sách các anh chị em mới; tìm đúng vị trí trong danh sách cho nút mới; và xây dựng các báo cáo cập nhật cần thiết (đó là bit mà bạn thực sự phải cẩn thận). Đối với việc thay đổi tiêu chí đặt hàng của bạn: Đó là một công việc hàng loạt, vì vậy bạn có thể đủ khả năng để thổi một số RAM và CPU vào nó, câu trả lời linh hoạt nhất sẽ là phá vỡ đại diện tập hợp lồng nhau vào một đại diện kề và xây dựng lại bộ lồng nhau từ adjacency dựa trên tiêu chí mới.

Answer 3

Tôi vừa viết xong những điều sau đây có tác dụng đối với tôi khi sắp xếp toàn bộ cây được đặt lồng nhau.

Sắp xếp (lý tưởng) yêu cầu chế độ xem danh sách cấp hiện tại của mỗi nút trong cây và thủ tục hoán đổi hai nút - cả hai đều được bao gồm bên dưới, mã trao đổi anh chị em đến từ cuốn sách của Joe Celkos 'Tree & Hierarchies' mà tôi đặc biệt khuyên dùng cho bất kỳ ai sử dụng bộ lồng nhau.

Các loại có thể được thay đổi trong 'INSERT INTO @t' tuyên bố, đây là một loại chữ đơn giản trên 'Tên'

Đây có thể là một cách nghèo để làm việc đó đặc biệt là sử dụng con trỏ cho bộ dựa mã nhưng như tôi nói nó làm việc cho tôi, hy vọng nó sẽ giúp.

UPDATE:

Mã dưới đây sẽ hiển thị các phiên bản mà không sử dụng cusor. Tôi thấy về cải thiện tốc độ 10x

CREATE VIEW dbo.tree_view 

AS 

SELECT t2.NodeID,t2.lft,t2.rgt ,t2.Name, COUNT(t1.NodeID) AS level 
FROM dbo.tree t1,dbo.tree t2 
WHERE t2.lft BETWEEN t1.lft AND t1.rgt 
GROUP BY t2.NodeID,t2.lft,t2.rgt,t2.Name 

GO 

---------------------------------------------- 

    DECLARE @CurrentNodeID int 
DECLARE @CurrentActualOrder int 
DECLARE @CurrentRequiredOrder int 
DECLARE @DestinationNodeID int 
DECLARE @i0 int 
DECLARE @i1 int 
DECLARE @i2 int 
DECLARE @i3 int 

DECLARE @t TABLE (TopLft int,NodeID int NOT NULL,lft int NOT NULL,rgt int NOT NULL,Name varchar(50),RequiredOrder int NOT NULL,ActualOrder int NOT NULL) 


INSERT INTO @t (toplft,NodeID,lft,rgt,Name,RequiredOrder,ActualOrder) 
    SELECT tv2.lft,tv1.NodeID,tv1.lft,tv1.rgt,tv1.Name,ROW_NUMBER() OVER(PARTITION BY tv2.lft ORDER BY tv1.ColumnToSort),ROW_NUMBER() OVER(PARTITION BY tv2.lft ORDER BY tv1.lft ASC) 
    FROM dbo.tree_view tv1 
    LEFT OUTER JOIN dbo.tree_view tv2 ON tv1.lft > tv2.lft and tv1.lft < tv2.rgt and tv1.level = tv2.level+1 
    WHERE tv2.rgt > tv2.lft+1 

    DELETE FROM @t where ActualOrder = RequiredOrder 


WHILE EXISTS(SELECT * FROM @t WHERE ActualOrder <> RequiredOrder) 
BEGIN 


    SELECT Top 1 @CurrentNodeID = NodeID,@CurrentActualOrder = ActualOrder,@CurrentRequiredOrder = RequiredOrder 
    FROM @t 
    WHERE ActualOrder <> RequiredOrder 
    ORDER BY toplft,requiredorder 

    SELECT @DestinationNodeID = NodeID 
    FROM @t WHERE ActualOrder = @CurrentRequiredOrder AND TopLft = (SELECT TopLft FROM @t WHERE NodeID = @CurrentNodeID) 

    SELECT @i0 = CASE WHEN c.lft < d.lft THEN c.lft ELSE d.lft END, 
      @i1 = CASE WHEN c.lft < d.lft THEN c.rgt ELSE d.rgt END, 
      @i2 = CASE WHEN c.lft < d.lft THEN d.lft ELSE c.lft END, 
      @i3 = CASE WHEN c.lft < d.lft THEN d.rgt ELSE c.rgt END 
    FROM dbo.tree c 
    CROSS JOIN dbo.tree d 
    WHERE c.NodeID = @CurrentNodeID AND d.NodeID = @DestinationNodeID 

    UPDATE dbo.tree 
    SET lft = CASE WHEN lft BETWEEN @i0 AND @i1 THEN @i3 + lft - @i1 
        WHEN lft BETWEEN @i2 AND @i3 THEN @i0 + lft - @i2 
      ELSE @i0 + @i3 + lft - @i1 - @i2 
      END, 
     rgt = CASE WHEN rgt BETWEEN @i0 AND @i1 THEN @i3 + rgt - @i1 
        WHEN rgt BETWEEN @i2 AND @i3 THEN @i0 + rgt - @i2 
      ELSE @i0 + @i3 + rgt - @i1 - @i2 
      END 
    WHERE lft BETWEEN @i0 AND @i3 
    AND @i0 < @i1 
    AND @i1 < @i2 
    AND @i2 < @i3 

    UPDATE @t SET actualorder = @CurrentRequiredOrder where NodeID = @CurrentNodeID 
    UPDATE @t SET actualorder = @CurrentActualOrder where NodeID = @DestinationNodeID 

    DELETE FROM @t where ActualOrder = RequiredOrder 

END 

Answer 4

Tôi đã sử dụng Bộ lồng nhau rất nhiều và tôi đã gặp phải sự cố tương tự thường xuyên. Những gì tôi làm, và những gì tôi muốn giới thiệu, là chỉ cần không sắp xếp các mục trong cơ sở dữ liệu. Thay vào đó, hãy sắp xếp chúng trong giao diện người dùng. Sau khi bạn kéo tất cả các nút từ DB, bạn có thể phải chuyển đổi chúng thành một số cấu trúc dữ liệu phân cấp. Trong cấu trúc đó, sắp xếp tất cả các mảng chứa các nút con của nút.

Ví dụ: nếu giao diện người dùng của bạn là ứng dụng Flex và con của nút được lưu trữ trong ICollectionView, bạn có thể sử dụng thuộc tính sắp xếp để chúng hiển thị theo cách bạn muốn.

Ví dụ khác, nếu giao diện của bạn là một số đầu ra từ tập lệnh PHP, bạn có thể có con của mỗi nút trong một mảng và sử dụng các hàm sắp xếp mảng của PHP để thực hiện sắp xếp của bạn.

Tất nhiên, điều này chỉ hoạt động nếu bạn không cần các mục nhập db thực sự được sắp xếp, nhưng phải không?

Answer 5

Tôi tin rằng, trong trường hợp của bạn, nơi các nút bạn muốn trao đổi không có bất kỳ con cháu nào, bạn có thể chỉ cần hoán đổi các giá trị lft và rgt xung quanh.Xem xét cây này:

A 
/ \ 
B  C 
    /\ 
    D E 

Điều này có thể biến thành nhóm này của bộ lồng nhau:

1 A 10 
2 B 3 
4 C 9 
5 D 6 
7 E 8 

Bây giờ xem xét bạn muốn trao đổi D và E. Các bộ lồng nhau sau đây là hợp lệ và D và E được hoán đổi :

1 A 10 
2 B 3 
4 C 9 
7 D 8 
5 E 6 

Nút hoán đổi có subtrees không thể thực hiện theo cách này, tất nhiên, vì bạn cũng cần phải cập nhật giá trị lft và rgt của trẻ em.

Answer 6

Bạn có thể sắp xếp lại khi bạn kết xuất. Tôi giải thích hiển thị tại đây How to render all records from a nested set into a real html tree

Answer 7

Sắp xếp các bộ lồng nhau không có giới hạn và không khó. Chỉ cần sắp xếp bởi Bower LEFT (neo, bất cứ điều gì) và nó được thực hiện. Nếu bạn có LEVEL cho mỗi nút, bạn cũng có thể kéo thụt lề chính xác dựa trên Cấp độ.

Answer 8

Xem giải pháp đơn giản của tôi từ phương pháp lớp học của tôi. $ this-> table-> order là Nette framework code để lấy dữ liệu từ DB.

$tree = Array(); 
$parents = Array(); 
$nodes = $this->table->order('depth ASC, parent_id ASC, name ASC'); 
$i = 0; 
$depth = 0; 
$parent_id = 0; 

foreach($nodes as $node) { 
    if($depth < $node->depth || $parent_id < $node->parent_id) { 
     $i = $parents["{$node->parent_id}"] + 1; 
    } 
    $tree[$i] = $node; 
    $parents["{$node->id}"] = $i; 
    $depth = $node->depth; 
    $parent_id = $node->parent_id; 
    $i += (($node->rgt - $node->lft - 1)/2) + 1; 
} 
ksort($tree);