Arbre cartésien

vignette|240x240px| Une séquence de nombres et l'arbre cartésien qui en dérive. En algorithmique, un arbre cartésien est un arbre binaire construit à partir d'une séquence de nombres. Il est défini comme un tas dont un parcours symétrique de l'arbre renvoie la séquence d'origine. Introduits par Jean Vuillemin (1980) dans le cadre des structures de données de recherche par plage géométrique, les arbres cartésiens ont également été utilisés dans la définition des arbres-tas et des structures de données d'arbres de recherche binaire randomisés pour les problèmes de recherche dichotomique. L'arbre cartésien pour une séquence peut être construit en temps linéaire en utilisant un algorithme basé sur la structure de pile pour trouver toutes les valeurs plus petites les plus proches dans une séquence. L'arbre cartésien associé à une séquence de nombres distincts est un arbre binaire défini de manière unique par les propriétés suivantes : L'arbre cartésien d'une séquence a un nœud pour chaque élément de la séquence, et chaque nœud est associé à un seul élément. Un parcours symétrique de l'arbre (c'est-à-dire un parcours qui renvoie pour tout nœud, d'abord le résultat du parcours de son fils gauche, puis le nœud lui-même, puis le parcours de son fils droit) de l'arbre donne la séquence d'origine. En d'autres termes, le sous-arbre gauche se compose des valeurs antérieures à la racine dans l'ordre de séquence, tandis que le sous-arbre droit se compose des valeurs postérieures à la racine, et une contrainte de classement similaire s'applique à chaque nœud inférieur de l'arborescence. L'arbre est un tas binaire : le parent éventuel de tout nœud a une valeur plus petite que le nœud lui-même. En accord avec la définition d'un tas, la racine de l'arbre doit être le plus petit nombre de la séquence. Partant de là, on obtient une autre définition, récursive de l'arbre comme suit : la racine est la valeur minimale de la séquence, et les sous-arbres gauche et droit sont les arbres cartésiens pour les sous-séquences à gauche et à droite de la valeur racine.