スケープゴート木
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/01/26 09:27 UTC 版)
スケープゴートツリーは計算機科学における平衡二分探索木の一種である。Arne Anderssonと、Igal Galperinとロナルド・リベストによって発明された[1]。探索、挿入、削除の償却時間計算量がO(log n)であり、探索においては最悪時間計算量もO(log n)である。
- ^ a b Galperin, Igal; Rivest, Ronald L. (1993). Scapegoat trees (PDF). Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms. Philadelphia: Society for Industrial and Applied Mathematics. pp. 165–174. ISBN 0-89871-313-7。
- ^ Morin, Pat. “Chapter 8 - Scapegoat Trees”. Open Data Structures (in pseudocode) (0.1G β ed.) 2017年9月16日閲覧。
[続きの解説]
「スケープゴート木」の続きの解説一覧
- 1 スケープゴート木とは
- 2 スケープゴート木の概要
- 3 語源
- スケープゴート木のページへのリンク
