二分探索木(binary search tree)から近似値を求める

二分探索木のデータとtargetが与えられる。二分探索木のデータの中からtargetの近似値を求める。

例えば次のような二分探索木のデータとtarget 5が与えられるとき、答えは6である。

        8
        /\
       3  10
      /\   \
     1 6   14
       /\   /
      4  7 13

ref: https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2%E6%9C%A8

二分探索木の定義

二分探索木のデータ構造は「左の子孫の値 ≤ 親 ≤ 右の子孫の値」という制約を持つ。与えられた値の近似値を求めるには、一時的にそれまで見つかった近似値を保持しておいて、次の子ノード、孫ノード、…と子ノードが存在しなくなるまで探索を続ける必要があるため、計算量はどのアルゴリズムでも最低O(n)となるはず。

子ノードが存在しないときに保持していた近似値が解となる。

与えられる引数

引数はtreeとtargetが与えられる。

treeオブジェクトは数値value、treeオブジェクトleft、treeオブジェクトrightのプロパティを持つ再帰的なオブジェクト。targetは数値。

アルゴリズム実装(1) O(n)

ノードが存在しないとき、treeオブジェクトはnullをとる。近似値を保持しておいて、tree === nullとなるまでループを続ける。二分探索木の定義から、leftプロパティのvalueは必ず現在のノードのvalueより小さく、rightプロパティのvalueは必ず現在のノードのvalueより大きい。

function findClosestValueInBst(tree, target) {
    return traverseNode(tree, target, null);
}

function traverseNode(node, target, closest) {
    while (node !== null) {
        if (closest === null || Math.abs(target - closest) > Math.abs(target - node.value)) {
            closest = node.value
        }
        if (target < node.value) {
            node = node.left
        } else if (target > node.value) {
            node = node.right
        } else {
            break
        }
    }
    
    return closest
}

アルゴリズム実装(2) O(n)

メモリ的には優しくないかもしれないが、再帰関数のほうが理解しやすいかも？

function findClosestValueInBst(tree, target) {
    return traverseNode(tree, target, null);
}

function traverseNode(node, target, closest) {
    if (node === null) {
        return closest
    }
    if (closest === null || Math.abs(target - closest) > Math.abs(target - node.value)) {
        closest = node.value
    }
    if (target < node.value) {
        return traverseNode(node.left, target, closest)
    } else if (target > node.value) {
        return traverseNode(node.right, target, closest)
    }
    
    return closest
}