Open Fantasy-Rain opened 4 years ago
Those nil's are considered as nodes when calculation, but not included in data_nodes(T)=n.
So given a red-black tree T with n data nodes, the two highlighted parts should be: log(n+1)+1, log(n+1).
Then height(T)= ((log(n+1)+1)+log(n+1)) - 1= 2log(n+1). (when calculating height, nil's are included; both CLRS, GeeksForGeeks gives the same result.)
This error has to be fixed immediately.
I'm on it!
LautaroLobo12
commented
4 years ago LautaroLobo12
commented
4 years ago
Those nil's are considered as nodes when calculation, but not included in data_nodes(T)=n.
So given a red-black tree T with n data nodes, the two highlighted parts should be: log(n+1)+1, log(n+1).
Then height(T)= ((log(n+1)+1)+log(n+1)) - 1= 2log(n+1). (when calculating height, nil's are included; both CLRS, GeeksForGeeks gives the same result.)
This error has to be fixed immediately.