Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
0
Help us understand the problem. What is going on with this article?
@kamikennn

完全二分木の根の高さがO(logn)となる理由

More than 1 year has passed since last update.

完全二分木

完全二分木は根付き木の一つで,各頂点の子は多くても2個であるような木のことです.また,頂点は常に左に詰めて配置されています.ヒープ木も完全二分木の一つで,根の要素が最小値であるような木のことです.根から一番遠い子孫までの路の長さを根の高さと言います.下図の例では根の高さは3となります.Screen Shot 2020-02-19 at 10.40.17.png

高さのオーダーは?

完全二分木は,根の高さによってその木の要素の最大数は決まっています.例えば,根の高さが3なら最大でも15個です.では,要素の数をnとすると根の高さはどうなるのか?各深さにおける最大の要素数は深さをdとすると,2^d個となります.つまり,根の高さがhの木の場合,最大の要素数は(2^0+2^1+...2^h)個になります.
ここで,
2^0 + 2^1 + ... 2^n = 2^(n+1) - 1
のように最大の要素数を表すことができます.根の高さがhの木の最大の要素数は2^(h+1) - 1個となります.
また,根の高さがh-1の木の最大の要素数は2^(h) - 1個となります
よってn個の要素を含む完全二分木の値の高さは,
2^h - 1 < 2^h <= n < 2^(h+1) - 1 < 2^(h+1)
⇨ 2^h <= n < 2^(h+1)
⇨ h = O(logn)
完全二分木の根の高さはO(logn)であることがわかりました.

0
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
kamikennn
majoring in computer science

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
0
Help us understand the problem. What is going on with this article?