Search code examples
mysqlsqlternary-tree

insert node in ternary tree

I have a ternary tree,ternary tree

I have created a table 

CREATE TABLE `user_tree` 
( `ID` int(11) NOT NULL AUTO_INCREMENT, 
`name` varchar(100) NOT NULL,
`parent_ID` int(11) NOT NULL,  
`next_pool` tinyint(1) NOT NULL DEFAULT '0', 
`last_update` timestamp(6) NOT NULL DEFAULT CURRENT_TIMESTAMP(6), 
 PRIMARY KEY (`ID`)) ENGINE=MyISAM AUTO_INCREMENT=23 DEFAULT CHARSET=latin1

How can I insert nodes in given sequence in image using mysql query

Solution

  • You must use the next rules set:

    Step 1: Select minimal level number which have empty socket(s);

    Step 2: Select maximal empty sockets per node amount for this level;

    Step 3: Select minimal id for a node with above level and empty sockets amount.

    Let's find where the node #30 must be connected to.

    Step 1.

    The amount of nodes per level may be easily calculated: 1st level contains 1 node, 2nd - 3 nodes, 3rd - 9 nodes, ... Nth - 3^(N-1) nodes. So you may easily calculate the level for a node to be inserted by this node number (for example, if a node is 30th then - 1 node for level 1, 1+3=4 for levels 1+2, 1+3+9=13 nodes for levels 1+2+3, 1+3+9+27=40 nodes for levels 1+2+3+4, i.e. node will be posessed on the 4th level).

    Step 2.

    As calculated above first 13 nodes occupies levels 1-3, so 30th node will be 17th node inserted into level 4. This level contains 9 parent nodes, so 17th node will be 2nd for its parent (roundUp(17/9)). And its parent is 6th on its 3rd level (17 MOD 9).

    Step 3.

    The levels about the parent (1 and 2) contains 1+3=4 nodes. So 6th node on 3rd level is 1+3+6=10th node.

    Totally - node 30 must be joined to the node 10, and it will be 2nd child node for it.