July 2, 2011 at 8:39 am
A decision making is built using a binary tree (Node, LeftNode, RightNode) is stored in the DB as
[font="System"]
/*
CREATE TABLE #Tree
( Root Int
, ParentNode INT
, Node INT
, LeftNode INT
, RightNode INT
, IsBranch CHAR(1)
, Sequence INT
)
*/
SELECT *
INTO #Tree
FROM (
SELECT 6000 AS Root, 6000 AS ParentNode, 650 AS Node, 0 AS LeftNode, 0 AS RightNode, 'N' AS IsBranch, 214 AS Sequence
UNION
SELECT 6000 AS Root, 6000 AS ParentNode, 651 AS Node, 652 AS LeftNode, 0 AS RightNode, 'Y' AS IsBranch, 218 AS Sequence
UNION
SELECT 6000 AS Root, 651 AS ParentNode, 652 AS Node, 654 AS LeftNode, 653 AS RightNode, 'Y' AS IsBranch, 220 AS Sequence
UNION
SELECT 6000 AS Root, 652 AS ParentNode, 653 AS Node, 0 AS LeftNode, 0 AS RightNode, 'N' AS IsBranch, 221 AS Sequence
UNION
SELECT 6000 AS Root, 652 AS ParentNode, 654 AS Node, 0 AS LeftNode, 0 AS RightNode, 'N' AS IsBranch, 222 AS Sequence
UNION
SELECT 6000 AS Root, 6000 AS ParentNode, 655 AS Node, 656 AS LeftNode, 657 AS RightNode, 'Y' AS IsBranch, 223 AS Sequence
UNION
SELECT 6000 AS Root, 655 AS ParentNode, 656 AS Node, 0 AS LeftNode, 0 AS RightNode, 'N' AS IsBranch, 224 AS Sequence
UNION
SELECT 6000 AS Root, 655 AS ParentNode, 657 AS Node, 0 AS LeftNode, 0 AS RightNode, 'N' AS IsBranch, 225 AS Sequence
UNION
SELECT 6000 AS Root, 6000 AS ParentNode, 658 AS Node, 659 AS LeftNode, 0 AS RightNode, 'Y' AS IsBranch, 226 AS Sequence
UNION
SELECT 6000 AS Root, 658 AS ParentNode, 659 AS Node, 0 AS LeftNode, 0 AS RightNode, 'N' AS IsBranch, 227 AS Sequence
UNION
SELECT 6000 AS Root, 6000 AS ParentNode, 660 AS Node, 661 AS LeftNode, 0 AS RightNode, 'Y' AS IsBranch, 228 AS Sequence
UNION
SELECT 6000 AS Root, 660 AS ParentNode, 661 AS Node, 0 AS LeftNode, 0 AS RightNode, 'N' AS IsBranch, 229 AS Sequence
UNION
SELECT 6000 AS Root, 6000 AS ParentNode, 663 AS Node, 664 AS LeftNode, 0 AS RightNode, 'Y' AS IsBranch, 230 AS Sequence
UNION
SELECT 6000 AS Root, 663 AS ParentNode, 664 AS Node, 0 AS LeftNode, 0 AS RightNode, 'N' AS IsBranch, 231 AS Sequence
UNION
SELECT 6000 AS Root, 6000 AS ParentNode, 665 AS Node, 666 AS LeftNode, 0 AS RightNode, 'Y' AS IsBranch, 232 AS Sequence
UNION
SELECT 6000 AS Root, 665 AS ParentNode, 666 AS Node, 0 AS LeftNode, 0 AS RightNode, 'N' AS IsBranch, 233 AS Sequence
UNION
SELECT 6000 AS Root, 6000 AS ParentNode, 667 AS Node, 668 AS LeftNode, 0 AS RightNode, 'Y' AS IsBranch, 234 AS Sequence
UNION
SELECT 6000 AS Root, 667 AS ParentNode, 668 AS Node, 669 AS LeftNode, 670 AS RightNode, 'Y' AS IsBranch, 235 AS Sequence
UNION
SELECT 6000 AS Root, 668 AS ParentNode, 669 AS Node, 0 AS LeftNode, 0 AS RightNode, 'N' AS IsBranch, 236 AS Sequence
UNION
SELECT 6000 AS Root, 668 AS ParentNode, 670 AS Node, 673 AS LeftNode, 672 AS RightNode, 'Y' AS IsBranch, 237 AS Sequence
UNION
SELECT 6000 AS Root, 670 AS ParentNode, 673 AS Node, 0 AS LeftNode, 0 AS RightNode, 'N' AS IsBranch, 238 AS Sequence
UNION
SELECT 6000 AS Root, 670 AS ParentNode, 672 AS Node, 0 AS LeftNode, 0 AS RightNode, 'N' AS IsBranch, 239 AS Sequence
) AS T
--SELECT * FROM #Tree ORDER BY Sequence --Section=6000
--SELECT * FROM #Tree WHERE Node=651 --1 child
--SELECT * FROM #Tree WHERE Node=652 --2 children
--SELECT * FROM #Tree WHERE Node=653 --0 children
--SELECT * FROM #Tree WHERE Root=ParentNode ORDER BY Sequence --Top tree for Section 6000
--SELECT * FROM #Tree WHERE Node>=667 ORDER BY Sequence -- tree for Node=667
--SELECT * FROM #Tree WHERE Node>=667 AND (LeftTree=0 OR RightTree=0) ORDER BY Sequence --terminal node on tree Node=667
[/font]
Characteristics:
- a node can have 1 child, e.g. Node=651
- a node can have 2 children, e.g. Node=652
- a node can have 0 children, e.g. 653
- a terminated node is a node that has 0 or 1 child; Using this node as an ID to another table to get the decision/answer
- columns: IsBranch & Sequence are added for illustration purpose
Section 6000 (Root=6000) has 8 decisions (SELECT * FROM #Tree WHERE Root=ParentNode ORDER BY Sequence), but total tree have 22 questions/decisions and a total of 18 possible answers.
The top question of node-667 (SELECT * FROM #Tree WHERE Node>=667 ORDER BY Sequence) has 6 elements but only ONE out of 4 answers. The answers is stored in node 667, 669, 672, 673.
The questions I have are:
1) Tree transversal:
- how to transverse (up) this binary tree for a given node (eg, 673), I expect 673, 670, 668, 667, 6000 without using cursor and recursive function
- how to transverse (down) this binary tree for a given node (eg, 667) without using cursor and recursive function. I expect:
667,0;
667, 668, 669,0;
667, 668, 670,672,0;
667, 668, 670,673,0;
2) Architecture:
- How to avoid/detect cyclic tree?
e.g.1 Node=555, ParentNode=555
e.g.2 Node=777, LeftNode=778; Node=778, LeftNode=779; Node=779, RightNode=777
add constrains?
- How to improve the tree "correctness"?
e.g. Node=222, LeftNode=223; Node=223, ParentNode=221 (should be 222)
- Is there are better architect for this? area improvement of this model?
July 2, 2011 at 8:59 am
without using cursor and recursive function
Why is this a requirement?
I suggest that you read up on the new hierarchyID datatype in 2008. You can start here.
__________________________________________________
Against stupidity the gods themselves contend in vain. -- Friedrich Schiller
Stop, children, what's that sound? Everybody look what's going down. -- Stephen Stills
July 3, 2011 at 6:02 am
We are still on SQL Server 2000. Besides, this is a typical problem.
July 3, 2011 at 8:49 am
You posted an SQL Server 2000 problem on an SQL Server 2008 forum and that's part of the reason you're not getting much help. Also, if it were a "typical" problem, you'd already have an answer. 😉
I've never had to work with a Binary Tree but the author of the article at the following link has... he's written a couple of books on the subject.
http://www.simple-talk.com/sql/t-sql-programming/binary-trees-in-sql/
--Jeff Moden
Viewing 4 posts - 1 through 3 (of 3 total)
You must be logged in to reply to this topic. Login to reply