二分探索木のプログラム
https://gyazo.com/c8b723080430a20fd18197b849d9fff6
二分木 (にぶんぎ・Binary Tree)とは木構造のデータで、ノードが左と右の2つの子を持つデータ構造を言う
とくにプログラミングの分野では、二分探索木(Binary Search Tree)というデータ構造がよく言及される
二分探索木は二分木の一種で、次のような特徴を持つ
左の子とその子孫はすべてそのノードよりも数値が小さい
右の子とその子孫はすべてそのノードよりも数値が大きい
上記の図がそれに当たる。詳しくはWikipediaを見よ
code:bintree.ts
interface BinaryTree {
// データを追加
add(n: number): void;
// データが存在するか
has(n: number): boolean;
// データを昇順/降順で列挙
iterate(order: "ascendant" | "descendant"): IterableIterator<number>
}
type Node = {
value: number,
left?: Node
right?: Node
};
function bintree(): BinaryTree {
let root: Node | undefined;
function _add(node: Node, n: number) {
if (n <= node.value) {
if (node.left) {
_add(node.left, n);
} else {
node.left = {value: n};
}
} else {
if (node.right) {
_add(node.right, n);
} else {
node.right = { value: n };
}
}
}
function add(n: number) {
if (!root) {
root = { value: n };
} else {
_add(root, n);
}
}
function _has(node: Node | undefined, n: number): boolean {
if (!node)
return false;
else if (node.value === n)
return true;
else if (n <= node.value)
return _has(node.left, n);
else
return _has(node.right, n);
}
function has(n: number) {
return _has(root, n);
}
function* ascendant(node: Node | undefined): IterableIterator<number> {
if (!node) return;
yield* ascendant(node.left);
yield node.value;
yield* ascendant(node.right)
}
function* descendant(node: Node | undefined): IterableIterator<number> {
if (!node) return;
yield* descendant(node.right);
yield node.value;
yield* descendant(node.left);
}
function* iterate(order: "ascendant" | "descendant"): IterableIterator<number> {
if (order === "ascendant") {
yield* ascendant(root)
} else {
yield* descendant(root);
}
}
return { add, iterate, has };
}
hr.icon
以下解説
上記は二分探索木のもっともシンプルな実装である
データの追加、探索、列挙ができる
add, has, iterate のすべてが再帰で記述できる
特に、データを昇順と降順で列挙することの違いが、左の子を先に反復するか右の子を先に反復するかの違いしか無いのがとても美しい
上記の実装では、やや複雑な木からのデータの削除を省いている
また平衡二分探索木ではないので、探索と追加の最悪計算量はO(N)になっている
平衡二分探索木の実装はいくつかあるがどれも複雑なのでまだ実装したことがない
そのうち挑戦してみたい