Определение высоты черного в красно-черном дереве - PullRequest
0 голосов
/ 12 сентября 2018

Я читаю стр. 309 CLRS, и меня смущает определение black-height RBT.

Определение в этой книге:

количество черногоузлы на любом простом пути от, но не включая, узла x до листа

Я также упоминал википедию, black-height определяется как

униформаколичество черных узлов на всех путях от корня до листьев

и geeksforgeeks.org

Черная высота - количество черных узлов на пути от узла к листу,Листовые узлы также считаются черными узлами.

Но ни один из них не дает примеров, особенно без краевых случаев.

Можете ли вы объяснить это следующими случаями?

Что такое black-height RBT:

  1. ноль
  2. B- (ноль ноль)
  3. B-R-B-(nil nil)
     \ \
      \ B-(nil nil)
       B-(nil nil)
    

По определению CLRS, я вычисляю black-height корня:

  1. 0
  2. 1
  3. 2

(Вмое мнение, я прав?)

И в доказательстве леммы 13.1 CLRS также используется height.Что такое height из этих трех деревьев?

  1. 0
  2. 1
  3. 2

(На мой взгляд, я прав?)

Ичто такое black-height дерева?

  1. 1
  2. 2
  3. 3

(не уверен, я сомневаюсь, что определение в Википедии отличается от определения из CLRS)

А также, Упражнение 13.1-1 использует это определение.

...