赤黒木を実装 / fujimisakari blog最近、業務委託で参画させていただいてる会社の方から新たな言語を使うときは まず赤黒木を作ってみるといいよと聞きGoで実装してみましたー red-black-treeコマンドに引数で数字を渡すと赤黒木として表示させる実装になってます 赤黒木について赤黒木は「平衡木」というデータ構造のひとつで、ツリー構造のうち、根ノードから子を持たない末端の葉ノードまでの深さがなるべく等しくなるような構造になります。 ざっくりとした特徴でいえば 二分木の一種ですが、ノードを赤と黒で色分けする 根から葉までがほぼ同じ数のノードを経由するため探索する際の平均の計算時間を短縮することができる ノードの挿入や削除時に深さのバランスが保たれるようバランス(回転)と呼ばれる操作で、ツリーの再構築を行う 赤黒木の実装に次の条件を満たす必要がある 各ノードは赤または黒に区分される あるノードが赤ならばその子ノードは必ず黒であ
