７−３．高度な木 （平衡木）

内容

1. スライド　1 ７−３．高度な木（平衡木）
2. スライド　2 ２分探索木の問題点
3. スライド　3 平衡木とは
4. スライド　4 平衡木のイメージ
5. スライド　5 ＡＶＬ木
6. スライド　6 様々なＡＶＬ木
7. スライド　7 ＡＶＬ木でない例
8. スライド　8 ＡＶＬ木の高さの導出
9. スライド　9 少ないノードのＡＶＬ木１
10. スライド　10 少ないノードのＡＶＬ木２
11. スライド　11 高さ　　　　のＡＶＬ木を実現する最小のノード数を 　　　　　　と表す。
12. スライド　12 高さ　　　を実現する最小ノード数のＡＶＬ木
13. スライド　13 以上の考察より、次の漸化式が成り立つ。
14. スライド　14 この同次解を求める。 すなわち、以下の漸化式を満たす解を求める。
15. スライド　15 これを解いて、
16. スライド　16 これより、
17. スライド　17 ＡＶＬへの挿入
18. スライド　18 バランスを崩す挿入
19. スライド　19 １重回転
20. スライド　20 ２重回転１
21. スライド　21 ２重回転２
22. スライド　22 １重回転２回での２重回転の実現
23. スライド　23 ＡＶＬ木への挿入例１
24. スライド　24 バランスが崩れる
25. スライド　25 １５
26. スライド　26 ＡＶＬ木への挿入例２
27. スライド　27 バランスが崩れる
28. スライド　28 バランスが崩れる
29. スライド　29 練習
30. スライド　30 ＡＶＬへの挿入の計算量
31. スライド　31 ＡＶＬへの削除の計算量
32. スライド　32 Ｂ木の概略
33. スライド　33 Ｂ木の満たすべき条件
34. スライド　34 Ｂ木の例
35. スライド　35 Ｂ木の高さ
36. スライド　36 Ｂ木への挿入
37. スライド　37 オーバーフロー時のノード分割１
38. スライド　38 オーバーフロー時のノード分割２
39. スライド　39 Ｂ木からの削除
40. スライド　40 アンダーフローにおけるデータの再配置
41. スライド　41 Ｂ木の最悪計算量
42. スライド　42 Ｂ木の応用
43. スライド　43 平衡木のまとめ