MESSAGE
| DATE | 2016-11-21 |
| FROM | ruben safir
|
| SUBJECT | Subject: [Learn] Fwd: creating a binary tree
|
From learn-bounces-at-nylxs.com Mon Nov 21 15:58:53 2016
Return-Path:
X-Original-To: archive-at-mrbrklyn.com
Delivered-To: archive-at-mrbrklyn.com
Received: from www.mrbrklyn.com (www.mrbrklyn.com [96.57.23.82])
by mrbrklyn.com (Postfix) with ESMTP id DD294161314;
Mon, 21 Nov 2016 15:58:52 -0500 (EST)
X-Original-To: learn-at-nylxs.com
Delivered-To: learn-at-nylxs.com
Received: from [10.0.0.62] (flatbush.mrbrklyn.com [10.0.0.62])
by mrbrklyn.com (Postfix) with ESMTP id D5128161312
for ; Mon, 21 Nov 2016 15:58:49 -0500 (EST)
References:
To: learn-at-nylxs.com
From: ruben safir
X-Forwarded-Message-Id:
Message-ID:
Date: Mon, 21 Nov 2016 15:58:49 -0500
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101
Thunderbird/45.4.0
MIME-Version: 1.0
In-Reply-To:
Content-Type: multipart/mixed; boundary="------------0EEE9678FD2A256C17159BE0"
Subject: [Learn] Fwd: creating a binary tree
X-BeenThere: learn-at-nylxs.com
X-Mailman-Version: 2.1.17
Precedence: list
List-Id:
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
Errors-To: learn-bounces-at-nylxs.com
Sender: "Learn"
This is a multi-part message in MIME format.
--------------0EEE9678FD2A256C17159BE0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit
more C++ work
--------------0EEE9678FD2A256C17159BE0
Content-Type: message/rfc822;
name="creating a binary tree.eml"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="creating a binary tree.eml"
Path: reader2.panix.com!panix!not-for-mail
From: Popping mad
Newsgroups: comp.lang.c++
Subject: creating a binary tree
Date: Sun, 20 Nov 2016 07:24:20 +0000 (UTC)
Organization: PANIX Public Access Internet and UNIX, NYC
Message-ID:
NNTP-Posting-Host: www.mrbrklyn.com
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
X-Trace: reader2.panix.com 1479626660 578 96.57.23.82 (20 Nov 2016 07:24:20 GMT)
X-Complaints-To: abuse-at-panix.com
NNTP-Posting-Date: Sun, 20 Nov 2016 07:24:20 +0000 (UTC)
User-Agent: Pan/0.140 (Chocolate Salty Balls; GIT b8fc14e
git.gnome.org/git/pan2)
Xref: panix comp.lang.c++:1125357
I know someone must have solved this problem at some point.
Lets say I have an array with 500 randon ints between 0-9999
I want to build a binary tree from the data in the array. Each node has
pointers to children nodes, a value and a point to a parent node, just
incase you want to look up.
How can you build this? A recursive function goes straight down the left
side.
--------------0EEE9678FD2A256C17159BE0
Content-Type: message/rfc822;
name="Re: creating a binary tree.eml"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="Re: creating a binary tree.eml"
Path: reader2.panix.com!panix!goblin2!goblin1!goblin.stu.neva.ru!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: "Alf P. Steinbach"
Newsgroups: comp.lang.c++
Subject: Re: creating a binary tree
Date: Sun, 20 Nov 2016 12:13:10 +0100
Organization: A noiseless patient Spider
Message-ID:
References:
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Sun, 20 Nov 2016 11:15:16 -0000 (UTC)
Injection-Info: mx02.eternal-september.org; posting-host="94133b64b90e83eb39a5882b4e50377c";
logging-data="32624"; mail-complaints-to="abuse-at-eternal-september.org"; posting-account="U2FsdGVkX19cdCdDwtC2ngh/LG7GjGWx"
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:45.0) Gecko/20100101
Thunderbird/45.5.0
In-Reply-To:
Cancel-Lock: sha1:6FOuu0WLOUKrXx6Jhf1MicWk9UM=
Xref: panix comp.lang.c++:1125362
On 20.11.2016 08:24, Popping mad wrote:
> I know someone must have solved this problem at some point.
>
> Lets say I have an array with 500 randon ints between 0-9999
>
> I want to build a binary tree from the data in the array. Each node has
> pointers to children nodes, a value and a point to a parent node, just
> incase you want to look up.
>
> How can you build this? A recursive function goes straight down the left
> side.
Well that's the degenerate case of sorted input. But you say it's random.
I'd build the tree first and worry about balancing it after.
Cheers!,
- Alf
--------------0EEE9678FD2A256C17159BE0
Content-Type: message/rfc822;
name="Re: creating a binary tree.eml"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="Re: creating a binary tree.eml"
Path: reader2.panix.com!panix!goblin3!goblin.stu.neva.ru!news-1.dfn.de!news.dfn.de!news.informatik.hu-berlin.de!fu-berlin.de!uni-berlin.de!not-for-mail
From: ram-at-zedat.fu-berlin.de (Stefan Ram)
Newsgroups: comp.lang.c++
Subject: Re: creating a binary tree
Date: 20 Nov 2016 11:23:59 GMT
Organization: Stefan Ram
Expires: 1 Jan 2017 11:59:58 GMT
Message-ID:
References:
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
X-Trace: news.uni-berlin.de gicwlPwbzbxXScSEusCjTwMK8uigRk1NSe0ebmiNSbhhiF
X-Copyright: (C) Copyright 2016 Stefan Ram. All rights reserved.
Distribution through any means other than regular usenet
channels is forbidden. It is forbidden to publish this
article in the world wide web. It is forbidden to change
URIs of this article into links. It is forbidden to remove
this notice or to transfer the body without this notice.
X-No-Archive: Yes
Archive: no
X-No-Archive-Readme: "X-No-Archive" is only set, because this prevents some
services to mirror the article via the web (HTTP). But Stefan Ram
hereby allows to keep this article within a Usenet archive server
with only NNTP access without any time limitation.
X-No-Html: yes
Content-Language: en
Xref: panix comp.lang.c++:1125363
"Alf P. Steinbach" writes:
>On 20.11.2016 08:24, Popping mad wrote:
>>I know someone must have solved this problem at some point.
>>Lets say I have an array with 500 randon ints between 0-9999
>>I want to build a binary tree from the data in the array. Each node has
>>pointers to children nodes, a value and a point to a parent node, just
>>incase you want to look up.
>>How can you build this? A recursive function goes straight down the left
>>side.
>Well that's the degenerate case of sorted input. But you say it's random.
>I'd build the tree first and worry about balancing it after.
I cannot find a requirement in the OP that say that the
binary tree needs to be balanced.
Implementing functionality that is not required might have
disadvantages:
- might increase the project duration
- might increase the product costs
- might offer more surface for bugs and attacks
- the additional work might be multiplied when
documentation, tests and reviews are to be done
for the added functionality
--------------0EEE9678FD2A256C17159BE0
Content-Type: message/rfc822;
name="Re: creating a binary tree.eml"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="Re: creating a binary tree.eml"
Path: reader2.panix.com!panix!goblin3!goblin1!goblin.stu.neva.ru!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: "Alf P. Steinbach"
Newsgroups: comp.lang.c++
Subject: Re: creating a binary tree
Date: Sun, 20 Nov 2016 14:14:07 +0100
Organization: A noiseless patient Spider
Message-ID:
References:
Mime-Version: 1.0
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Sun, 20 Nov 2016 13:16:13 -0000 (UTC)
Injection-Info: mx02.eternal-september.org; posting-host="94133b64b90e83eb39a5882b4e50377c";
logging-data="24003"; mail-complaints-to="abuse-at-eternal-september.org"; posting-account="U2FsdGVkX19hgQ8TmQFHM72Wa6DwUa+S"
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:45.0) Gecko/20100101
Thunderbird/45.5.0
In-Reply-To:
Cancel-Lock: sha1:7813Nq/LXNM1G7A7nJvY5nsRF7o=
Xref: panix comp.lang.c++:1125367
On 20.11.2016 12:23, Stefan Ram wrote:
> "Alf P. Steinbach" writes:
>> On 20.11.2016 08:24, Popping mad wrote:
>>> I know someone must have solved this problem at some point.
>>> Lets say I have an array with 500 randon ints between 0-9999
>>> I want to build a binary tree from the data in the array. Each node has
>>> pointers to children nodes, a value and a point to a parent node, just
>>> incase you want to look up.
>>> How can you build this? A recursive function goes straight down the left
>>> side.
>> Well that's the degenerate case of sorted input. But you say it's random.
>> I'd build the tree first and worry about balancing it after.
>
> I cannot find a requirement in the OP that say that the
> binary tree needs to be balanced.
>
> Implementing functionality that is not required might have
> disadvantages:
>
> - might increase the project duration
> - might increase the product costs
> - might offer more surface for bugs and attacks
> - the additional work might be multiplied when
> documentation, tests and reviews are to be done
> for the added functionality
>
Are you for real?
Cheers!,
- Alf
--------------0EEE9678FD2A256C17159BE0
Content-Type: message/rfc822;
name="Re: creating a binary tree.eml"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="Re: creating a binary tree.eml"
Path: reader2.panix.com!panix!not-for-mail
From: ruben safir
Newsgroups: comp.lang.c++
Subject: Re: creating a binary tree
Date: Sun, 20 Nov 2016 09:16:56 -0500
Organization: PANIX Public Access Internet and UNIX, NYC
Message-ID:
References:
NNTP-Posting-Host: www.mrbrklyn.com
Mime-Version: 1.0
Content-Type: text/plain; charset=windows-1252
Content-Transfer-Encoding: 7bit
X-Trace: reader2.panix.com 1479651416 7284 96.57.23.82 (20 Nov 2016 14:16:56 GMT)
X-Complaints-To: abuse-at-panix.com
NNTP-Posting-Date: Sun, 20 Nov 2016 14:16:56 +0000 (UTC)
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101
Thunderbird/45.4.0
In-Reply-To:
Xref: panix comp.lang.c++:1125369
On 11/20/2016 05:13 AM, Stefan Ram wrote:
> for_each( array.begin(), array.end(), insert_into_tree );
/dev/null - bye
--------------0EEE9678FD2A256C17159BE0
Content-Type: message/rfc822;
name="Re: creating a binary tree.eml"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="Re: creating a binary tree.eml"
Path: reader2.panix.com!panix!bloom-beacon.mit.edu!bloom-beacon.mit.edu!168.235.88.217.MISMATCH!2.us.feeder.erje.net!feeder.erje.net!1.eu.feeder.erje.net!news2.arglkargh.de!newsfeed.fsmpi.rwth-aachen.de!newsfeed.straub-nv.de!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!jstuckle.eternal-september.org!.POSTED!not-for-mail
From: Jerry Stuckle
Newsgroups: comp.lang.c++
Subject: Re: creating a binary tree
Date: Sun, 20 Nov 2016 17:47:27 -0500
Organization: A noiseless patient Spider
Message-ID:
References:
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit
Injection-Date: Sun, 20 Nov 2016 22:46:46 -0000 (UTC)
Injection-Info: jstuckle.eternal-september.org; posting-host="41ec4db4d8d7892f0646595b26a5fa28";
logging-data="3028"; mail-complaints-to="abuse-at-eternal-september.org"; posting-account="U2FsdGVkX1/qGxwbIzXJvdlgUAfTim/RuxcTtMxcYBo="
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:45.0) Gecko/20100101
Thunderbird/45.4.0
In-Reply-To:
Cancel-Lock: sha1:kJx3YnfrPg4UUifJR3XOpqwLmjg=
Xref: panix comp.lang.c++:1125384
On 11/20/2016 2:24 AM, Popping mad wrote:
> I know someone must have solved this problem at some point.
>
> Lets say I have an array with 500 randon ints between 0-9999
>
> I want to build a binary tree from the data in the array. Each node has
> pointers to children nodes, a value and a point to a parent node, just
> incase you want to look up.
>
> How can you build this? A recursive function goes straight down the left
> side.
>
https://www.tutorialspoint.com/data_structures_algorithms/avl_tree_algorithm.htm
has a good example of algorithms It's not too hard to balance one once
you understand the rotations. And the overhead of maintaining balance
is pretty low.
I did it in C, but that's been probably 25 years ago and I don't have
that code any more. But the code wasn't that big.
--
==================
Remove the "x" from my email address
Jerry Stuckle
jstucklex-at-attglobal.net
==================
--------------0EEE9678FD2A256C17159BE0
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
_______________________________________________
Learn mailing list
Learn-at-nylxs.com
http://lists.mrbrklyn.com/mailman/listinfo/learn
--------------0EEE9678FD2A256C17159BE0--
|
|
