Я читаю стр. 309 CLRS, и меня смущает определение black-height
RBT.
Определение в этой книге:
количество черногоузлы на любом простом пути от, но не включая, узла x до листа
Я также упоминал википедию, black-height
определяется как
униформаколичество черных узлов на всех путях от корня до листьев
и geeksforgeeks.org
Черная высота - количество черных узлов на пути от узла к листу,Листовые узлы также считаются черными узлами.
Но ни один из них не дает примеров, особенно без краевых случаев.
Можете ли вы объяснить это следующими случаями?
Что такое black-height
RBT:
- ноль
- B- (ноль ноль)
B-R-B-(nil nil)
\ \
\ B-(nil nil)
B-(nil nil)
По определению CLRS, я вычисляю black-height
корня:
- 0
- 1
- 2
(Вмое мнение, я прав?)
И в доказательстве леммы 13.1 CLRS также используется height
.Что такое height
из этих трех деревьев?
- 0
- 1
- 2
(На мой взгляд, я прав?)
Ичто такое black-height
дерева?
- 1
- 2
- 3
(не уверен, я сомневаюсь, что определение в Википедии отличается от определения из CLRS)
А также, Упражнение 13.1-1 использует это определение.