导读：笛卡尔树结构由Vuillmin在解决范围搜索的几何数据结构问题时提出的，从数列中构造一棵笛卡尔树可以线性时间完成，需要采用基于栈的算法来找到在该数列中的所有最近小数。由此可知，笛卡尔树是一种特定的二叉树数据结构，可由数列构造，在范围最值查询、范围top k查询(range top k queries)等问题上有广泛应用。它具有堆的有序性，中序遍历可以输出原数列。
笛卡尔树结构由Vuillmin在解决范围搜索的几何数据结构问题时提出的，从数列中构造一棵笛卡尔树可以线性时间完成，需要采用基于栈的算法来找到在该数列中的所有最近小数。由此可知，笛卡尔树是一种特定的二叉树数据结构，可由数列构造，在范围最值查询、范围top k查询(range top k queries)等问题上有广泛应用。它具有堆的有序性，中序遍历可以输出原数列。
