red-black tree에 대한 질문입니다.

21.01.31 10:35 작성 조회수 160

영상의 26분 42초 쯤에

2(2^(bh(x)-1)-1)+1의 식에서

왜 마지막에 +1을 해주어야 하는지 모르겠습니다 ㅠ

영리한 프로그래밍을 위한 알고리즘 강좌

red black tree - 1

강의실 바로가기

답변 1

답변을 작성해보세요.

오종화

2021.02.06

내부 노드의 개수를 구하는 식인데 노드 x도 포함해야 되니까 + 1한 거에요!

2(2^(bh(x)-1)-1)만 하면 좌우 서브트리에 있는 내부노드만 포함하니까 노드 x를 따로 +1 해준거죠 ㅎㅎ