Glossary

ノード

• ランク (rank) またはインデックス (index)
  • 木を中間順巡回により訪問する順序
• サイズ (size) または重み (weight)
  • 部分木に含まれるノードの個数

二分木

• 二分木 (binary tree)
  • 各ノードが左の子と右の子を持つ根付き木
• サイズ付き二分木 (sized binary tree)
  • 各ノードがサイズを保持している二分木
• 二分探索木 (binary search tree)
  • ソートされた二分木
• サイズ付き二分探索木 (sized binary search tree)

平衡二分木

• サイズ付き平衡二分木 (sized self-balancing binary tree)
  • インデックスによるアクセスが効率的
  • 二分探索については不問
• 平衡二分探索木 (self-balancing binary search tree)
  • インデックスによるアクセスについては不問
  • 二分探索が効率的
• サイズ付き平衡二分探索木 (sized self-balancing binary search tree)
  • インデックスによるアクセスが効率的
  • 二分探索が効率的

重み平衡二分木

• 重み平衡二分木 (weight-balanced binary tree)
  • サイズ付き平衡二分木の一種
• 重み平衡二分探索木 (weight-balanced binary search tree)
  • サイズ付き平衡二分探索木の一種
  • Wikipedia の Weight-balanced tree に相当する