Recently for a student, I was asked to explain the design considerations of a Binary Tree which was to be used in an MLM solution. About 10 years back it was a nightmare, and in my career, I was lucky to get that privilage for more than a dozen times with varying schemes and structures. But now with MySQL having procedures, and functions, the tree design and related functions were a breze. Reproducing it here for future reference. This is in no way a complete solution, but just bits and pieces which may even be discarded as crap.
CREATE TABLE `binTree` (
`nodeid` int(10) unsigned NOT NULL auto_increment,
`lnode` int(10) unsigned NOT NULL default '0',
`rnode` int(10) unsigned NOT NULL default '0',
`pnode` int(10) unsigned NOT NULL default '0',
`pside` enum('l','r') NOT NULL default 'l',
`tLevel` int(10) unsigned NOT NULL default '1',
PRIMARY KEY (`nodeid`),
KEY `parent` (`pnode`),
KEY `treelevel` (`tLevel`),
KEY `lside` (`lnode`),
KEY `rside` (`rnode`)
) ENGINE=MyISAM;
The above is the basic structure of the tree table, and some complementary functions and procedures are accompanied to make the usage simple, otherwise would be a herculian task for the developer to do the same.
CREATE PROCEDURE `addTreeNode`(iParent int, cSide char(1))
BEGIN
declare iCheck int;
declare iLevel int;
declare iNewNode int;
select if(@silentmode is null, 0, @silentmode) into @silentmode;
# need to do some validations, since this is add.. and not change
# check that parent side is vaccant
if cSide = 'l' then
select lnode into iCheck from binTree where nodeid = iParent;
end if;
if cSide = 'r' then
select rnode into iCheck from binTree where nodeid = iParent;
end if;
if iCheck = 0 then
# okay we can start applying
select tLevel into iLevel from binTree where nodeid = iParent;
insert into binTree ( `pnode`, `pside`, `tLevel`) values (iParent, cSide, iLevel + 1);
select last_insert_id() into iNewNode;
if cSide = 'l' then
update binTree set lnode = iNewNode where nodeid = iParent;
end if;
if cSide = 'r' then
update binTree set rnode = iNewNode where nodeid = iParent;
end if;
else
set iNewNode = 0;
end if;
if @silentmode = 0 then
select iNewNode as res;
end if;
END
The addTreeNode procedure is called to add a new node into the system, if need to use this, one should have a login, and profile table different, and then invoke the procedure with parentid and l/r for left/right, which will return the userid, which should be used as primary key to save login info as well as contact info.
CREATE PROCEDURE `getTreeFrom`(iNode int)
BEGIN
declare iMaxLevel int;
declare iLevel int;
declare iCheck int;
select tLevel + 1 into iLevel from binTree where nodeid = iNode;
select max(tLevel) into iMaxLevel from binTree;
# cant play without temporary tables;
create temporary table tNodes (itNode int unsigned );
create temporary table uNodes (itNode int unsigned );
insert into tNodes value(iNode);
loop1: LOOP
if iLevel > iMaxLevel then
LEAVE loop1;
end if;
insert into uNodes select nodeid from binTree where pnode in (select itNode from tNodes) and tLevel = iLevel;
select count(*) into iCheck from uNodes;
if iCheck = 0 then
LEAVE loop1;
end if;
insert into tNodes select itNode from uNodes;
truncate table uNodes;
set iLevel = iLevel + 1;
END LOOP;
select bt.* from binTree bt, tNodes tn where tn.itNode = bt.nodeid order by bt.tLevel, bt.nodeid;
drop table uNodes;
drop table tNodes;
END
This procedure would be a bit too much on systems when the tree called from is one of the top range.. still we cannot let the system go without one like this and hence any tree starting from a node can be selected using getTreeFrom.
CREATE PROCEDURE `pruneNode`(iNode int, iParent int, sSide char(1))
BEGIN
declare iCheck int;
declare iNewLevel int;
declare oParent int;
declare oSide char(1);
#request is to pluck iNode from existing parent and attach to new parent in said side
#side should not be empty.. check that first
if (sSide = 'l') then
select lnode into iCheck from binTree where nodeid = iParent;
if iCheck = 0 then
update binTree set lnode = iNode where nodeid = iParent;
end if;
end if;
if (sSide = 'r') then
select rnode into iCheck from binTree where nodeid = iParent;
if iCheck = 0 then
update binTree set rnode = iNode where nodeid = iParent;
end if;
end if;
if (iCheck > 0) then
select 0 as res;
else
select pnode into oParent from binTree where nodeid = iNode;
select pside into oSide from binTree where nodeid = iNode;
update binTree set pnode=iParent, pside=sSide where nodeid = iNode;
if oSide = 'l' then
update binTree set lnode = 0 where nodeid = oParent;
end if;
if oSide = 'r' then
update binTree set rnode = 0 where nodeid = oParent;
end if;
select tLevel into iNewLevel from binTree where nodeid = iNode;
CALL stabilizeLevels(iNewLevel);
end if;
END
This one function was just out of the nostalgy, since this was demanded by one of my clients, and we just said it was not possible thinking of all the recursive calls we had to implement using php, but now just a wimph.. The parameters are node to be pruned, new parent, and side of new parent. Resulting result set will contain single column single row, either ‘0’ ( means the new parent’s side was not empty ) or ‘1’ ( means the operation was successful ). This uses a complementary procedure for which the listing is reproduced below.
CREATE PROCEDURE `stabilizeLevels`(iLevel int)
BEGIN
declare iCheck int;
declare iMaxLevel int;
declare iNCount int;
declare sNodeList text;
if iLevel = 1 then
select 0 as res;
else
#starting from iLevel.. traverse to iMaxLevel and make sure all nodes are correct..
select max(tLevel) into iMaxLevel from binTree;
loop1: LOOP
if (iLevel > iMaxLevel) then
LEAVE loop1;
end if;
create TEMPORARY table mylist (iNode int);
insert into mylist select nodeid from binTree where tLevel = iLevel;
select sum(checkLevel(iNode) * 1) into iCheck from mylist;
drop table mylist;
if (iCheck = 0) then
LEAVE loop1;
end if;
set iLevel = iLevel + 1;
END LOOP;
select 1 as res;
end if;
END
And another function which was just out of sheer curiosity..
CREATE FUNCTION `checkLevel`(iNode int) RETURNS enum('0','1') CHARSET latin1
BEGIN
declare iParent int;
declare iMyLevel int;
declare iCheck int;
declare iMaxLevel int;
if (iNode = 0) then
return '0';
end if;
#get parent level and make sure the difference is 1 if not.. go deep and update the levels
select count(*) into iCheck from binTree where nodeid = iNode;
if iCheck = 0 then
return '0';
end if;
select tLevel into iMyLevel from binTree where nodeid = iNode;
select pnode into iParent from binTree where nodeid = iNode;
select iMyLevel - tLevel into iCheck from binTree where nodeid = iParent;
if iCheck <> 1 then
select tLevel + 1 into iMyLevel from binTree where nodeid = iParent;
update binTree set tLevel = iMyLevel where nodeid = iNode;
return '1';
else
return '0';
end if;
END
The above system is not benchmarked, neither tested in realtime. But if it becomes of use to any one of you, please add a comment to the comments box here.
Sunday, Oct 4.
Just added a couple of procedures more to test and do some benchmarks. Adding those procedures to this post, for future reference.
CREATE PROCEDURE `initTree`() BEGIN truncate table binTree; insert into binTree values (1,0,0,0,'l',1); select * from binTree; END
Just got tired of truncating the table, inserting the initial row etc..
CREATE PROCEDURE `gFillNodes`(iParent int, iCount int, bRandPlace binary(1))
BEGIN
declare sLeg char(1);
declare iTest int;
declare iLevel int;
#start the loop
set @silentmode = 1;
loop1: LOOP
if iCount = 0 then
LEAVE loop1;
end if;
if bRandPlace = 1 then
select floor(rand() * 100) % 2 into iTest;
if iTest = 0 then
set sLeg = 'r';
select min(nodeid) into iParent from binTree where nodeid >= iParent and rnode = 0;
else
set sLeg = 'l';
select min(nodeid) into iParent from binTree where nodeid >= iParent and lnode = 0;
end if;
else
select min(tLevel) into iLevel from binTree where nodeid >= iParent and (lnode = 0 or rnode = 0);
select count(*) into iTest from binTree where lnode = 0 and tLevel = iLevel;
if iTest = 0 then
select min(nodeid) into iParent from binTree where rnode = 0 and tLevel = iLevel;
set sLeg = 'r';
else
select min(nodeid) into iParent from binTree where lnode = 0 and tLevel = iLevel;
set sLeg = 'l';
end if;
end if;
CALL addTreeNode(iParent, sLeg);
set iCount = iCount - 1;
END LOOP;
END
Random as well as sequential fill of the tree.. one can see the working in the screen shot of the console..
Addition
Few days back some body was asking me, how I would go about to finding the parent node of parent node of given node, well I did not have to think much, than kick in the following listing as a mysql function. Since mysql does not support arrays (afaik), well that is not a big problem, we could split the return value in any of the programming language.
CREATE FUNCTION `getAncestors`(iNode int, iSteps int) RETURNS text
BEGIN
declare sAncestors text;
if (iSteps = 0) then
select count(*) into iSteps from binTree where nodeId <= iNode;
end if;
loop1: LOOP
if ( iSteps <= 0 ) then
LEAVE loop1;
end if;
select pnode into iNode from binTree where nodeid = iNode;
if (iNode = 0) then
LEAVE loop1;
end if;
if(length(sAncestors) > 0) then
set sAncestors = concat(sAncestors,',',iNode);
else
set sAncestors = concat(iNode,'');
end if;
set iSteps = iSteps - 1;
END LOOP;
RETURN sAncestors;
END