Prove that the height of a 2-3 tree is between log_3 N and lg N

Gauge Odom

Gauge Odom

Answered question

2022-09-07

Prove that the height of a 2-3 tree is between log 3 N and lg N

Answer & Explanation

letovanjelm

letovanjelm

Beginner2022-09-08Added 13 answers

Step 1
A tree of height h has at least
1 + 2 + + 2 h = 2 h + 1 1
nodes and at most
1 + 3 + + 3 h = ( 3 h + 1 1 ) / 2
nodes, i.e.
2 h + 1 1 N 3 h + 1 1 2 .

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?