[Tutor] How to create a binary tree hierarchy given a list of elements as its leaves
ThreeBlindQuarks
threesomequarks at proton.me
Mon Jan 29 18:17:57 EST 2024
Marc,
You have asked quite a few questions on this forum including some where I kept wondering WHY you want something. Speaking for myself, I like to be motivated to help someone and at a time when I can afford to volunteer.
Your code takes time and effort to copy and try as it is not written as intuitively or commented as well as you think. I won't start a project till I have time from an otherwise busy life, and besides, it does not look at all the way my instincts would design it and I said so.
I had hoped others would chime in ;-)
In my experience, the first step in debugging is to understand your own code well by commenting it properly.
So, what does this do:
def generate_numbers_list_until_number(stop_number):
if str(stop_number).isnumeric():
return np.arange(stop_number)
else:
raise TypeError('Input should be a number!')
I have to look further to see how it is invoked and perhaps guess the purpose. It may turn out to be irrelevant to finding out what is wrong. But the code is simple enough so it simply seems to be a way of making a sort of sequence while checking if the input for highest (minus one) number is actually numeric. No big deal but it already makes me wonder if your code has an off-by-one error as what should be returned is 0..stop_number as a numpy array
>>> generate_numbers_list_until_number(5)
array([0, 1, 2, 3, 4])
Your next function is a bit opaque without explanation:
def generate_node_label():
return random.choice(string.ascii_lowercase) \
+ str(random.randint(0, 10))
It takes no argument and generates two-part strings like s9 and w8. So far, purpose unknown but perhaps part of building a simulation.
They do get evaluated and run fine but the main() does not.
What version of python are you using? Any recent version does not have a print command but more of a print function. I replaced uour:
print cells_arrays
with
print (cells_arrays)
I made the same update for other print statements. Otherwise, the code has issues but can continue running as these seem to be debug statements.
Now what was the point of this line? Motivate us:
cells_arrays = np.array_split(data, data.size // k)
In your example, k is 100 and cells_arrays.size is not an array but a native python list also of length 100 containing what?
>>> print (cells_arrays)
[array([0]), array([1]), array([2]), array([3]), array([4]), array([5]), array([6]), array([7]), array([8]), array([9]), array([10]), array([11]), array([12]), array([13]), array([14]), array([15]), array([16]), array([17]), array([18]), array([19]), array([20]), array([21]), array([22]), array([23]), array([24]), array([25]), array([26]), array([27]), array([28]), array([29]), array([30]), array([31]), array([32]), array([33]), array([34]), array([35]), array([36]), array([37]), array([38]), array([39]), array([40]), array([41]), array([42]), array([43]), array([44]), array([45]), array([46]), array([47]), array([48]), array([49]), array([50]), array([51]), array([52]), array([53]), array([54]), array([55]), array([56]), array([57]), array([58]), array([59]), array([60]), array([61]), array([62]), array([63]), array([64]), array([65]), array([66]), array([67]), array([68]), array([69]), array([70]), array([71]), array([72]), array([73]), array([74]), array([75]), array([76]), array([77]), array([78]), array([79]), array([80]), array([81]), array([82]), array([83]), array([84]), array([85]), array([86]), array([87]), array([88]), array([89]), array([90]), array([91]), array([92]), array([93]), array([94]), array([95]), array([96]), array([97]), array([98]), array([99])]
I see it as a list of numpy singleton arrays containing the same info in 100 chunks rather than one array containing all 100. If that is what you want, I need to read on to see what purpose this has as an explanation of your algorithm in some human language would have been useful. I am quite flexible on the language. As a guess, you may want to make your binary tree by extending some of those arrays, perhaps several times at greater depth. I repeat, not my idea of an appropriate data structure.
A bit later, the following code fails for me with an error:
The next lines generate what may be too many strings unless you wanted names ending with eleven choices from a0 to a10.
Moving on, this two-line combo floors me.
while len(node_hierarchy_name) > 1:
k = k * 2
This is either an infinite loop or does nothing. The body of the loop never changes the variable so the length remains the same.
If all you want is to calculate a large number just calculate k^n where n is the size. I assume you meant to consume some items in the list, perhaps only in some cases would you do the doubling.
Until you submit code with the changes needed, I cannot follow your code further except on paper.
My bottom line remains that I do not see you providing enough to motivate help here. Yes, iot likely is possible to use numpy arrays embedded some way to arbitrary levels or other techniques but do not be shocked if doing what is in some sense a recursive process does not easily work this way.
Good Luck.
Sent with Proton Mail secure email.
On Monday, January 29th, 2024 at 2:30 AM, marc nicole <mk1853387 at gmail.com> wrote:
> great comments! but could you help debug the code I provided?
>
> Le lun. 29 janv. 2024 à 04:09, ThreeBlindQuarks threesomequarks at proton.me
>
> a écrit :
>
> > I too am not clear on exactly what is wanted and just want to say that you
> > need to come up first with which of the many ways you can construct a
> > binary tree of sorts in a way that makes the rest of what you want
> > straightforward or at least doable.
> >
> > Numpy does not come to mind as a way to do a binary tree. I am sure it can
> > be used in some way to get a result but my first thoughts include using
> > nested lists that contain no more than two items at each level. But that
> > can have some issues if you also want to store labels in some way so I
> > would suspect using a customized object, or some module that already
> > supplies what you want, as easier.
> >
> > If using objects, you might have an object that points to or contains two
> > similar objects with a name like left/right and when one is not is use,
> > puts in a stub like a null instead. You can have other contents to hold
> > names, or how many time sit has been visited, maybe pointers back up the
> > tree and so on and add the member functions needed to do additions or
> > deletions or searches or whatever makes sense, and some may best be written
> > in a sort of recursive way.
> >
> > Of course, if your other functionality wants results in another format,
> > such as a nested tuple implementation, you may want functions that take a
> > root pointing to the binary tree parts and traverse them while building the
> > tuple or list or vice versa. You need not use one fixed structure for every
> > kind of calculation if they are inter-convertible. It depends on your
> > needs, such as will you ever be asked to identify and return a sub-tree
> > rather than a leaf?
> >
> > If this is akin to homework, you may want to design your own version from
> > scratch. If not, this is a very common thing often used and often
> > traversed. You need to decide if it has to be very fast or just easier to
> > construct and use and so on.
> >
> > Note another of many possibilities could be using nested dictionaries with
> > each containing a left and a right. It may make sense to experiment with
> > which data structure you feel a bit more comfortable.
> >
> > And, as Alan pointed out, binary trees tend to not be at all balanced if
> > the data fed is is already in order. There are algorithms people use to
> > take a bad tree and rebalance it better so it can be accessed and
> > manipulated faster on average.
> >
> > Sent with Proton Mail secure email.
> >
> > On Sunday, January 28th, 2024 at 6:11 PM, marc nicole mk1853387 at gmail.com
> > wrote:
> >
> > > Here's the tree example I attached earlier which shows how to go from
> > > leaf
> > > nodes (0,1,2,3) to the root node (the range[0,3]) my problem (bug) in the
> > > code is that the generated intermediate intervals for the nodes don't fit
> > > each other because of the way I binary split the input array
> > >
> > > C1[0,3]
> > > ├── B1[0,1]
> > > │ ├── A0(0)
> > > │ └── A1(1)
> > > └── B2[2,3]
> > > ├── A2(2)
> > > └── A3(3)
> > >
> > > Le dim. 28 janv. 2024 à 20:12, Alan Gauld via Tutor tutor at python.org a
> > >
> > > écrit :
> > >
> > > > On 28/01/2024 18:16, marc nicole via Python-list wrote:
> > > >
> > > > > So I am trying to build a binary tree hierarchy given numerical
> > > > > elements
> > > > > serving for its leaves (last level of the tree to build). From the
> > > > > leaves I
> > > > > want to randomly create a name for the higher level of the hierarchy
> > > > > and
> > > > > assign it to the children elements. For example: if the elements
> > > > > inputted
> > > > > are `0,1,2,3` then I would like to create firstly 4 elements (say by
> > > > > random
> > > > > giving them a label composed of a letter and a number) then for the
> > > > > second
> > > > > level (iteration) I assign each of 0,1 to a random name label (e.g.
> > > > > `b1`)
> > > > > and `2,3` to another label (`b2`) then for the third level I assign a
> > > > > parent label to each of `b1` and `b2` as `c1`.
> > > > >
> > > > > An illustation of the example is the following tree:
> > > > >
> > > > > [image: tree_exp.PNG]
> > > >
> > > > Unfortunately the Python mail servers strip out binary
> > > > attachments so we can't see the example.
> > > >
> > > > Which is a pity because I don't really understand your
> > > > explanation, particularly about the random labelling
> > > > of parents.
> > > >
> > > > Also you are using an ordered set of inputs which is usually
> > > > a bad case for a binary tree - it turns into a linear list...
> > > >
> > > > However, I notice you've included several other mailing
> > > > lists so maybe someone else will comprehend your intention.
> > > >
> > > > Meanwhile, for a basic Python binary tree implementation
> > > > example you could try here:
> > > >
> > > > https://www.askpython.com/python/examples/binary-tree-implementation
> > > >
> > > > That may or may not help!
> > > >
> > > > I'm actually surprised it's not already in the standard
> > > > library somewhere, but I couldn't find one.
> > > >
> > > > --
> > > > Alan G
> > > > Author of the Learn to Program web site
> > > > http://www.alan-g.me.uk/
> > > > http://www.amazon.com/author/alan_gauld
> > > > Follow my photo-blog on Flickr at:
> > > > http://www.flickr.com/photos/alangauldphotos
> > > >
> > > > _______________________________________________
> > > > Tutor maillist - Tutor at python.org
> > > > To unsubscribe or change subscription options:
> > > > https://mail.python.org/mailman/listinfo/tutor
> > >
> > > _______________________________________________
> > > Tutor maillist - Tutor at python.org
> > > To unsubscribe or change subscription options:
> > > https://mail.python.org/mailman/listinfo/tutor
>
> _______________________________________________
> Tutor maillist - Tutor at python.org
> To unsubscribe or change subscription options:
> https://mail.python.org/mailman/listinfo/tutor
More information about the Tutor
mailing list