Promenade parmi les arbres

Cette semaine, c'est Renaud qui vous propose un #KataOfTheWeek : Arbres binaires de recherche

Briefing du Kata : Un BST est une structure de données ordonnée, qui permet de rechercher des éléments en temps logarithmique. Par exemple, l'arbre suivant est un BST :

Votre objectif sera de coder une fonction qui construit un arbre binaire à partir d'entiers passés en entrée.

L'arbre en sortie n'a pas besoin d'être équilibré (les chemins de la racine aux feuilles peuvent être de n'importe quelle longueur).

Quelques exemples :

• 42 -> 42
• 1 2 -> 1()(2)
• 2 1 3 -> 2(1)(3)
• 2 4 1 0 3 -> 2(1(0)())(4(3)())

Saurez-vous résoudre le problème ?

Bon courage !

Et voici une solution proposée par l'auteur :

Pour construire l'arbre, on peut coder la méthode d'insertion d'un élément dans l'arbre et insérer chaque élément à la suite.

Pour insérer un élément, on descend dans l'arbre en choisissant à chaque fois la bonne branche selon si la valeur à insérer est inférieure ou supérieure au nœud courant. Lorsque la branche dans laquelle on veut descendre n'existe pas (un nœud null), on insère le nouveau nœud à cet endroit.

fun insert(root: Node, data: Int): Node {
    var curr = root
    var shouldInsert = false

    while (!shouldInsert) {
        if (data < curr.data && curr.left != null) {
            curr = curr.left!!
        } else if (data >= curr.data && curr.right != null) {
            curr = curr.right!!
        } else {
            shouldInsert = true
        }
    }
    val newNode = Node(null, null, data)

    if (data < curr.data) {
        curr.left = newNode
    } else {
        curr.right = newNode
    }
    return newNode
}

fun buildTree(nodes: List<Int>): Node {
    val root = Node(null, null, nodes[0])
    nodes.drop(1).forEach { insert(root, it) }
    return root
}

Cette méthode construit ainsi un Arbre Binaire de Recherche en O(n.log(n)). Il est important de noter cela dit que l'arbre produit n'est pas équilibré, et donc qu'il peut potentiellement être équivalent à une simple liste chaînée (par exemple lorsque la liste en entrée est triée). Dans ce cas, la recherche ou l'insertion d'un élément se feront en O(n) au lieu de O(log(n)).

Enfin, pour conclure, il est important de rappeler qu'à part pour des cas d'usages très précis, il est rarement nécessaire de implémenter de nouveau soi-même un BST : par exemple, en Java/Kotlin, on peut utiliser un TreeSet, en lui fournissant éventuellement un comparateur custom. Le TreeSet de Java est implémenté avec un Red-Black Tree, qui s'équilibre à chaque insertion/enlèvement, et qui garantit donc des recherches et insertions en O(log(n)).

Votre équipe TakiVeille