Promenade parmi les arbres - Solution

On se retrouve aujourd'hui pour la solution du précédent #KataOfTheWeek proposé par Renaud en début de semaine !

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 réimplementer 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)).

A bientôt pour un nouveau #KataOfTheWeek !

TakiVeille

TakiVeille