回答編集履歴
2
加筆
answer
CHANGED
|
@@ -2,4 +2,7 @@
|
|
|
2
2
|
|
|
3
3
|
(根からじゃなく)左端の末っ子を起点に辿れば小さい順になります。
|
|
4
4
|
|
|
5
|
-
※ "set::begin() が二分木の根を指す" なんて、標準C++規格にはどこにも書かれていません。
|
|
5
|
+
※ "set::begin() が二分木の根を指す" なんて、標準C++規格にはどこにも書かれていません。
|
|
6
|
+
さらに言えば "std::set は二分木で実装されている(or されなければならない)" とも書かれていません。
|
|
7
|
+
言語規格書には 検索/削除が時間計算量 O(logN) であること と書かれているだけです。
|
|
8
|
+
実際のところほとんどすべて二分木(赤黒木)で実装されてるんですけどね。
|
1
追記
answer
CHANGED
|
@@ -1,3 +1,5 @@
|
|
|
1
1
|
> setの構造が二分木ならS.begin()が根で、その次が根の左の子、その次が根の右の子。というふうにならないのでしょうか？
|
|
2
2
|
|
|
3
|
-
(根からじゃなく)左端の末っ子を起点に辿れば小さい順になります。
|
|
3
|
+
(根からじゃなく)左端の末っ子を起点に辿れば小さい順になります。
|
|
4
|
+
|
|
5
|
+
※ "set::begin() が二分木の根を指す" なんて、標準C++規格にはどこにも書かれていません。
|