右に分岐する不均衡な二分木を作成するにはどうすればよいですか?

Question

私が望むもののイメージ：

興味のある方のために：この図はこの記事（無料で入手できるバージョンは見つかりませんでした）そして、k-バケット(四角形) バイナリ ID 空間のますます大きくなるプレフィックスをカバーします。

このタイプのツリーを作成する方法について、どなたか提案していただければ幸いです。

• 各葉はバケツ/正方形です
• 葉っぱにだけバケツがついています。
• 木は右に枝分かれし、各枝のスペースは前の枝の半分になります。

編集

Gonzalo Medina の素晴らしい回答の数字の一部を少し調整して、自分が求めているものに近づけましたが、何が起こっているのか、コードがどのように機能するのか、まったくわからないと言わざるを得ません。

私が今やりたいのは、ボックスが垂直軸上で重ならないようにツリーを広くすることです。

\begin{forest}
for tree={parent anchor=south, child anchor=north},
s sep=30pt,
[
  [,draw,text width=4cm,edge label={node[midway,left=12pt]{$1$}}]
  [,shape=coordinate,edge label={node[midway,right=10pt]{$0$}}
    [,draw,text width=2cm,edge label={node[midway,left=4pt]{$1$}}]
    [,shape=coordinate,s sep=-\pgflinewidth,edge label={node[midway,right=4pt]{$0$}}
      [,draw,text width=0.5cm,edge label={node[midway,left]{$1$}}]
      [,draw,text width=0.5cm,edge label={node[midway,right]{$0$}}]
    ]
  ]
]
\end{forest}

また、いくつかのボックス内にテキストを入れたい場合はどこに配置すればよいでしょうか?

Answer 1

強力なforestパッケージ：

\documentclass{article}
\usepackage{forest}

\begin{document}

\begin{forest}
for tree={parent anchor=south, child anchor=north},
s sep=30pt,
[
  [,draw,text width=3cm,edge label={node[midway,left=4pt]{$0$}}]
  [,shape=coordinate,edge label={node[midway,right]{$1$}}
    [,draw,text width=2cm,edge label={node[midway,left]{$0$}}]
    [,shape=coordinate,s sep=-\pgflinewidth,edge label={node[midway,right]{$1$}}
      [,draw,text width=1cm,edge label={node[midway,left]{$0$}}]
      [,draw,text width=1cm,edge label={node[midway,right]{$1$}}]
    ]
  ]
]
\end{forest}

\end{document}

l、l sep(垂直距離)、s sep(水平距離)の値を使用して、ツリーの形状を変更できます (これらのキーの説明については、パッケージのドキュメントを参照してください)。小さな例:

\documentclass{article}
\usepackage{forest}

\begin{document}

\begin{forest}
for tree={parent anchor=south, child anchor=north},
for tree={l =-0ex}
[,s sep=3cm
  [,draw,text width=3cm,edge label={node[midway,above left=0pt]{$0$}}]
  [,s sep=1.5cm,shape=coordinate,edge label={node[midway,above right]{$1$}}
    [,draw,text width=2cm,edge label={node[midway,left=8pt]{$0$}}]
    [,shape=coordinate,s sep=-\pgflinewidth,edge label={node[midway,right=8pt]{$1$}}
      [,draw,text width=1cm,edge label={node[midway,left=6pt]{$0$}}]
      [,draw,text width=1cm,edge label={node[midway,right=6pt]{$1$}}]
    ]
  ]
]
\end{forest}

\end{document}

ボックスにテキストを入れる場合は、すべてのボックスの高さが同じになるようにスタイルを定義することをお勧めします。

\documentclass{article}
\usepackage{forest}

\begin{document}
\forestset{
myempty/.style={
  draw,
  text width=#1,
  minimum height=16pt,
  anchor=north
  }
}

\begin{forest}
for tree={parent anchor=south, child anchor=north},
for tree={l =2ex}
[,s sep=1cm
  [texta,myempty=3cm,edge label={node[midway,above left=0pt]{$0$}}]
  [,s sep=1cm,shape=coordinate,edge label={node[midway,above right]{$1$}}
    [textb,myempty=2cm,edge label={node[midway,left=8pt]{$0$}}]
    [,shape=coordinate,s sep=-\pgflinewidth,edge label={node[midway,right=8pt]{$1$}}
      [textc,myempty=1cm,edge label={node[midway,left=6pt]{$0$}}]
      [textd,myempty=1cm,edge label={node[midway,right=6pt]{$1$}}]
    ]
  ]
]
\end{forest}

\end{document}