Thu Dec 12 13:27:34 2024
EVENTS
 FREE
SOFTWARE
INSTITUTE

POLITICS
JOBS
MEMBERS'
CORNER

MAILING
LIST

NYLXS Mailing Lists and Archives
NYLXS Members have a lot to say and share but we don't keep many secrets. Join the Hangout Mailing List and say your peice.

DATE 2015-05-01

LEARN

2024-12-12 | 2024-11-12 | 2024-10-12 | 2024-09-12 | 2024-08-12 | 2024-07-12 | 2024-06-12 | 2024-05-12 | 2024-04-12 | 2024-03-12 | 2024-02-12 | 2024-01-12 | 2023-12-12 | 2023-11-12 | 2023-10-12 | 2023-09-12 | 2023-08-12 | 2023-07-12 | 2023-06-12 | 2023-05-12 | 2023-04-12 | 2023-03-12 | 2023-02-12 | 2023-01-12 | 2022-12-12 | 2022-11-12 | 2022-10-12 | 2022-09-12 | 2022-08-12 | 2022-07-12 | 2022-06-12 | 2022-05-12 | 2022-04-12 | 2022-03-12 | 2022-02-12 | 2022-01-12 | 2021-12-12 | 2021-11-12 | 2021-10-12 | 2021-09-12 | 2021-08-12 | 2021-07-12 | 2021-06-12 | 2021-05-12 | 2021-04-12 | 2021-03-12 | 2021-02-12 | 2021-01-12 | 2020-12-12 | 2020-11-12 | 2020-10-12 | 2020-09-12 | 2020-08-12 | 2020-07-12 | 2020-06-12 | 2020-05-12 | 2020-04-12 | 2020-03-12 | 2020-02-12 | 2020-01-12 | 2019-12-12 | 2019-11-12 | 2019-10-12 | 2019-09-12 | 2019-08-12 | 2019-07-12 | 2019-06-12 | 2019-05-12 | 2019-04-12 | 2019-03-12 | 2019-02-12 | 2019-01-12 | 2018-12-12 | 2018-11-12 | 2018-10-12 | 2018-09-12 | 2018-08-12 | 2018-07-12 | 2018-06-12 | 2018-05-12 | 2018-04-12 | 2018-03-12 | 2018-02-12 | 2018-01-12 | 2017-12-12 | 2017-11-12 | 2017-10-12 | 2017-09-12 | 2017-08-12 | 2017-07-12 | 2017-06-12 | 2017-05-12 | 2017-04-12 | 2017-03-12 | 2017-02-12 | 2017-01-12 | 2016-12-12 | 2016-11-12 | 2016-10-12 | 2016-09-12 | 2016-08-12 | 2016-07-12 | 2016-06-12 | 2016-05-12 | 2016-04-12 | 2016-03-12 | 2016-02-12 | 2016-01-12 | 2015-12-12 | 2015-11-12 | 2015-10-12 | 2015-09-12 | 2015-08-12 | 2015-07-12 | 2015-06-12 | 2015-05-12 | 2015-04-12 | 2015-03-12 | 2015-02-12 | 2015-01-12 | 2014-12-12 | 2014-11-12 | 2014-10-12

Key: Value:

Key: Value:

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


??



  1. 2015-05-02 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] debuging methods
  2. 2015-05-02 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Excellent article on Virtual Paging and OS memory
  3. 2015-05-02 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Great Article on Software Concordance program writing
  4. 2015-05-02 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Semephores and what the heck are those things?
  5. 2015-05-03 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Go Language tutorials
  6. 2015-05-04 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] ACL and beyound security in linux
  7. 2015-05-04 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Fwd: [Perlweekly] #197 - YAPC::EU Master classes - talks - hackathons
  8. 2015-05-05 Ruben <ruben.safir-at-my.liu.edu> Re: [LIU Comp Sci] Fibonacci trees
  9. 2015-05-05 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Examination Question for Allogorthims
  10. 2015-05-05 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Fibonacci trees
  11. 2015-05-05 Ruben <ruben.safir-at-my.liu.edu> Subject: [LIU Comp Sci] Fwd: Internships with Oracle, Amtrak, The Nature Conservancy & more
  12. 2015-05-05 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Nice possible project for NYLXS or others
  13. 2015-05-06 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] Fibonacci trees
  14. 2015-05-06 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] Fibonacci trees
  15. 2015-05-06 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] Fibonacci trees
  16. 2015-05-06 Ruben <ruben.safir-at-my.liu.edu> Subject: [LIU Comp Sci] Fwd: Re: [opensuse] Re: no space left on the device
  17. 2015-05-06 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] hashing multiplication
  18. 2015-05-08 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Fwd: Kernel Scheduling and wait queues
  19. 2015-05-08 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Fwd: Re: Kernel Scheduler and wiat queues
  20. 2015-05-08 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Re: [NYLXS - HANGOUT] Things to study over the summer
  21. 2015-05-08 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Things to study over the summer
  22. 2015-05-10 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] scheduler Slides
  23. 2015-05-10 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] scheduler Slides
  24. 2015-05-11 Ruben Safir <ruben.safir-at-my.liu.edu> Re: [LIU Comp Sci] scheduler Slides
  25. 2015-05-11 Ruben Safir <ruben.safir-at-my.liu.edu> Re: [LIU Comp Sci] scheduler Slides
  26. 2015-05-11 Justin Lau <justinml-at-gmail.com> Re: [LIU Comp Sci] scheduler Slides
  27. 2015-05-11 Justin Lau <justinml-at-gmail.com> Re: [LIU Comp Sci] scheduler Slides
  28. 2015-05-11 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] scheduler Slides
  29. 2015-05-11 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] scheduler Slides
  30. 2015-05-11 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] scheduler Slides
  31. 2015-05-12 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Job sound like this evenings lectures
  32. 2015-05-12 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] jobs
  33. 2015-05-12 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] LAMP Jobs
  34. 2015-05-13 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] April Journal is Available
  35. 2015-05-13 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Fwd: Tomorrow: You and 256 others are going to "Btrfs"
  36. 2015-05-13 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Malloc systemtap probes: an example
  37. 2015-05-13 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Stackiq - Educational Program
  38. 2015-05-13 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Student Lab and Club House
  39. 2015-05-13 mrbrklyn-at-panix.com Subject: [LIU Comp Sci] [member-at-linkedin.com: RE: April Journal is Available]
  40. 2015-05-13 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] [mrbrklyn-at-panix.com: Re: [NYLXS - HANGOUT] Things to study over the
  41. 2015-05-14 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Weekly Education Meeting
  42. 2015-05-18 mrbrklyn-at-panix.com Subject: [LIU Comp Sci] [jkeen-at-verizon.net: ny.pm Technical Meeting Wed May 20 6:15 pm]
  43. 2015-05-25 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Summer NYLXS Study Schedule
  44. 2015-05-28 Tony Genao <tony.genao-at-my.liu.edu> Re: [LIU Comp Sci] Summer NYLXS Study Schedule
  45. 2015-05-28 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] Summer NYLXS Study Schedule
  46. 2015-05-28 Tony Genao <tony.genao-at-my.liu.edu> Re: [LIU Comp Sci] Summer NYLXS Study Schedule
  47. 2015-05-28 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] Summer NYLXS Study Schedule
  48. 2015-05-28 Ruben <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Fwd: Re: Programming Position
  49. 2015-05-28 mrbrklyn-at-panix.com Subject: [LIU Comp Sci] [ruben-at-www.mrbrklyn.com: Linux 1 Book]
  50. 2015-05-31 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] Summer NYLXS Study Schedule

NYLXS are Do'ers and the first step of Doing is Joining! Join NYLXS and make a difference in your community today!