决策树（Decision Tree）

Last Updated: 2024-04-08 14:56:14 Monday

-- TOC --

Decision tree is a FULL binary tree，which means that a decision can be made only when a leaf is reached from root. Decision tree model can be used to prove the lower bound of any comparison sorting algorithms, which is \(\Omega(n\log{n})\).

当使用决策树来对搜索问题进行建模时，需要清楚的认识到，不同于程序员一般认知的BSTree，搜索决策树必须要到达其某个Leaf节点，才能够得到一个确定的决策，并且决策树一定是Full状态，即节点要么没有child，要么左右child全有。

Desicion tree is a model that is especially useful when we are concerned with only the number of comparisions made by an algorithm. We assume that comparisons have at most two outcomes. The decision tree provides a useful way to measure the performance of algorithms.

在搜索决策树时，Cost为从root出发到达某个Leaf时，所有经过edge的权重和。Worst case就是这个cost最大的情况。一般情况下，Edge的cost都是1，左右相等，此时Cost与经过的节点数相同，节点数代表了某个关键操作的数量，比如Comparison。如果搜索结果影响cost，比如在某个高度扔鸡蛋时，鸡蛋broken与否，cost就不同，此时最优的树结构不再是平衡的，叫做Lopsided tree。Lopsided tree在全网的资料非常少！

用Decision Tree Model证明算法Lower Bound的关键，就是\(2^{height}\ge\textit{number of leaf}\)。

本文链接：https://cs.pynote.net/ag/tree/202401202/

-- EOF --

-- MORE --