MESSAGE
| DATE | 2015-05-05 |
| FROM | Ruben Safir
|
| SUBJECT | Subject: [LIU Comp Sci] Fibonacci trees
|
From owner-learn-outgoing-at-mrbrklyn.com Tue May 5 23:18:58 2015
Return-Path:
X-Original-To: archive-at-mrbrklyn.com
Delivered-To: archive-at-mrbrklyn.com
Received: by mrbrklyn.com (Postfix)
id C147D1612E1; Tue, 5 May 2015 23:18:58 -0400 (EDT)
Delivered-To: learn-outgoing-at-mrbrklyn.com
Received: by mrbrklyn.com (Postfix, from userid 28)
id AF1FE1612ED; Tue, 5 May 2015 23:18:58 -0400 (EDT)
Delivered-To: learn-at-nylxs.com
Received: from mailbackend.panix.com (mailbackend.panix.com [166.84.1.89])
by mrbrklyn.com (Postfix) with ESMTP id AAF891612E1
for ; Tue, 5 May 2015 23:18:33 -0400 (EDT)
Received: from [10.0.0.19] (www.mrbrklyn.com [96.57.23.82])
by mailbackend.panix.com (Postfix) with ESMTPSA id 6EE47127FF;
Tue, 5 May 2015 23:18:32 -0400 (EDT)
Message-ID: <55498808.7030608-at-panix.com>
Date: Tue, 05 May 2015 23:18:32 -0400
From: Ruben Safir
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"
CC: learn-at-nylxs.com
Subject: [LIU Comp Sci] Fibonacci trees
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
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
??
|
|
