The issue is to move the gaps between siblings in a tree to the right
of the rightmost sibling while also maintaining the spread between
each node's left and right values. Additionally, it would be useful
to be able to set the root node's left value to 1 before left shifting
so that the tree is put into "normal form". This would be useful if
we wanted to present a subtree normalized. Furthermore, we might want
to begin the left shifting at any node in the tree and not just the
tree's root node. When working with a very large tree it could be
much more efficient to left shift only certain subtrees, indicated by
giving the subtree's root node.
Before we can left shift a tree we need to identify the gaps to
close. There are two types of gaps:
1. Between the left value of the oldest, i.e., leftmost, child N1L and
the left value of its parent N2L. We look for instances where
N1L - N2L > 1.
2. Between the left value of a node N1L and the right value of its
sibling N2R to the immediate left. We look for instances where
N1L - N2R > 1.
For all gaps on level N to be closed, all gaps in the previous N-1
levels must have been closed. This would lead to a top-down
breadth-first iterative algorithm. However, note that when left
shifting a level N the same amount of shifting must be simultaneously
applied to all descendants of this level so that the tree's
ancestor-descendant relationship, represented by nested sets, is
always maintained.
Below is some T-SQL code, tested on SQL Server, that implements this
followed by a few examples. The code might appear a bit complex on a
first pass but the algorithm is straightforward. Note that while
iteration is used, no temp tables or extra columns are required.
First, let's show the DDL and sample data.
CREATE TABLE Tree
(
value VARCHAR(10) NOT NULL PRIMARY KEY,
lft INT NOT NULL CHECK (lft > 0),
rgt INT NOT NULL CHECK (rgt > 0),
CHECK (rgt > lft)
)
INSERT INTO TREE
SELECT 'Albert', 100, 1200
UNION ALL
SELECT 'Bert', 101, 201
UNION ALL
SELECT 'Ernie', 250, 300
UNION ALL
SELECT 'Chuck', 400, 1100
UNION ALL
SELECT 'Donna', 501, 601
UNION ALL
SELECT 'Eddie', 701, 801
UNION ALL
SELECT 'Fred', 901, 1001
Next, let's look at some views that provide structural information
about the tree.
- Define tree levels with the root node being at level 1,
- not the standard level 0
CREATE VIEW NodeLevels
AS
SELECT T2.value AS value,
COUNT(T1.value) AS level
FROM Tree AS T1
INNER JOIN
Tree AS T2
ON T2.lft BETWEEN T1.lft AND T1.rgt
GROUP BY T2.value
- Define tree parent-child relationship
CREATE VIEW Children
AS
SELECT T1.value AS parent,
T2.value AS child,
T1.lft AS lftParent,
T1.rgt AS rgtParent,
T2.lft AS lftChild,
T2.rgt AS rgtChild
FROM Tree AS T1
INNER JOIN
Tree AS T2
ON T2.lft > T1.lft AND
T2.rgt < T1.rgt AND
NOT EXISTS (SELECT *
FROM Tree AS T3
WHERE T3.lft > T1.lft AND
T3.lft < T2.lft AND
T3.rgt < T1.rgt AND
T3.rgt > T2.rgt)
- Define tree ancestor-descendant relationship
CREATE VIEW Descendants
AS
SELECT T1.value AS ancestor,
T2.value AS descendant
FROM Tree AS T1
INNER JOIN
Tree AS T2
ON T2.lft > T1.lft AND
T2.rgt < T1.rgt
- Consecutive siblings with a gap > 0
CREATE VIEW ConsecutiveSiblingGaps
AS
SELECT C1.child AS lftChild,
C2.child AS rgtChild,
L.level AS level,
C2.lftChild - C1.rgtChild - 1 AS gap
FROM Children AS C1
INNER JOIN
Children AS C2
ON C1.parent = C2.parent AND
C1.rgtChild < C2.lftChild - 1 AND
NOT EXISTS (SELECT *
FROM Children AS C3
WHERE C3.parent = C1.parent AND
C3.lftChild > C1.rgtChild AND
C3.rgtChild < C2.lftChild)
INNER JOIN
NodeLevels AS L
ON L.value = C1.child
- Gap between parent and oldest child, i.e., leftmost child, > 0
CREATE VIEW ParentOldestChildGaps
AS
SELECT C1.parent AS parent,
C1.child AS child,
L.level AS childLevel,
C1.lftChild - C1.lftParent - 1 AS gap
FROM Children AS C1
INNER JOIN
NodeLevels AS L
ON NOT EXISTS (SELECT *
FROM Children AS C2
WHERE C2.parent = C1.parent AND
C2.lftChild < C1.lftChild) AND
C1.lftParent < C1.lftChild - 1 AND
L.value = C1.child
Finally, the stored procedure that does the left shifting.
- Procedures to left-shift tree
- All gaps are moved rightward
- All spreads remain the same
- Only left-shift subtree rooted at the given node
CREATE PROCEDURE ShiftLeftSubtree
@node VARCHAR(10)
AS
DECLARE @level INT
SELECT @level = level
FROM NodeLevels
WHERE value = @node
IF @level IS NOT NULL
EXEC ShiftLeftHelper @node, @level
- Left-shift complete tree where the root can optionally be shifted so
- that its left value is 1
CREATE PROCEDURE ShiftLeft
@rootLeftAt1 BIT = 0
AS
DECLARE @root VARCHAR(10)
SELECT @root = value
FROM NodeLevels
WHERE level = 1
IF @root IS NOT NULL
EXEC ShiftLeftHelper @root, 1, @rootLeftAt1
- This is the main procedure that does all left shifting
CREATE PROCEDURE ShiftLeftHelper
@node VARCHAR(10), -- node to start shifting from
@level INT, -- node's level (root is level 1)
@rootLeftAt1 BIT = 0 -- set root's left value to 1?
AS
BEGIN
- Current tree level to visit
DECLARE @currentLevel INT
SELECT @currentLevel = @level
- Tree height
DECLARE @height INT
SELECT @height = MAX(level)
FROM NodeLevels
- Handle left shifting of root node when it's left value is to be 1
IF @currentLevel = 1
BEGIN
IF @rootLeftAt1 = 1
BEGIN
- Left shift tree based on gap provided by root node
DECLARE @rootGap INT
SELECT @rootGap = T1.lft - 1
FROM Tree AS T1
WHERE NOT EXISTS (SELECT *
FROM Tree AS T2
WHERE T2.lft < T1.lft AND
T2.rgt > T1.rgt)
UPDATE Tree
SET lft = CASE WHEN Tree.value = @node
THEN 1
ELSE Tree.lft - @rootGap
END,
rgt = Tree.rgt - @rootGap
END
END
ELSE
BEGIN
- Left shift starting from a node at a level > 1
- This is the first pass at left shifting a subtree based only on
- the gap before a subtree's root. All subsequent left shifting of
- this subtree provided by levels greater than the subtree's root
- level will take place in the loop following this block.
DECLARE @consecutiveSiblingGap INT
SELECT @consecutiveSiblingGap = G.gap
FROM ConsecutiveSiblingGaps AS G
WHERE G.level = @currentLevel AND
G.rgtChild = @node
DECLARE @parentOldestChildGap INT
SELECT @parentOldestChildGap = G.gap
FROM ParentOldestChildGaps AS G
WHERE G.childLevel = @currentLevel AND
G.child = @node
UPDATE Tree
SET lft = COALESCE(Tree.lft - @consecutiveSiblingGap,
Tree.lft - @parentOldestChildGap,
Tree.lft),
rgt = COALESCE(Tree.rgt - @consecutiveSiblingGap,
Tree.rgt - @parentOldestChildGap,
Tree.rgt)
WHERE Tree.value = @node OR
EXISTS (SELECT *
FROM Descendants
WHERE ancestor = @node AND
descendant = Tree.value)
END
- Proceed to the level just after the level of the tree's (or
- subtree's) root node.
SELECT @currentLevel = @currentLevel + 1
- Loop through each level up to the height of the tree
WHILE @currentlevel <= @height
BEGIN
- Each iteration of this loop will shift a level's nodes further to
- the left until there are no more gaps on this level.
- Concurrently, all shifts applied to the nodes on this level are
- also applied to all of those nodes' descendants so as to maintain
- the tree's parent-child relationship.
WHILE EXISTS (SELECT *
FROM ConsecutiveSiblingGaps AS G
INNER JOIN
Descendants AS D
ON G.level = @currentLevel AND
D.descendant = G.rgtChild AND
D.ancestor = @node) OR
EXISTS (SELECT *
FROM ParentOldestChildGaps AS G
INNER JOIN
Descendants AS D
ON G.childLevel = @currentLevel AND
D.descendant = G.child AND
D.ancestor = @node)
BEGIN
UPDATE Tree
SET lft = COALESCE((SELECT Tree.lft - G.gap
FROM ConsecutiveSiblingGaps AS G
WHERE G.level = @currentLevel AND
(G.rgtChild = Tree.value OR
EXISTS (SELECT *
FROM Descendants AS D
WHERE D.descendant = Tree.value AND
D.ancestor = G.rgtChild))),
(SELECT Tree.lft - G.gap
FROM ParentOldestChildGaps AS G
WHERE G.childLevel = @currentLevel AND
(G.child = Tree.value OR
EXISTS (SELECT *
FROM Descendants AS D
WHERE D.descendant = Tree.value AND
D.ancestor = G.child))),
Tree.lft),
rgt = COALESCE((SELECT Tree.rgt - G.gap
FROM ConsecutiveSiblingGaps AS G
WHERE G.level = @currentLevel AND
(G.rgtChild = Tree.value OR
EXISTS (SELECT *
FROM Descendants AS D
WHERE D.descendant = Tree.value AND
D.ancestor = G.rgtChild))),
(SELECT Tree.rgt - G.gap
FROM ParentOldestChildGaps AS G
WHERE G.childLevel = @currentLevel AND
(G.child = Tree.value OR
EXISTS (SELECT *
FROM Descendants AS D
WHERE D.descendant = Tree.value AND
D.ancestor = G.child))),
Tree.rgt)
- Only interested in shifting nodes >= the current level that are
- also descendants of the supplied root node
WHERE EXISTS (SELECT *
FROM Descendants AS D
INNER JOIN
NodeLevels AS L
ON D.descendant = Tree.value AND
D.ancestor = @node AND
L.value = Tree.value AND
L.level >= @currentLevel)
END
- Prepare to visit next level of nodes
SELECT @currentLevel = @currentLevel + 1
END
END
Some examples might be illustrative. The tree we start with is
value lft rgt
Albert 100 1200
Bert 101 201
Ernie 250 300
Chuck 400 1100
Donna 501 601
Eddie 701 801
Fred 901 1001
If we want to left shift the entire tree we execute
EXEC ShiftLeft
so the resulting tree is
value lft rgt
Albert 100 1200
Bert 101 201
Ernie 202 252
Chuck 253 953
Donna 254 354
Eddie 355 455
Fred 456 556
If we want to shift the entire tree but start with a left value of 1
for the root node we execute
EXEC ShiftLeft 1
which results in the following tree
value lft rgt
Albert 1 1101
Bert 2 102
Ernie 103 153
Chuck 154 854
Donna 155 255
Eddie 256 356
Fred 357 457
Finally, we can just shift a subtree by giving that subtree's root
node by executing
EXEC ShiftLeftSubtree 'Chuck'
which modifies the original table to
value lft rgt
Albert 100 1200
Bert 101 201
Ernie 250 300
Chuck 301 1001
Donna 302 402
Eddie 403 503
Fred 504 604
or
EXEC ShiftLeftSubtree 'Eddie'
value lft rgt
Albert 100 1200
Bert 101 201
Ernie 250 300
Chuck 400 1100
Donna 501 601
Eddie 602 702
Fred 901 1001
Regards,
jag
Received on Mon Sep 16 2002 - 15:47:48 CDT
