バイナリーサーチツリー for TypeScript を ChatGPT に書かせると
入学しようかなと思う程度には、放送大学を好きなしょっさんです。
今朝ものんびりと見ていたんです。こちら。
今日の内容はバイナリーサーチツリー。この科目 Python でプログラム作ってアルゴリズムを学ぶ学習やってるんです。
授業の中で「これが最適なプログラムではありません。ChatGPTなどにも聞いてみましょう」みたいなこというんです。
なるほど。
ということで、適当な乱数をバイナリーサーチツリーにつっこんで、表示させるプログラムを ChatGPT4o に TypeScript で作ってもらいました。
表示のトコが授業と同じようにならなかったので、その辺だけ手を入れて作り直してみたコードがこちらです。
class TreeNode {
value: number;
left: TreeNode | null;
right: TreeNode | null;
constructor(value: number) {
this.value = value;
this.left = null;
this.right = null;
}
}
export class BinarySearchTree {
root: TreeNode | null;
constructor() {
this.root = null;
}
// ノードの挿入
insert(value: number): void {
const newNode = new TreeNode(value);
if (this.root === null) {
this.root = newNode;
} else {
this.insertNode(this.root, newNode);
}
}
private insertNode(node: TreeNode, newNode: TreeNode): void {
if (newNode.value < node.value) {
if (node.left === null) {
node.left = newNode;
} else {
this.insertNode(node.left, newNode);
}
} else {
if (node.right === null) {
node.right = newNode;
} else {
this.insertNode(node.right, newNode);
}
}
}
// ノードの検索
search(value: number): boolean {
return this.searchNode(this.root, value) !== null;
}
private searchNode(node: TreeNode | null, value: number): TreeNode | null {
if (node === null) {
return null;
}
if (value < node.value) {
return this.searchNode(node.left, value);
} else if (value > node.value) {
return this.searchNode(node.right, value);
} else {
return node;
}
}
// ノードの削除
remove(value: number): void {
this.root = this.removeNode(this.root, value);
}
private removeNode(node: TreeNode | null, value: number): TreeNode | null {
if (node === null) {
return null;
}
if (value < node.value) {
node.left = this.removeNode(node.left, value);
return node;
} else if (value > node.value) {
node.right = this.removeNode(node.right, value);
return node;
} else {
// 値が一致するノードが見つかった場合
if (node.left === null && node.right === null) {
return null; // 葉ノードの場合
}
if (node.left === null) {
return node.right;
}
if (node.right === null) {
return node.left;
}
// 両方の子ノードが存在する場合、右部分木の最小値を探して置き換える
const tempNode = this.findMinNode(node.right);
node.value = tempNode.value;
node.right = this.removeNode(node.right, tempNode.value);
return node;
}
}
private findMinNode(node: TreeNode): TreeNode {
while (node.left !== null) {
node = node.left;
}
return node;
}
// ツリーの表示（in-order traversalを利用、深さ情報を出力）
display(): void {
this.inOrderTraversal(this.root, 0);
}
private inOrderTraversal(node: TreeNode | null, depth: number): void {
if (node !== null) {
this.inOrderTraversal(node.left, depth + 1);
// console.log(`Value: ${node.value}, Depth: ${depth}`);
for (let i = 0; i < depth; i++) {
process.stdout.write('-');
}
console.log(node.value);
this.inOrderTraversal(node.right, depth + 1);
}
}
}
function generateUniqueRandomNumbers(
min: number,
max: number,
count: number
): number[] {
if (count > max - min + 1) {
throw new Error('範囲に対して数が多すぎます');
}
const numbers: number[] = [];
for (let i = min; i <= max; i++) {
numbers.push(i);
}
for (let i = numbers.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
[numbers[i], numbers[j]] = [numbers[j], numbers[i]];
}
return numbers.slice(0, count);
}
// 1から10000の乱数を1000個、重複なく生成して表示する
const bst = new BinarySearchTree();
generateUniqueRandomNumbers(1, 10000, 100).forEach(value => bst.insert(value));
console.log('In-order Traversal with Depth:');
bst.display(); // ノードの値と深さが表示される
いやー凄いなー。手を入れたのは、ここだけ。
// console.log(`Value: ${node.value}, Depth: ${depth}`);
for (let i = 0; i < depth; i++) {
process.stdout.write('-');
}
console.log(node.value);これ以外は生成されたコードだけです。もっと洗練されたコードを作ることは可能だと思いますが、ちょっとお願いしたらすぱっと書いてくれるの本当にヤバイ。
出力サンプルはこんな感じ。
In-order Traversal with Depth:
-----67
----235
---428
------605
-------660
--------714
-----890
----945
--1384
:
(中略)
:
--9102
---9312
-9451
--9516
----9572
---9676
-----9700
------9756
----9860
-----9996
アルゴリズム面白いし生成AIも便利だけど、自分で考えずにこうやって出てくるのも考えものだな。とかちょっと冷静になってしまう。
おまけ
テストコードは GitHub Copilot に作ってもらいました。Jest です。
import {BinarySearchTree} from '../src/bst';
describe('BinarySearchTree', () => {
test('insert and search', () => {
const bst = new BinarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(3);
bst.insert(7);
bst.insert(12);
bst.insert(18);
expect(bst.search(10)).toBe(true);
expect(bst.search(5)).toBe(true);
expect(bst.search(15)).toBe(true);
expect(bst.search(3)).toBe(true);
expect(bst.search(7)).toBe(true);
expect(bst.search(12)).toBe(true);
expect(bst.search(18)).toBe(true);
expect(bst.search(100)).toBe(false);
});
test('remove', () => {
const bst = new BinarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(3);
bst.insert(7);
bst.insert(12);
bst.insert(18);
expect(bst.search(10)).toBe(true);
bst.remove(10);
expect(bst.search(10)).toBe(false);
expect(bst.search(5)).toBe(true);
bst.remove(5);
expect(bst.search(5)).toBe(false);
expect(bst.search(15)).toBe(true);
bst.remove(15);
expect(bst.search(15)).toBe(false);
expect(bst.search(3)).toBe(true);
bst.remove(3);
expect(bst.search(3)).toBe(false);
expect(bst.search(7)).toBe(true);
bst.remove(7);
expect(bst.search(7)).toBe(false);
expect(bst.search(12)).toBe(true);
bst.remove(12);
expect(bst.search(12)).toBe(false);
expect(bst.search(18)).toBe(true);
bst.remove(18);
expect(bst.search(18)).toBe(false);
});
test('remove root', () => {
const bst = new BinarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(3);
bst.insert(7);
bst.insert(12);
bst.insert(18);
expect(bst.search(10)).toBe(true);
bst.remove(10);
expect(bst.search(10)).toBe(false);
});
});
いいなと思ったら応援しよう！
