Pointers Galore - Binary Trees and Linked Lists

[TheZsterBunny]

*whew*

I've been throwing some ideas at this program, and I've decided that the best way to do this would be to use a binary tree of linked lists.

This program takes a list of information (name, number, phone, gender...) and stores it in a binary tree.

I have dealt with duplicates by having them in a linked list.

If I can get this working, it will be very effective in solving my problems.

If not, then I'm going to start again for the 5th time. Not fun.

I'm sorry for the lack of commenting, I just got tired of doing it after the 3rd time.

Erm, classes are as follows.

Profile - (works) Holds all information about the individual
PNode - a node which holds a profile and a pointer to the next PNode
TNode - a node which holds pointers to 2 other TNodes and a pointer to a PNode.
TTree - a Binary Tree of TNodes
TreeTest - Creates a sample tree and runs the basic commands.

I've also included a junk-generator, and the junk data file it reads.

*cries* my brain hurts.

-Z

[wtd]

Are you coming from a C or C++ background? Your use of the word "pointers" would seem to indicate that.

[Hikaru79]

wtd wrote:

Are you coming from a C or C++ background? Your use of the word "pointers" would seem to indicate that.

He doesn't. We both wish we did, though

I'm still persistant in reccomending against having a linked list inside every BTree node. Besides the obvious added complexity, it's completely unnecessary. You say you use it for duplicates, but by the very nature of a Binary Tree, duplicates will all be in a nice neat little row anyway, so having a linked list for them is overkill. Then there's the matter of the nodes which do NOT have duplicates (the vast, vast majority of them, in the context of the assignment), it is wasteful to have a linked list with only one person in them for each non-duplicate node. Pure overkill, IMO.

[TheZsterBunny]

H,

my use of 2 different types of nodes makes for great ease when performing operations such as balancing trees or returning all nodes of one value.

oh wait. that would make it difficult to return multiple ranges, now wouldn't it.

crap.

-Z

[Hikaru79]

TheZsterBunny wrote:

H,

my use of 2 different types of nodes makes for great ease when performing operations such as balancing trees or returning all nodes of one value.

Why does it make it easier? All that is different is that instead of going down the "right" link of a binary tree until there's a different value, you're going down the "next" link of a linked list until it's null. I don't see the difference.

TheZsterBunny wrote:

oh wait. that would make it difficult to return multiple ranges, now wouldn't it.

crap.

What do you mean?

[Andy]

i wrote the same prgram last year in c++... if you want i'll post the code.. however, i dont know how much it'll help considering in c++, we use real pointers

[McKenzie]

Way to contribute to the discussion Andy. Z doesn't want to know if you can do the program he wants to know if it is worthwhile to make a linked list of the dupes. Clearly it is more effecient because you don't need to traverse the dupes when looking for a node that is greater or less. By the way Z, it is proper to refer to this as a trinary tree. When you have a binary tree where duplicates are allowed there are a number of ways to inprove the efficiency. In order of increasing efficiency and complexity they are:
0. Let them fall wherever. Try making a btree from {5,2,8,7,9,8} all dupes appear in either the left or right sub-tree of the original (depending on definition).
1. Add any dupes as a direct descendant of the original. This makes them easy to find, but you still have a binary tree so the complexity is fairly low.
2. A Trinary tree. Each node has up to three children. Greater,Equal,Tied.
3. A Quadary tree. Each node has up to four children. Basically what you have here is a binary tree of all the dupes organized based on another field in the record. As we all know this would be the phone number for the assignmnet you are talking about.

Binary trees are already hard enough. Don't kill yourself by trying to over-optimise your solution. Keep in mind that most binary trees force the use of a unique key to organize the nodes to avoid the problem altogether, of those who allow dupes In general they opt for #0.

[TheZsterBunny]

a quatinary tree, eh?

that wouldn't be too bad to do, but i'm afraid mike would think i've copied him.

how would something like this work (i.e. well or not)?

4 notpointers per node two point to lesser/greater love quotient, and the other point to lesser/greater phone numbers

Were I to get that working, searching would be a breeze.

-Z

[Andy]

trinay? you got that off me! i remember my trinary tree heh.. u gave me weird looks

[wtd]

I'm bored, so allow me to show off.

code:

data Tree a = Branch (Tree a) (Tree a) | Leaf a | Empty treeSize Empty = 0 treeSize (Leaf _) = 1 treeSize (Branch b1 b2) = treeSize b1 + treeSize b2 -- or, let's sum up all of the items stored in the tree treeSum Empty = 0 treeSum (Leaf l) = l treeSum (Branch b1 b2) = treeSum b1 + treeSum b2 -- and let's search for the presence of a particular value in a tree treeSearch _ Empty = False treeSearch item (Leaf l) = item == l treeSearch item (Branch b1 b2) = treeSearch item b1 || treeSearch item b2 -- and a slightly more complex search treeSearchBy _ Empty = False treeSearchBy f (Leaf l) = f l treeSearchBy f (Branch b1 b2) = treeSearchBy f b1 || treeSearchBy f b2

So if I want to check if any of the entries in a tree are evenly divisible by 3:

code:

myTree = Branch (Leaf 42) (Branch (Leaf 53) (Branch (Leaf 76) Empty)) treeSearchBy (\x -> mod x 3 == 0) myTree -- or more concisely: -- treeSearchBy ((0 ==) . (`mod` 3)) myTree

[McKenzie]

you're fooling yourself Andy. I've been doing this assignment for years before coming to Massey and some students each year always come to the same conclusion. No one has actually tried the quad until this year, it has only been trivia.

[TheZsterBunny]

*whew* I've cut this down to the wire.


right now I have 2 trees (one for male, one for female) with 3 pointers each.
3 pointers are for greater, even and lesser love values. the other 2 are for greater or lesser phone number (no duplicates possible)

It works.

except I can't figure out how to delete. Can someone explain the steps I'll need to go through so I can figure it out?

-Z