Zipster, are you arguing that the second part is true? Timkin, say you were searching for C? It's not A, so what do you do. If you check right and find it then that is two nodes. Now lets say you are checking for B instead. It isn't A, so you check right, i.e. we have no basis to go any other direction than we did the first time, but it isn't C so we go left. Three nodes to get to B. So say 34% of the time we check 1 node, 33% of the time we check 2 nodes and 33% of the time we check 3 nodes. Now if B is the root and all nodes less than B are left and all nodes greater than B is right a search for B takes 1 node, C takes 2 nodes and A takes two nodes. So 33%*1+33%*2+34%*2 < 34%*1+33%*2+33%*3 unless I'm gravely mistaken in my math. Part B says nothing about the values, but it does say every and here is a case where it isn't true. Thus as near as I can tell if it isn't true for one case it cannot possibly be true for every case.

[edited by - LilBudyWizer on October 29, 2002 7:57:12 PM]

[edited by - LilBudyWizer on October 29, 2002 7:58:24 PM]

quote:

---

Original post by LilBudyWizer
Zipster, are you arguing that the second part is true? Timkin, say you were searching for C? It''s not A, so what do you do. If you check right and find it then that is two nodes. Now lets say you are checking for B instead. It isn''t A, so you check right, i.e. we have no basis to go any other direction than we did the first time, but it isn''t C so we go left. Three nodes to get to B. So say 34% of the time we check 1 node, 33% of the time we check 2 nodes and 33% of the time we check 3 nodes. Now if B is the root and all nodes less than B are left and all nodes greater than B is right a search for B takes 1 node, C takes 2 nodes and A takes two nodes. So 33%*1+33%*2+34%*2 < 34%*1+33%*2+33%*3 unless I''m gravely mistaken in my math. Part B says nothing about the values, but it does say every and here is a case where it isn''t true. Thus as near as I can tell if it isn''t true for one case it cannot possibly be true for every case.

---

Thank you. After reading Timkin''s post, I went back to my books "Oh my God! I never understood binary search trees at all!".

I''m still not sure that I''m right, but your post is exactly how I was going to argue about this.

Timkin,

   A    / \  B   C 

That''s not a binary search tree, as LilBudyWizer pointed out.

Definition of a Binary Search Tree: A binary tree where every node''s left subtree has values less than the node''s value, and every right subtree has values greater. A new node is added as a leaf.

Since A < B < C, your tree is not valid.

Cédric

quote:

---

Original post by LilBudyWizer
Now if B is the root and all nodes less than B are left and all nodes greater than B is right a search for B takes 1 node, C takes 2 nodes and A takes two nodes. So 33%*1+33%*2+34%*2 < 34%*1+33%*2+33%*3

---

But the probabilities would be different if there were other nodes! I do see what you are getting at though... I''ll give it some more thought.

Cheers,

Timkin

quote:

---

Original post by cedricl
That's not a binary search tree, as LilBudyWizer pointed out.

---

Err, I thought were we talking about binary trees as opposed to binary search trees!??? I see though that I was mistaken... sorry.

I need to go back an rethink this whole thing.

Cheers,

Timkin

[edited by - Timkin on October 29, 2002 8:44:45 PM]

I just thought about something, in your comment:

quote:

---

Original Post by Timkin
Note: you have more nodes than A,B & C... look at your branches... and if you don''t, then it isn''t a binary tree. Make sense?"

---

I think that it is the difference between a binary tree and a full binary tree.

Binary tree: A tree with at most two children for each node

Full Binary Tree: A binary tree in which each node has exactly zero or two children

Cédric

quote:

---

Zipster, are you arguing that the second part is true?

---

Yes, I am. However, I am also assuming that the data is sorted, which is the prerequisite for doing a binary search. Otherwise, it isn't really a true binary search, but more like a systematic tree traversion until we find our node.

So, assuming the data is sorted, we would know whether to go left or right, and given any level, the amount of node checks required to reach that level is equal to the depth. As long as we sort our nodes from highest probability to lowest probability from root to leafs, inter-level order isn't important. It's much like the linked list, only level-wise with the tree.

[edited by - Zipster on October 29, 2002 9:14:35 PM]

quote:

---

Original post by Zipster
So, assuming the data is sorted, we would know whether to go left or right

---

How?

I''m not following you. Couldn''t you take the A-B-C example to prove your point? We''re saying that

  A / \B   Cis not a sorted binary search tree, and that  A / \    B   / \      Cis sub-optimal. How do you build your tree if you are not using these two configurations? 

Cédric

I agree with cedricl If the keys are A > B > C and they occur with probabilities 0.4, 0.3 and 0.3 respectively then
A
/
B
/
C
has 1.9 expected steps whereas the second tree where A doesn''t appear in the root node
B
/ \
C A
takes 1.7 steps on average.

Timkin, the statement was every. There certainly are other probabilities and there could be more nodes, but it only takes one case where the statement is wrong to disprove a statement about every wrong. The statement there exist optimal binary search trees for which the root node has maximum probability would certainly be true.

Cedric, you can build a binary search tree for which the root node has maximum probability, i.e. any node in the tree can be the root.

Zipster, you can only insure that the root node has maximum probability. The ordering of the keys determines where every other node has to be to keep it a binary search tree. With three nodes there are six possible orderings for the search keys. Only two of those orderings result in a balanced tree with the key of maximum probability in the root. So two out of six are optimum. Whether the rest are optimum depends upon the actual probabilities, but you are not given the actual probabilties, just there relationship. Lets say we are dealing with a tree where the three nodes are right, right-right and right-right-right. If 2*p(1)+p(2)+2*p(3) > p(1)+2*p(2)+3*p(3) then p(1) being the root would be optimum even though it is unbalanced. If it is not true then a balanced tree would require accessing fewer nodes on average, but the key of maximum probability would not be the root. Well, there is also equal where both are optimum, but lets ignore that. Now the statement is about every tree and here we have a set of conditions for building a tree where it is not true so it is not true for every tree.

quote:

---

Original post by LilBudyWizer
Cedric, you can build a binary search tree for which the root node has maximum probability, i.e. any node in the tree can be the root.

---

Where did I say otherwise? I agree with that. It is, however, impossible to build a full binary search tree with A as the root.

Cédric