Красное-чёрное дерево — различия между версиями

Материал из Public ATP Wiki
Перейти к: навигация, поиск
(Чёрная высота)
Строка 11: Строка 11:
  
 
'''Чёрная высота вершины $x$''' (Обозначаем $bh(x)$) - количество чёрных вершин на пути от $x$ до любого её потомка-листа, не считая самого $x$.
 
'''Чёрная высота вершины $x$''' (Обозначаем $bh(x)$) - количество чёрных вершин на пути от $x$ до любого её потомка-листа, не считая самого $x$.
 +
 +
{{Template:Lemma
 +
|What = Лемма
 +
|Statement = В поддереве вершины $x$ как минимум $2^{bh(x)} - 1$ вершин.
 +
|Proof =
 +
Пусть $c(x)$ - количество вершин в поддереве x.
 +
 +
Индукция по $h(x)$:
 +
* База: $h(x) = 0$ - очевидное отверждение
 +
* Переход: <br/> К потомкам $x$ - $y$ и $z$ применимо предположение индукции. <br/> Заметим также, что $bh(y) \geq bh(x) - 1$ и $bh(z) \geq bh(x) - 1$. <br/> Тогда $c(x) \geq 1 + 2^{bh(y)} - 1 + 2^{bh(z)} - 1 \geq 2^{bh(x) - 1} + 2^{bh(x) - 1} - 1 \eq 2^{bh(x)} - 1$
 +
}}

Версия 23:26, 12 марта 2020

Красно-чёрное дерево(англ. red-black tree) - самобалансирующееся бинарное дерево поиска (англ. Binary Search Tree, BST) со следующими свойствами:

  • Каждая вершина имеет цвет: красный или чёрный
  • Корень дерева - чёрный
  • У каждой нелистовой вершины ровно два ребёнка
  • Все листья чёрные и фиктивные
  • У красной вершины оба ребёнка чёрные
  • Чёрная высота каждой вершины определена корректно

Чёрная высота

На пути от любой вершины красно-чёрного дерева до её потомка-листа одинаковое количество чёрных вершин.

Чёрная высота вершины $x$ (Обозначаем $bh(x)$) - количество чёрных вершин на пути от $x$ до любого её потомка-листа, не считая самого $x$.

Лемма
В поддереве вершины $x$ как минимум $2^{bh(x)} - 1$ вершин.
Доказательство

Пусть $c(x)$ - количество вершин в поддереве x.

Индукция по $h(x)$:

  • База: $h(x) = 0$ - очевидное отверждение
  • Переход:
    К потомкам $x$ - $y$ и $z$ применимо предположение индукции.
    Заметим также, что $bh(y) \geq bh(x) - 1$ и $bh(z) \geq bh(x) - 1$.
    Тогда $c(x) \geq 1 + 2^{bh(y)} - 1 + 2^{bh(z)} - 1 \geq 2^{bh(x) - 1} + 2^{bh(x) - 1} - 1 \eq 2^{bh(x)} - 1$