Topic: Binary Tree Algorithm

[irneb]

Now, I'm just guessing here, but are those numbers the sequence numbers for traversal? Do you actually want to generate those from the tree itself?

[JohnK]

From what I understand, trees aren't necessarily sorted like that guys [ 0, 1, 2, 3... ]. ...that would be just be a flat list then. Trees are good for fast searching and whatnot so it could be in any order (actually that's all my experience with them is; create a node when you discover an item you want to store and keep adding to the tree as you keep parsing--add nodes; small on the left, and big on the right-).

About nodes, each node can contain as much information as you want. However the bigger the node the more memory usage. I'm working on a node right now where I'm storing all the integers in a tree and in each node I store the int and two char strings and an enum (another int).

I have been looking at these pictures and from what I can see, this looks like a simple association list kind of thing (I think).

[Kerry]

John,
The tree is simply an ordered Tree using a Universal Address System : 

This is from the linked pdf.



http://csis.bits-pilani.ac.in/faculty/nirmal/dscs/Intro_Trees.pdf

[Kerry]

udaaf,
The tree is ordered and has a unique naming index for each node.
The nodes can be traversed easily without additional link numbers( the left and right sequence numbers youve used).

Is there a particular reason you want to add the sequence numbers.??

What sort of data do you want to associate with each node ( or edge) ??

It's pointless writing code (other than for just it's acedemic value) without knowing the rules to your problem ... 

Regards, Kerry

p.s. :
Keeping in mind that the tree is just a visualisation of the indexing for your data ;
it seems to me that for a lisp solution a nested cons list with each recursive data level represented by a level in the tree may be a viable solution.
This assumed that you have control of the data structure.

[udaaf]

Hi Irneb,

Thanks for your reply. Please find the answer in blue color.

Hang on a sec.

• Is this tree always 0 or 3 subnodes? This seems negative, because your root node only has 2 subnodes, even though the rest seem to have 0 or 3.

For the root yes index always 0 and for subnode can > 2
   

• Is it always filled? I.e. you wouldn't skip a number, say have 2.1 and 2.3 but not 2.2.

Yes always filled with sequence number 2.1 -> 2.2 not 2.3
   

• If filled, does it also fill from the left? E.g. you'd never have a situation where 1 has no subnodes, but 2 has some. This also seems negative, since your first sample has 1 with 0 nodes, and 2 with 3 nodes.

Yes I always fill from the left. If not find subnodes or it's called leaf the number will fill the right position
   

• Is it balanced? I.e. it's always as flat as it can be made, no situations where you might have a 1.1.1 but 2 doesn't have any subnodes.

Sometimes I'll have number 1-1.1-1.1.1-1.1.2-1.2
[/list]The reason I'm asking is that if all those questions are answered in the negative, then this tree structure is quite complex to build programatically. Many checks to go through in order to place the correct item in the correct level at the correct branch.

[udaaf]

Hi Kerry,

Thank for your replay and explanation  .
Please find the answer in blue color.

udaaf,
The tree is ordered and has a unique naming index for each node.
The nodes can be traversed easily without additional link numbers( the left and right sequence numbers youve used).

Is there a particular reason you want to add the sequence numbers.??
Yes. There is a particular reason for add sequence numbers. Because I wanna to add sequence number into table for query the database
What sort of data do you want to associate with each node ( or edge) ??

It's pointless writing code (other than for just it's acedemic value) without knowing the rules to your problem ... 

Regards, Kerry

p.s. :
Keeping in mind that the tree is just a visualisation of the indexing for your data ;
it seems to me that for a lisp solution a nested cons list with each recursive data level represented by a level in the tree may be a viable solution.
This assumed that you have control of the data structure.

[Kerry]

The potential problem with the system you propose is that if you add (or remove) sub-assemblies or parts to your tree the left and right links will be forced to change, making maintenance a nightmare.

Refer to the Ordered Tree using a Universal Address System diagram that I posted.

Each vertex with children could be considered a component(sub-assembly) of your assembly( node 0).
Each vertex without children (leaf) would be a part of its parent component.
So your database need only refer to the node index without the additional left and right numbering.

I'll have a look at some code tonight (after 0800 UTC)

Regards, Kerry

[udaaf]

The potential problem with the system you propose is that if you add (or remove) sub-assemblies or parts to your tree the left and right links will be forced to change, making maintenance a nightmare.

Refer to the Ordered Tree using a Universal Address System diagram that I posted.

Each vertex with children could be considered a component(sub-assembly) of your assembly( node 0).
Each vertex without children (leaf) would be a part of its parent component.
So your database need only refer to the node index without the additional left and right numbering.

I'll have a look at some code tonight (after 0800 UTC)

Regards, Kerry

Hi Kerry,

In this case if I add or remove part or assembly, I'll delete the all record first and renumbering and then reload the data. Because I'll save this data in transaction table.

Regards,

Udaaf

[irneb]

Trees are good for fast searching and whatnot so it could be in any order (actually that's all my experience with them is; create a node when you discover an item you want to store and keep adding to the tree as you keep parsing--add nodes; small on the left, and big on the right-).

You get many different flavours of trees. What you're referring to here is specifically called a Binary Search Tree.

There are even further specializations of that particular type. Look down in that page under the "Optimal binary search trees" heading. One of the flavours of the self-balancing BST is actually one of the algorithms I had to create in one of the exams in my 2nd year CS degree (in 1995): Red Black Tree.

Yes. There is a particular reason for add sequence numbers. Because I wanna to add sequence number into table for query the database

In that case the #1 data #2 needs to be calculated from a traversal of the tree. Will have to look at that. It would be a form of destructive traversal as each node visited would have to modify that node. It would be a form of pre-order traversal.

The potential problem with the system you propose is that if you add (or remove) sub-assemblies or parts to your tree the left and right links will be forced to change, making maintenance a nightmare.

Yep, it means that each time you insert anything into that tree (if it doesn't simply replace an existing node) the entire traversal re-numbering has to be done again. It might be possible to come up with an algorithm to only renumber those nodes which change - potentially halving the average number of changes.

[irneb]

Here's the code for the pre-order traversal sequencing:

Code - Auto/Visual Lisp: [Select]

1. (defun Tree:Pre-Order-Traverse (tree visit / )
2.   (apply visit (list (Tree:GetValue tree)))
3.   (foreach child (cdr tree) (Tree:Pre-Order-Traverse child visit)))
4.  
5. (defun Tree:Pre-Order-Traverse-And-Back (tree visit / val)
6.   (setq val (apply visit (list (Tree:GetValue tree))))
7.   (foreach child (cdr tree) (Tree:Pre-Order-Traverse-And-Back child visit))
8.   (apply visit (list val)))
9.  
10. (defun Tree:Pre-Order-Sequence-Index (tree / num result)
11.   (setq num 0)
12.   (Tree:Pre-Order-Traverse-And-Back tree
13.     (function (lambda (val / found)
14.                 (cond ((and (listp val) (setq found (assoc (car val) result)))
15.                        (setq result (subst (setq val (append val (list (setq num (1+ num))))) found result)))
16.                       (t (setq result (cons (setq val (list (setq num (1+ num)) val)) result))))
17.                 val)))
18.   (reverse result))
19.  
20. ;| Testing code
21. (setq testData '("Albert" "Bert" "Chuck" "Donna" "Eddie" "Fred")
22.       testIndex '("0" "1" "2" "2.1" "2.2" "2.3"))
23. (setq testTree (Tree:Make (mapcar 'Tree:ParseIndex testIndex) testData)) ; Returns ("Albert" ("Bert") ("Chuck" ("Donna") ("Eddie") ("Fred")))
24. (Tree:GetValue (Tree:GetFromIndex (Tree:ParseIndex "2.2") testTree)) ; Returns "Eddie"
25. (Tree:Pre-Order-Sequence-Index testTree) ; Returns ((1 "Albert" 12) (2 "Bert" 3) (4 "Chuck" 11) (5 "Donna" 6) (7 "Eddie" 8) (9 "Fred" 10))
26. |;

[udaaf]

Trees are good for fast searching and whatnot so it could be in any order (actually that's all my experience with them is; create a node when you discover an item you want to store and keep adding to the tree as you keep parsing--add nodes; small on the left, and big on the right-).

You get many different flavours of trees. What you're referring to here is specifically called a Binary Search Tree.

There are even further specializations of that particular type. Look down in that page under the "Optimal binary search trees" heading. One of the flavours of the self-balancing BST is actually one of the algorithms I had to create in one of the exams in my 2nd year CS degree (in 1995): Red Black Tree.

Yes. There is a particular reason for add sequence numbers. Because I wanna to add sequence number into table for query the database

In that case the #1 data #2 needs to be calculated from a traversal of the tree. Will have to look at that. It would be a form of destructive traversal as each node visited would have to modify that node. It would be a form of pre-order traversal.

The potential problem with the system you propose is that if you add (or remove) sub-assemblies or parts to your tree the left and right links will be forced to change, making maintenance a nightmare.

Yep, it means that each time you insert anything into that tree (if it doesn't simply replace an existing node) the entire traversal re-numbering has to be done again. It might be possible to come up with an algorithm to only renumber those nodes which change - potentially halving the average number of changes.

Hi  Irneb,

Thanks for your code. I'll try for learn this code first.

[udaaf]

Here's the code for the pre-order traversal sequencing:

Code - Auto/Visual Lisp: [Select]

1. (defun Tree:Pre-Order-Traverse (tree visit / )
2.   (apply visit (list (Tree:GetValue tree)))
3.   (foreach child (cdr tree) (Tree:Pre-Order-Traverse child visit)))
4.  
5. (defun Tree:Pre-Order-Traverse-And-Back (tree visit / val)
6.   (setq val (apply visit (list (Tree:GetValue tree))))
7.   (foreach child (cdr tree) (Tree:Pre-Order-Traverse-And-Back child visit))
8.   (apply visit (list val)))
9.  
10. (defun Tree:Pre-Order-Sequence-Index (tree / num result)
11.   (setq num 0)
12.   (Tree:Pre-Order-Traverse-And-Back tree
13.     (function (lambda (val / found)
14.                 (cond ((and (listp val) (setq found (assoc (car val) result)))
15.                        (setq result (subst (setq val (append val (list (setq num (1+ num))))) found result)))
16.                       (t (setq result (cons (setq val (list (setq num (1+ num)) val)) result))))
17.                 val)))
18.   (reverse result))
19.  
20. ;| Testing code
21. (setq testData '("Albert" "Bert" "Chuck" "Donna" "Eddie" "Fred")
22.       testIndex '("0" "1" "2" "2.1" "2.2" "2.3"))
23. (setq testTree (Tree:Make (mapcar 'Tree:ParseIndex testIndex) testData)) ; Returns ("Albert" ("Bert") ("Chuck" ("Donna") ("Eddie") ("Fred")))
24. (Tree:GetValue (Tree:GetFromIndex (Tree:ParseIndex "2.2") testTree)) ; Returns "Eddie"
25. (Tree:Pre-Order-Sequence-Index testTree) ; Returns ((1 "Albert" 12) (2 "Bert" 3) (4 "Chuck" 11) (5 "Donna" 6) (7 "Eddie" 8) (9 "Fred" 10))
26. |;

Hi Irneb,

I had test your code and this is code what I want.
I'll learn your code and link for basic theory.

Code: [Select]

;| Testing code
(setq testData '("M1" "S1" "P1" "S2" "P2" "P5" "P6" "P9" "P0" "P3" "S3" "P4" "P7" "P8")
      testIndex '("0" "1" "1.1" "2" "2.1" "2.1.1" "2.1.2" "2.1.2.1" "2.1.2.2" "2.2" "3" "3.1" "3.1.1" "3.1.2"))
(setq testTree (Tree:Make (mapcar 'Tree:ParseIndex testIndex) testData)) ; Returns ("M1" ("S1" ("P1")) ("S2" ("P2" ("P5") ("P6" ("P9") ("P0"))) ("P3")) ("S3" ("P4" ("P7") ("P8"))))
(Tree:GetValue (Tree:GetFromIndex (Tree:ParseIndex "2.1.2") testTree)) ; Returns "P6"
(Tree:Pre-Order-Sequence-Index testTree) ; Returns ((1 "M1" 28) (2 "S1" 5) (3 "P1" 4) (6 "S2" 19) (7 "P2" 16) (8 "P5" 9) (10 "P6" 15) (11 "P9" 12) (13 "P0" 14) (17 "P3" 18) (20 "S3" 27) (21 "P4" 26) (22 "P7" 23) (24 "P8" 25))
|;

[irneb]

Glad it worked for you. Just note that the code is meant for a generic multi node tree. There's nothing "special" about it as it doesn't enforce stuff like maximum children or balancing at all. You could use it as the base for other types of trees, or you could re-write to implement something like a binary search tree - the principles are very much the same.

That I leave for someone else  You tend to learn more by doing than by seeing. Tip: the trick with trees is to use recursion. It makes life a lot simpler.

[udaaf]

Glad it worked for you. Just note that the code is meant for a generic multi node tree. There's nothing "special" about it as it doesn't enforce stuff like maximum children or balancing at all. You could use it as the base for other types of trees, or you could re-write to implement something like a binary search tree - the principles are very much the same.

That I leave for someone else  You tend to learn more by doing than by seeing. Tip: the trick with trees is to use recursion. It makes life a lot simpler.

I thought for the beginning your code is more than enough.
And thank you very much for your tips n trick 

[Kerry]

Thanks irned,
saved me from translating some Python code I wrote a couple of months ago.
I'll go watch the football instead

udaaf
Looks like you're well on your way now.