**درخت دکارتی**

درخت دکارتی روی یک آرایه از اعداد به این صورت تعریف می‌شود که هر عضو آرایه به یک راس در درخت تبدیل می‌شود. خروجی پیمایش //In-Order// درخت دکارتی باید آرایه اصلی باشد. همچنین درخت دکارتی باید خاصیت //هرم کمینه// را داشته باشد. این درخت روی هر آرایه‌ای یکتا است. در تعریف داده ساختارهای treap و randomized binary search tree از درخت دکارتی به منظور جستجوی دودویی استفاده می‌شود. 

{{:آموزش:الگوریتم‌های_تکمیلی:cartesian.png?200|(درخت دکارتی)}}

**نحوه ساخت درخت دکارتی**

داده ساختارهای زیادی وجود دارند(مثلا درخت پاره‌خطی) که اگر آرایه‌مان را درون آن‌ها ذخیره کنیم، می‌توانیم در $O(logn)$ مقدار کمینه هر بازه‌ای را بدست آوریم. برای ساخت یک درخت دکارتی از یکی از این‌ها استفاده می‌کنیم.
ابتدا مقدار مینیمم کل آرایه را پیدا می‌کنیم و به‌عنوان ریشه درخت دکارتی قرار می‌دهیم. سپس به طور بازگشتی درخت دکارتی عناصر سمت چپ و راست مقدار مینیمم را پیدا می‌کنیم. درخت دکارتی سمت چپ را به‌عنوان فرزند چپ ریشه و درخت دکارتی سمت راست را به عنوان فرزند راست ریشه قرار می‌دهیم.
<code c++>
node get_root_cartesian_tree(int left, int right) {
    int min_index = get_min(left, right);
    node left_tree = get_root_cartesian_tree(left, min_index);
    node right_tree = get_root_cartesian_tree(min_index, right);
    node root;
    root.value = array[min_index];
    root.left_child = left_tree;
    root.right_child = right_tree;
    return root;
}
</code>

با این روش درخت دکارتی برای آرایه‌ای از $n$ عنصر در $O(n.logn)$ ساخته می‌شود.

**کاربردهای درخت دکارتی**

یکی از کاربردهای درخت دکارتی در تبدیل مساله //RMQ// به مساله //LCA// است. به این شکل که برای حل مساله //RMQ// می‌توانیم //Cartesian Tree// متناظر با آرایه را بسازیم، سپس مقدار کمینه یک بازه در آرایه به کوچک‌ترین جد مشترک رئوس متناظر دو سر بازه در درخت دکارتی تبدیل می‌شود.

  * [[https://en.wikipedia.org/wiki/Cartesian_tree]]