I am studying some old past test questions. Is this search tree correctly pruned?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
I once implemented this in common lisp and running my program on your tree tells me that the pruned nodes are the one you marked and also the rightmost leaf and its parent. The output of the program gives $\alpha$ and $\beta$ values for each node (if you mark from A through X in a BFS manner, left-to-right. Then O and J are pruned).
MIN: K -INFTY 11 [v:11] MIN: L 11 INFTY [v:9] MAX: E 11 INFTY [v:11] MIN: M -INFTY 4 [v:4] MIN: N 4 11 [v:13] MAX: F 4 11 [v:13] MIN: B -INFTY 11 [v:11] MIN: P 11 12 [v:12] MIN: Q 12 INFTY [v:8] MIN: R 12 INFTY [v:4] MAX: G 12 INFTY [v:12] MIN: C 11 12 [v:12] MIN: S 12 INFTY [v:9] MIN: T 12 13 [v:13] MIN: U 13 INFTY [v:1] MAX: H 13 INFTY [v:13] MIN: V 12 13 [v:12] MIN: W 12 13 [v:9] MAX: I 12 13 [v:12] MIN: D 12 13 [v:12] MAX: A 12 INFTY [v:12] 12 21 T
I was close. Here's an answer from my tutor which makes sense:
There should be some pruning on the last branch.
When descending into the third branch from the main node, the top criteria is >=12. The first sub-tree of that node sets its value to 13 (>12), so the next sub-tree is expanded. When the value of the node changes to 12 after the second sub-tree is completed, the condition triggers.
It doesn't matter what the value of the last sub-tree is. If the value is > 12 then min will choose it and max will choose the previous top-level sub-tree (value 12). if the value is <= 12 then min will choose 12 and the overall value doesn't change. For this reason the last two nodes (both value 10) are pruned before being examined.
I think he may have slightly messed up his wording in the last paragraph, but basically we are not going to improve on the 12, as min will select 12 and less, so there's no point in checking anymore.