YOMEDIA
Qui tắc duyệt cây đa cấp trên MS SQL Server
Chia sẻ: Abcdef_46 Abcdef_46
| Ngày:
| Loại File: PDF
| Số trang:7
57
lượt xem
2
download
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
Qui tắc duyệt cây đề cập ở đây là theo chiều sâu, duyệt từ trái sang phải, thứ tự duyệt được thể hiện bằng các chữ số bên trong các node ở hình 1. Bảng Tree lưu trữ thông tin của cây đa cấp có cấu trúc như sau: Column Name NodeID NodeName ParentID WoodenLeg Data Type Int varchar Int varchar Size 20 100 Allow Null No No Yes Yes Description Khóa chính của bảng Tree Tên node Mã của node cha gần nhất Cột giả hỗ trợ khi sắp xếp dữ liệu
...
AMBIENT/
Chủ đề:
Nội dung Text: Qui tắc duyệt cây đa cấp trên MS SQL Server
- Duyệt cây đa cấp trên MS SQL Server
Qui tắc duyệt cây đề cập ở đây là theo chiều sâu, duyệt từ trái sang phải, thứ tự
duyệt được thể hiện bằng các chữ số bên trong các node ở hình 1.
Bảng Tree lưu trữ thông tin của cây đa cấp có cấu trúc nh ư sau:
Column Data Allow
Size Description
Name Type Null
Khóa chính c ủa bảng Tree
NodeID Int No
NodeName varchar 20 No Tên node
Mã của node cha gần nhất
ParentID Int Yes
Cột giả hỗ trợ khi sắp xếp dữ
WoodenLeg varchar 100 Yes
liệu
Scrip tạo bảng Tree như sau:
Create Table Tree(
NodeID int Primary Key,
NodeName varchar(20) Not Null,
ParentID int Null,
WoodenLeg varchar(100) Null
);
Dữ liệu trong bảng Tree mô tả cây đa cấp ở hình 1 được thể hiện ở hình 2. Qui
tắc tạo dữ liệu như sau:
NodeName NodeName ParentID WoodenLeg
1 Root Node Null "1"
2 Node 1 1 "12"
3 Node 2 1 "13"
4 Node 3 1 "14"
5 Node 4 1 "15"
6 Node A 2 "126"
- 7 Node B 2 "127"
8 Node C 3 "138"
9 Node D 3 "139"
10 Node E 3 "1310"
11 Node F 5 "1511"
12 Node G 5 "1512"
13 Node X 11 "151113"
14 Node Y 11 "151114"
15 Node Z 11 "151115"
Hình 2: Dữ liệu mô tả cấu trúc cây đa cấp
(Đừng quan tâm đến giá trị column
WoodenLeg, tôi sẽ giải thích ở phần sau)
* NodeID của node cha sẽ nhỏ hơn NodeID của node con. Đối với các node
cùng cấp, NodeID của node trái sẽ nhỏ h ơn NodeID c ủa node phải.
Đọc đến đây, các bạn có thể thắc mắc nếu NodeID của một cây có sẵn có giá
trị không thoả điều kiện trên thì chúng ta có sắp xếp được hay không. Câu trả
lời là hoàn toàn có thể, vì khi đó chúng ta có thể tạo thêm một column mới với
các giá trị thoả điều kiện. Vì muốn giữ tính đơn giản cho bài viết nên cho phép
tôi không nêu ra cách tính cho trường hợp này. Nếu có bất kỳ thắc mắc gì, các
bạn có thể liên hệ trực tiếp với tôi.
* Đối với node gốc (Root Node) thì ParentID = Null. Các node th ứ cấp còn lại
sẽ có ParentID bằng NodeID của node cha gần nhất.
Chúng ta dễ dàng nhận thấy, không thể sử dụng bất kỳ các cột NodeID hay
NodeName hay ParentID để hiển thị danh sách các Node theo thứ tự duyệt
trên. Trong bài vi ết này, tôi sẽ dùng cột WoodenLeg với các giá trị đặc biệt để
làm việc đó. Giá trị cột WoodenLeg đ ược tính như sau:
* Nếu là node gốc (Root Node) thì WoodenLeg = NodeID
* Các node thứ cấp còn lại thì WoodenLeg = WoodenLeg c ủa node cha gần
nhất + NodeID của node đó. (dấu "+" trong biểu thức trên là phép ghép/c ộng
chuỗi ký tự)
Với cách tính trên, ta tính được giá trị cột WoodenLeg cho từng node nh ư sau:
- Biểu thức Kết quả Mô t ả
NodeName
Vì nó là node gốc
Root node "1" "1"
- "1" là giá trị của cột
WoodenLeg của node cha của
Node 1 "1"+"2" "12"
Node 1 (Root Node)
- 2 là NodeID của Node 1
- Giải thích tương tự
Node 2 "1"+"3" "13"
...
Hình 3: Bảng mô tả cách tính giá trị cột WoodenLeg (Các bạn có thể
xem giá trị WoodenLeg của tất cả các node ở hình 2)
Script để tính giá trị cột WoodenLeg:
* Trường hợp 1: Cập nhật ngay cột n ày khi vừa thêm 1 node vào cây
§ Khi thêm node gốc:
Insert Into Tree
Values (1, Root Node, Null, 1);
§ Khi thêm node thứ cấp:
Insert Into Tree
Values(2, Node 1, 1, Null); -- Node 1 là node con c ủa Root Node
Update Tree
Set Tree.WoodenLeg = Cast(T.WoodenLeg As varchar(100)) +
Cast(Tree.NodeID As varchar(100))
From Tree, Tree T
Where (Tree.ParentID = T.NodeID) And
(Tree.NodeID = 2); -- 2 là NodeID của Node 1 vừa
-- được thêm vào table Tree
- * Trường hợp 2: Cập nhật giá trị cột này khi có nhu cầu hiển thị theo thứ tự
duyệt cây
-- Xóa tất cả giá trị của cột WoodenLeg trong bảng
Update Tree
Set WoodenLeg = Null;
-- Gán giá trị column WoodenLeg cho node gốc
Update Tree
Set WoodenLeg = NodeID
Where ParentID Is Null;
-- Node có ParentID = Null là node g ốc
/* Gán giá trị cột WoodenLeg cho các node thứ cấp
Ứng với mỗi lần lặp ta tính được giá trị cho các node ở cấp t ương ứng
Ví dụ ở lần lặp đầu tiên, ta tính được giá trị cho các node cấp 1, bao
gồm: Node 1, Node 2, Node 3, Node 4.
*/
While (1=1) -- Điều kiện thoát được thể hiện bên trong vòng lặp
Begin
Update Tree
Set Tree.WoodenLeg =Cast(T.WoodenLeg As varchar(100))+
Cast(Tree.NodeID As varchar(100))
From Tree, Tree T
- Where (Tree.ParentID = T.NodeID) And
(Tree.WoodenLeg Is Null);
If (@@RowCount = 0)
-- Đã tính xong giá trị WoodenLeg cho
-- tất cả các node trong bảng Tree
Break;
End
Sau khi tính toán xong giá trị cho cột WoodenLeg, chúng ta viết script để hiển
thị danh sách theo thứ tự duyệt cây nh ư được yêu cầu:
Select NodeName, WoodenLeg
From Tree
Order By WoodenLeg;
Và kết quả thu được như mô tả trong hình 4. Sở dĩ chúng ta có được kết quả
này là do c ột WoodenLeg có kiểu dữ liệu là varchar nên khi so sánh các giá trị
để xác định trình tự hiển thị nó sẽ tiến hành so sánh theo kiểu chuỗi ký tự.
Chuỗi "126" của Node A sẽ nhỏ hơn chuỗi "13" của node 2 nên Node A sẽ
đứng trước Node 2 trong danh sách.
- Như vậy thứ tự duyệt cây thông qua phát biểu NodeName WoodenLeg
Select ở trên gần giống với thứ tự duyệt cây mong Root Node 1
đợi. Nó chỉ khác nhau khi đi đến các node con của
Node 1 12
Node 2.
Node A 126
Vấn đề chúng ta đang gặp phải là do Node 2 có ba Node B 127
Node 2 13
node con là Node C, Node D, Node E. Trong đó,
Node C, Node D lần lượt có NodeID là 8 và 9, tức Node E 1310
chỉ có một ký số, trong khi Node E có NodeID là Node C 138
10, tức hai ký số. Vì thế, giá trị cột WoodenLeg Node D 139
của ba node con trên lần lượt là: "138", "139", Node 3 14
"1310". Như đã nói ở trên, kiểu so sánh ở cột
Node 4 15
WoodenLeg là so sánh chuỗi nên chuỗi "1310"
Node F 1511
nhỏ hơn chuỗi "138" cũng như "139". Và đó là
Node X 151113
nguyên nhân dẫn đến thứ tự duyệt cây không đạt
Node Y 151114
như mong đợi.
Node Z 151115
Node G 1512
Nếu ta lần lượt thay thế chuỗi ký số "8" v à "9"
(NodeID của hai Node C & D) thành 08" và "09" Hình 4: Kết quả thu được
từ phát biểu Select
trong biểu thức tính giá trị WoodenLeg thì các
chuỗi kết quả sẽ l à: "1308", "1309", "1310". Và thứ tự duyệt cây cũng thay đổi
theo hướng ta mong đợi. Điều đó cũng có nghĩa là mọi vấn đề đã được giải
quyết.
Như vậy, nếu chúng ta xác định đ ược số ký số tối đa được dùng để lưu giá trị
NodeID của bảng Tree thì chúng ta luôn kiểm soát được tình hình và kết quả
thu được luôn luôn chính xác. Giả sử cây đa cấp chúng ta đang xét ở tr ên có
không quá 1000 node, điều đó có nghĩa l à số ký số được dùng tối đa cho
NodeID là 3 (t ừ 1 đến 999). Khi đó, biểu thức tính toán cột WoodenLeg đ ược
chỉnh lại như sau (áp dụng cho cả hai trường hợp):
....
Set Tree.WoodenLeg =Cast(T.WoodenLeg As varchar(100))+ SubString(00 +
Cast(Tree.NodeID As varchar(100)), Len(Tree.NodeID), 3)
....
Các bạn có thể thay thế cột WoodenLeg bằng biểu thức tính toán để phục vụ
cho việc thể hiện thứ tự duyệt cây. Tuy nhiên, server sẽ phải làm nhiều việc
hơn vì ở mỗi lần thực thi, server phải tính lại giá trị của biểu thức.
- Bài toán duyệt cây là một bài toán tổng quát mà từ đó chúng ta có thể nhân
rộng để áp dụng cho rất nhiều bài toán thực tế khác. Tôi hi vọng bài viết này ít
nhiều mang lại một chút kinh nghiệm bổ ích cho các bạn.
Quốc Hồng Anh
Thêm tài liệu vào bộ sưu tập có sẵn:
Báo xấu
LAVA
ERROR:connection to 10.20.1.100:9315 failed (errno=111, msg=Connection refused)
ERROR:connection to 10.20.1.100:9315 failed (errno=111, msg=Connection refused)
Đang xử lý...
Thêm vào BST
Báo xấu
