Binary Search Trees

Master / Vertiefung Künstliche Intelligenz
1

(Re: Questions from Jonas’ Exercise Group)

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

Binary Search Trees
Hey everyone!

During my session on tuesday 12:00-14:00, there were some questions on binary search trees that remained unclear.

Leaves vs. internal nodes:

The correct way to go about a binary search tree is to have all nodes [i]but[/i] the leaves carry numbers.
This way, you can have even numbers of inserted nodes (problematic if both carry numbers) but still have log(n)
access times (unlike when only the leaves carry numbers).

So the leaves in your implementations should all be "dangling" without information. That all goes into the internal nodes.

Please excuse my case of "Tafelblindheit". :rolleyes:

The idea behind [m]count_leaves[/m]

To avoid some confusion, [m]count_leaves[/m] is supposed to be a measure of the structure of the tree that your 
function [m]construct[/m] constructs. What would be a "better" or "worse" structure? How does [m]count_leaves[/m] reflect this?

There’s more information on this in the obvious place:
https://en.wikipedia.org/wiki/Binary_search_tree

P.S.: Please note, that the deadline to hand in your exercises is stroke of midnight from
Friday to Saturday, not Sunday to Monday as I assumed. See also the other topic for that.

1 „Gefällt mir“
3

Okay to clear things up, because I might have learned another terminology regarding leaves ( = nodes with no children instead of nodes with “empty” children, there were no “empty” nodes).

We do use explicitely empty nodes instead of just ignoring their (non)existence. Only those empty nodes have no children themselves and are therefore leaves.
We do not call those nodes leaves, that only have empty child nodes (or “no children” if you don’t use empty nodes).

I might have to change my code a bit now :rolleyes:

The measure of how many leaves there are is only changing by factor 2, doesn’t change a lot in terms of what it tells us.

I’m curious, why is the use of empty nodes better?

4

I was wrong, I got it now :slight_smile: