Определить, имеет ли поддерево красно-черного дерева не более 3n / 4 узлов?

Question

У меня есть красно-черное дерево с n узлами, с корнем в x.Как я могу доказать или опровергнуть, что число узлов в левом поддереве x (включая корень x.left) составляет максимум 3n / 4 без учета?

Answer 1

Вы можете просто построить контрпример с как можно большим количеством красных узлов слева и без красных узлов справа.

Если справа - полное черное дерево с 2 ^Узлы h-1, а левый может быть полным деревом с 2 ^ (2h) -1 узлами.

Когда h> = 3, левая сторона имеет более 3n / 4 узлов.