TypeScriptで木構造と遊ぶ - たーせる日記

あらすじ

突然ですが、やむにやまれぬ事情により木構造と戯れることになりました。緊急クエストです。 僕の大嫌いな再帰……

1年生の頃、C言語で難しいと感じたのは、メモリの動的確保と再帰アルゴリズムの実装だった。いまだにメモリ漏れ/2重解放といった致命的なミスを時々やっちゃう。
— たーせる (@tercel_s) 2010年5月26日

やりたいこと

かなり長くなりそうな予感がするので最終目標から書いておくと、ルートが同じ木構造 2 つが与えられたとき、下図のようにマージする処理を TypeScript で実装します。

f:id:tercel_s:20190720202032p:plain:w500
今日はコードと図版が多め・日本語少なめです。文章を書くのがあまりにもしんどかったので図解に逃げました。

データ型の定義

今回は簡単のため、木構造のノードを表すデータ型を以下のように定義します。

interface Node {
  id: string;
  children: Node[];  // 子ノード
}

チャームポイントは、Node 型が再帰的に定義されていること。子ノードを格納するメンバ children が Node 型になっているので、以下のようにいくらでも深い階層を持ったデータを表現できます。
f:id:tercel_s:20190720190150p:plain:w200

上図のようなデータ構造は、 TypeScript で以下のように記述できます。簡単ですね。

  const tree: Node = {
    id: '(root)',
    children: [
      { id: 'node1', children: [
        { id: 'node1-1', children: []},
        { id: 'node1-2', children: []},
        { id: 'node1-3', children: [
          {id: 'node1-3-1', children: []},
          {id: 'node1-3-2', children: []},
          {id: 'node1-3-3', children: []},
        ]},
      ]},
      { id: 'node2', children: [
        { id: 'node2-1', children: [
          {id: 'node2-1-1', children: []},
          {id: 'node2-1-2', children: []},
        ]},
        { id: 'node2-2', children: []},
      ]},
    ]};

注意点として、これ以降は以下2点を前提としています。

ノードの参照がループしてはなりません
各ノードのIDは一つの木の中で必ず一意でなくてはなりません

それではさっそくいってみよう、やってみよう。

Tips1: 木構造を配列に変換する

まずは、木構造を深さ優先でトラバースし、その結果を配列に詰めて返してみようと思います。

f:id:tercel_s:20190720191819p:plain:w410

もともとは、階層構造を持つデータを木構造で保持しておき、いざというときに配列に変換してリストボックスにバインドするというアクロバティックな仕様を満たすために作りました。

この Tips 自体はマージ処理と全く関係ないのですが、深さ優先探索は木構造を扱う上で頻出ですので、準備運動として取り上げました。

  /** 与えられた木構造のすべてのノードのidを
    * 深さ優先順の配列形式に変換して返却します */
  convertToArray(root: Node): string[] {
    return (root.children || [])
      .reduce((arr, c) => arr.concat(this.convertToArray(c)), [root.id]);
  }

  /** 与えられた木構造のうち、ルート以外のノードのidを
    * 深さ優先順の配列形式に変換して返却します */
  convertToArrayExceptForRoot(root: Node): string[] {
    return this.convertToArray(root).slice(1);
  }

Tips2: ルートからの経路情報を得る

こちらも探索問題です。

データ構造上、各ノードは親 → 子という一方向の参照しか持っていないため、祖先からの経路を知るにはルートからあらゆる経路をしらみつぶしに探索しなくてはなりません。ここでも深さ優先探索を使っています。

f:id:tercel_s:20190720193357p:plain:w410

  /** 指定したidに一致するノード、およびルートからの経路を返却します */
  private find(root: Node, id: string, path: string[] = []): { node: Node, path: string[] } {
    const nextPath: string[] = path.concat([root.id]);

    return root.id === id ? ({ node: root, path: nextPath }) :
      (root.children || [])
        .map(child => this.find(child, id, nextPath))
        .find(x => !!x.node) || ({ node: null, path: [] });
  }

  /** 指定したidに一致するノードまでの、ルートからの経路を返却します */
  private findPath(root: Node, id: string): string[] {
    return this.find(root, id).path;
  }

  /** 指定したidに一致するノードを返却します */
  private findNode(root: Node, id: string): Node {
    return this.find(root, id).node;
  }

Tips2.5: 1階層上までの経路情報を得る

先ほどの応用技で、自分自身の一つ上の親ノードを得る方法です。アルゴリズム的にはあまりスマートではないのですが、Tips2 で祖先からの経路情報が分かるので、自分自身の一つ手前 = 親という理論で一階層上の経路情報を求めています。

f:id:tercel_s:20190720194227p:plain:w410

  /** 指定したidに一致するノードの親ノード、およびルートからの経路を返却します */
  private findParent(root: Node, id: string): { node: Node, path: string[] } {
    const path = this.findPath(root, id);
    return path.length < 2 ? ({node: null, path: []}) :
      this.find(root, path.reverse()[1]);
  }

Tips3: 部分木を抽出する

ここから先は、言葉だけで説明するのが少し難しくなってきます。

「ルートから自分自身までのパスと、自分自身の子ノードすべてを含む部分木」を抽出します。

下図のように、パラメータに node2-1 を与えると、ルートからの階層の深さを維持したまま node2-1 とその子どもたち全員から成る新たな木が構築されます。

f:id:tercel_s:20190720195327p:plain:w460

ちなみに、もしも node2-1 に孫や曾孫がいる場合も、みんなまとめて新たな部分木の仲間になります。

  /** 指定したidに一致するノードを持つ部分木を抽出します
    * 子ノードはそのまま部分木になります */
  private extractSubTree(root: Node, id: string): Node {
    const { node, path } = this.find(root, id);
    return path.reverse()
      .filter(x => x !== id)
      .reduce((n, x) => ({ id: x, children: [n] }), node);
  }

Tips4: ノードをディープコピーする

これは簡単すぎるので図解不要ですね。

このあと木構造をこねくり回す際、元のデータに対する破壊的な操作（子ノードへの参照の継ぎ替えなど）を避けるために、中身はそっくり同じコピー品を作ります。

  /** 指定したノードをディープコピーします */
  private copy(root: Node): Node {
    return ({ id: root.id, children: (root.children || []).map(x => this.copy(x)) });
  }

Tips5: 部分木を除去する

指定したIDを持つノードに対して部分木を求め、それを元の木構造から除去します。これも言葉で伝えようとすると細かすぎて伝わらないのですが、図解するとこういうことです。

f:id:tercel_s:20190720200538p:plain:w460

ちなみに、指定したIDを持つノードを消した結果、親が生き残る場合とそうでない場合があります。親が自分以外の子を持たない場合は、親ごと消えます。

  /** 指定したidに一致するノードを持つ部分木を、
    * 元の木構造から取り除いた結果を返却します */
  private removeSubTree(root: Node, id: string, destructive: boolean = false): Node {
    const subTree = destructive ? root : this.copy(root);
    const { node } = this.findParent(subTree, id);
    if (!node) return subTree;

    node.children = (node.children || []).filter(x => x.id !== id);
    return !!node.children.length ? subTree :
      this.removeSubTree(subTree, node.id, true);
  }

Tips6: 子ノードの有無を判定する（1親等）

現在注目しているノードから見て1親等の子ノードのいずれかが、指定したIDに一致するかどうかをチェックします。

もしも指定したIDに一致する子ノードが存在する場合はそれをそのまま返却します。存在しなければnullを返却します。

f:id:tercel_s:20190720202909p:plain:w200

  /** 自ノードの子に、指定したidを持つノードがあれば返却します */
  private findChild(target: Node, id: string): Node {
    if (!target) return null;
    const child = (target.children || []).filter(x => x.id === id);
    return child.length ? child[0] : null;
  }

これだけだと有難みが今ひとつ分かりませんが、次のマージ処理で密かに大切な役割を果たしてくれます。

Tips7: 同じルートを持つ2つの木をマージする

これですべての準備が整ったので、最後にいよいよマージ処理を実装します。

f:id:tercel_s:20190720202032p:plain:w500

  /** 2つの木構造をマージした結果を返却します */
  private merge(target: Node, source: Node): Node {
    if (target.id !== source.id) return null;
    if (!(target.children || []).length) return source;
    if (!(source.children || []).length) return target;

    const newChildren: Node[] = (target.children || [])
      .map(c => {
        const otherChild = this.findChild(source, c.id);
        return otherChild ? this.merge(c, otherChild) : c;
      });

    newChildren
      .push(...(source.children || [])
        .filter(c => !this.findChild(target, c.id)));

    const ret = this.copy(target);
    ret.children = newChildren;
    return ret;
  }

Tips3, Tips5 と合わせることで、木構造を2つに分けたりくっつけたりすることができるようになります。

おまけ: 木構造を HTML 化して Angular のテンプレート内に埋め込む

せっかくだから TypeScript でいじくり回した木構造を視覚化したい！というのは自然な願望でしょう（強引な動機付け）。

ただし残念ながら、木構造をバインドする仕掛けは Angular に用意されていないので、自力でなんとかするしかありません。具体的には、表示したい HTML を自分で生成して、テンプレート側の [innerHTML] にバインディングするという超デンジャラスな方法を採ることになります。

生成したい HTML

<ul>
  <li>(root)<ul>
      <li>node1<ul>
          <li>node1-1</li>
          <li>node1-2</li>
          <li>node1-3<ul>
              <li>node1-3-1</li>
              <li>node1-3-2</li>
              <li>node1-3-3</li>
            </ul>
          </li>
        </ul>
      </li>
      <li>node2<ul>
          <li>node2-1<ul>
              <li>node2-1-1</li>
              <li>node2-1-2</li>
            </ul>
          </li>
          <li>node2-2</li>
        </ul>
      </li>
    </ul>
  </li>
</ul>

表示イメージ^{※ すみません、パソコンからご覧ください}

(root)
- node1
  - node1-1
  - node1-2
  - node1-3
    - node1-3-1
    - node1-3-2
    - node1-3-3
- node2
  - node2-1
    - node2-1-1
    - node2-1-2
  - node2-2

そんなわけで、木構造を HTML の <ul>, <li> として組み立てる createHtmlForTree() をおまけで置いておきます。

app.component.ts

import { Component, SecurityContext } from '@angular/core';
import { DomSanitizer, SafeHtml } from '@angular/platform-browser';

@Component({
  selector: 'app-root',
  templateUrl: './app.component.html',
  styleUrls: ['./app.component.css']
})
export class AppComponent {
  constructor(private sanitizer: DomSanitizer) { }

  createHtmlForTree(root: Node): SafeHtml {
    return this.sanitizer.bypassSecurityTrustHtml(
      `<ul><li>${this.sanitizer.sanitize(SecurityContext.HTML, root.id)}${this.createHtmlUlForTree(root)}</li></ul>`
    );
  }

  private createHtmlUlForTree(root: Node): string {
    if (!root) return '';
    const innerHtml = this.createHtmlLiForTree(root);
    return !innerHtml ? '' : `<ul>${innerHtml}</ul>`;
  }

  private createHtmlLiForTree(root: Node): string {
    if (!root) return '';
    return (root.children || [])
      .map(x => `<li>${this.sanitizer.sanitize(SecurityContext.HTML, x.id)}${this.createHtmlUlForTree(x)}</li>`)
      .join('');
  }
}

DOM ツリー上、<ul> と <li> が相互に入れ子になるため、内部的には <ul> 構築用のメソッドと <li> 構築用のメソッドを互いに呼び合う構造になっています。

さらに、以下のような CSS を当てると、いい感じに罫線とかが引かれて木構造っぽい見た目になります。

styles.css

ul, li {
  padding: 0;
  margin: 0;
}

ul {
  line-height: 1.8;
  list-style: none;
}

ul ul {
  margin-left: 1em;
}

ul ul li {
  position: relative;
  padding-left: 1.15em;
}

ul ul li::before {
  position: absolute;
  top: 0;
  left: 0;
  bottom: 0;
  content: '';
  border-left: 1px solid #aaa;
}

ul ul li:last-child::before {
  height: 0.9em;
}

ul ul li::after {
  position: absolute;
  top: 0.9em;
  left: 0;
  width: 0.7em;
  content: '';
  border-top: 1px solid #aaa;
}

では、また。