MESSAGE
| DATE | 2015-05-05 |
| FROM | Ruben
|
| SUBJECT | Re: [LIU Comp Sci] Fibonacci trees
|
From owner-learn-outgoing-at-mrbrklyn.com Tue May 5 23:37:43 2015
Return-Path:
X-Original-To: archive-at-mrbrklyn.com
Delivered-To: archive-at-mrbrklyn.com
Received: by mrbrklyn.com (Postfix)
id 98ADF1612E1; Tue, 5 May 2015 23:37:43 -0400 (EDT)
Delivered-To: learn-outgoing-at-mrbrklyn.com
Received: by mrbrklyn.com (Postfix, from userid 28)
id 867831612ED; Tue, 5 May 2015 23:37:43 -0400 (EDT)
Delivered-To: learn-at-mrbrklyn.com
Received: from mail-qk0-f169.google.com (mail-qk0-f169.google.com [209.85.220.169])
by mrbrklyn.com (Postfix) with ESMTP id DDF401612E1
for ; Tue, 5 May 2015 23:37:19 -0400 (EDT)
Received: by qkgx75 with SMTP id x75so120501571qkg.1
for ; Tue, 05 May 2015 20:37:18 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20130820;
h=x-gm-message-state:message-id:date:from:user-agent:mime-version:to
:subject:references:in-reply-to:content-type
:content-transfer-encoding;
bh=CJPFqyko5CyXj47N+kRO1DZDfvSwtlwlBYu9srUeoXY=;
b=ZkDx00bahTV9wG7ktcnTw0IZwsPl0ZDordJ6eXCxLQ8hC2P+kicbA23OIxGvx9GMII
yBpK7kjvxVDNwPeVNvQLrvqpv1qjmv8eJxvseUeIxtN/wRmeF678l4HxGMYuYprUl/nY
8eYtdzWimiOaocnF9S7l0dTFILNmXqBCd1pyix1sJgNI50TOHg53BDfBH00MaxO4t5vK
u+7kEm4Jw2SHzV06HmwHJjpc8m9vI7qlMw1KEvSqg/BbaBsNYlGbTBn3gXlMP1VsHSrE
yQAmbbMAu7o3v9DTUEH1GhgiXkH1bF39gwqLdo3rk5hfn+qLivVcq1Nv95jJufSWchLs
Mu7g==
X-Gm-Message-State: ALoCoQnOB0rCoA4xF2SDIAz5NMn7XjIVOGe8EngImGboMPdOkR1XfW9qvNhNm/FeuRb8/PqOAwJF
X-Received: by 10.140.39.164 with SMTP id v33mr36766043qgv.80.1430883438203;
Tue, 05 May 2015 20:37:18 -0700 (PDT)
Received: from [10.0.0.19] (www.mrbrklyn.com. [96.57.23.82])
by mx.google.com with ESMTPSA id f9sm346571qhe.34.2015.05.05.20.37.17
(version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128);
Tue, 05 May 2015 20:37:17 -0700 (PDT)
Message-ID: <55498C6D.4070404-at-my.liu.edu>
Date: Tue, 05 May 2015 23:37:17 -0400
From: Ruben
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.6.0
MIME-Version: 1.0
To: "Jose A. Rodriguez"
Subject: Re: [LIU Comp Sci] Fibonacci trees
References: <55498808.7030608-at-panix.com>
In-Reply-To: <55498808.7030608-at-panix.com>
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Sender: owner-learn-at-mrbrklyn.com
Precedence: bulk
Reply-To: learn-at-mrbrklyn.com
I think the answer of this problem in the notes is wrong
You are given that
F0 = 1
F1 = 2
|Fh| = Fh-1 + Fh-2
F2 = F1 + F0 + 1
2 + 1 + 1 = 4
F3 = F2 + F1 + 1
4 + 2 + 1 = 7
F4 = F3 + F2 + 1
7 + 4 + 1= 12
F5 = F4 + F3 + 1
12 + 7 + 1 = 20
F6 = F5 + F4 + 1
20 + 12 + 1= 33
F7 = F5 + F3 + 1
33 + 20 + 1 = 54 <=====
In other words, I think you misnumbered them starting with 3 instead of two.
Or I don't understand something very important.
Ruben
On 05/05/2015 11:18 PM, Ruben Safir wrote:
> OK - so here is from the notes:
>
>
> The inequalitiy also holds for h = 0 and h = 1, so by induction it holds for
> all h ? 0. Therefore, given a height-balanced tree on n nodes having
> height h we
> have n ? |Fh | ? 2?h. Taking log we obtain ?h ? log(n) or h ? (1/?)
> log(n). We
> have (1/?) is about 1.44042009 . . . < 1.45. So we conclude that h ?
> 1.45 log(n),
> that is, a height-balance binary tree is at most 45% taller than its
> perfectly
> balanced counterpart on the same number of nodes. The height of an AVL tree
> will in practice be a lot less than what this upper bound indicates.
>
>
> I don't understand this part
>
> n ? |Fh | ? 2?h
>
>
> Fh is defined as the smallest number of nodes for balanced AVL tree
> so how can is be GREATER than 2?h
>
>
> ??
>
>
>
>
|
|
