Inflearn Community Q&A
asked
red-black tree에 대한 질문입니다.
Written on
·
338
1
영상의 26분 42초 쯤에
2(2^(bh(x)-1)-1)+1의 식에서
왜 마지막에 +1을 해주어야 하는지 모르겠습니다 ㅠ
algorithm
Answer 1
3
내부 노드의 개수를 구하는 식인데 노드 x도 포함해야 되니까 + 1한 거에요!
2(2^(bh(x)-1)-1)만 하면 좌우 서브트리에 있는 내부노드만 포함하니까 노드 x를 따로 +1 해준거죠 ㅎㅎ