98
правок
Изменения
→Высота красно-черного дерева
Если обычная высота дерева равна <tex>h</tex>, то черная высота дерева будет не меньше <tex>h/2-1</tex> и, по лемме, количество внутренних вершин в дереве
<tex>N >= \ge 2^{h/2}-1</tex>
Прологарифмировав неравенство, имеем:
<tex>\log(N+1) >= \ge h/2</tex>
<tex>2\log(N+1) >= \ge h</tex>
<tex>h <= \le 2\log(N+1)</tex>
Итак, учитывая, что для любого бинарного дерева <tex>h > \log(N)</tex>, получаем, что доказана следующая
'''Теорема'''. Для красно-черного дерева, имеющего <tex>N</tex> внутренних вершин, верна следующая оценка для его высоты <tex>h=O(\log(N))</tex>, или, более точно, <tex>\log(N) < h <= \le 2\log(N+1)</tex>.
== Операции ==
