5 ms·

> Wait, why do the leaves contain no data? What's the point of even adding them then? You need something to represent a completely empty tree. You also need so

> Wait, why do the leaves contain no data? What's the point of even adding them then? You need something to represent a completely empty tree. You also need something to represent in a Tree node that "there is no child here". It makes sense to use the same thing for both. In Python and other languages with nullable references you can just use None (or null, or ...) for this. But ML-family languages have no nullable references. You could use option types instead, but that would look pretty complex, something like (my Haskell is rusty): data Tree a = Maybe (TreeStructure a) data TreeStructure a = TreeNode (Maybe (TreeStructure a)) (Maybe (TreeStructure a)) (You should be able to use Tree a in the definition of TreeNode, but I wanted to show the "real" structure, which you would also have to care about when pattern matching.) It's easier to have an empty leaf instead. Personally I would possibly call it EmptyLeaf or maybe NoTree instead of just Leaf.

contravariant 7y ago
At this point we're basically discussing what kind of tree you want. Including if you truly need an empty tree (which is maybe necessary if you want to do Monad like operations that don't return a result, but then doing so on a tree is pretty weird in the first place, and I'm not entirely sure what you'd do if a node in the middle of the tree returned Nothing, do you just throw away its children?). The best design will depend on what you need a tree for as well as in what language you will implement it. But yeah if you want an empty tree I'd recommend just using None in python. You'll just need checks like 'if node' where you'd otherwise have pattern matching; you could improve QoL a little by defining an iterator over the existing children. If you really want a separate object then you run into all kinds of annoying stuff, including the fact that by default python will allocate separate objects for all of them, which is 1) slow and 2) bad for memory usage.
- tom_mellior 7y ago
  > if you truly need an empty tree I'm sure in Python you regularly have uses for empty lists, dicts, and strings. (Probably not empty tuples, but what do I know.) Why would empty trees be particularly strange or exotic?
  - contravariant 7y ago
    For what it's worth I prefer to use empty tuples as a cheap empty iterator (empty lists are mutable and not unique, so the empty tuple is a bit nicer). The concept of an empty tree is not too exotic, but I'm struggling a bit to find a use for it (which is not to say that there isn't one). What makes it different in my mind is that with lists/dicts/strings it makes perfect sense to filter them, which is a bit weirder with trees. It's easy to imagine a scenario where you filter a lists and end up with no items, I'm struggling a bit to figure out what happens if you filter a tree, do you just throw out the entire subtree if one of the parents is filtered out? It seems to me that the answer depends strongly on what you want to use the tree for, and if you know that you will likely also know whether you need an empty tree or not. Just to illustrate why the 'remove the subtree if the parent is filtered away' option is not obviously the correct one, consider that it also makes sense to just remove the node and return a list of disjointed trees. In that case the 'empty' case is just an empty list of trees.
    - the_af 7y ago
      An algorithm that builds a tree out of some other data source matching some criteria can return an empty tree if no element matches the filter. Then, algorithms that process trees must take empty trees in consideration. (Yes, you could write "if notEmpty(tree) then f(tree)" in your language, but then you have a partial function f which doesn't work if tree is empty, and partial functions often lead to bugs because we tend to forget about their partial-ness). Almost every "collection" data structure needs to have an empty representation. Trees are no different.
    - tom_mellior 7y ago
      Filtering any data structure means building up a new filtered copy, not removing from the current one, no? >>> x = [1, 2, 3, 4] >>> y = list(filter(lambda n: n < 3, x)) >>> x, y ([1, 2, 3, 4], [1, 2]) Same with trees: No removal is needed for filtering, you could implement it something like: def filter_tree(f, tree): filtered_tree = new_empty_tree() # it's useful if this is *not* None! for element in tree: if f(element): filtered_tree.add(element) return filtered_tree Regardless, removal of individual, even internal, nodes from trees is of course possible without removing entire subtrees. The details depend very much on the actual kind of tree, but you can start at https://en.wikipedia.org/wiki/Binary_tree#Deletion https://en.wikipedia.org/wiki/Binary_tree#Deletion
super_mario 7y ago
A leaf is a node that has no children. So you don't need to represent it directly. Just check both children and if they are both None, it's a leaf. Empty tree can be represented with root node that is a leaf and has no data.
- tom_mellior 7y ago
  You forgot to include your Haskell code.
  - super_mario 7y ago
    I'm talking about how you could do this in Python. Don't know much about Haskell.

contravariant 7y ago

At this point we're basically discussing what kind of tree you want. Including if you truly need an empty tree (which is maybe necessary if you want to do Monad like operations that don't return a result, but then doing so on a tree is pretty weird in the first place, and I'm not entirely sure what you'd do if a node in the middle of the tree returned Nothing, do you just throw away its children?). The best design will depend on what you need a tree for as well as in what language you will implement it. But yeah if you want an empty tree I'd recommend just using None in python. You'll just need checks like 'if node' where you'd otherwise have pattern matching; you could improve QoL a little by defining an iterator over the existing children. If you really want a separate object then you run into all kinds of annoying stuff, including the fact that by default python will allocate separate objects for all of them, which is 1) slow and 2) bad for memory usage.

tom_mellior 7y ago
> if you truly need an empty tree I'm sure in Python you regularly have uses for empty lists, dicts, and strings. (Probably not empty tuples, but what do I know.) Why would empty trees be particularly strange or exotic?
- contravariant 7y ago
  For what it's worth I prefer to use empty tuples as a cheap empty iterator (empty lists are mutable and not unique, so the empty tuple is a bit nicer). The concept of an empty tree is not too exotic, but I'm struggling a bit to find a use for it (which is not to say that there isn't one). What makes it different in my mind is that with lists/dicts/strings it makes perfect sense to filter them, which is a bit weirder with trees. It's easy to imagine a scenario where you filter a lists and end up with no items, I'm struggling a bit to figure out what happens if you filter a tree, do you just throw out the entire subtree if one of the parents is filtered out? It seems to me that the answer depends strongly on what you want to use the tree for, and if you know that you will likely also know whether you need an empty tree or not. Just to illustrate why the 'remove the subtree if the parent is filtered away' option is not obviously the correct one, consider that it also makes sense to just remove the node and return a list of disjointed trees. In that case the 'empty' case is just an empty list of trees.
  - the_af 7y ago
    An algorithm that builds a tree out of some other data source matching some criteria can return an empty tree if no element matches the filter. Then, algorithms that process trees must take empty trees in consideration. (Yes, you could write "if notEmpty(tree) then f(tree)" in your language, but then you have a partial function f which doesn't work if tree is empty, and partial functions often lead to bugs because we tend to forget about their partial-ness). Almost every "collection" data structure needs to have an empty representation. Trees are no different.
  - tom_mellior 7y ago
    Filtering any data structure means building up a new filtered copy, not removing from the current one, no? >>> x = [1, 2, 3, 4] >>> y = list(filter(lambda n: n < 3, x)) >>> x, y ([1, 2, 3, 4], [1, 2]) Same with trees: No removal is needed for filtering, you could implement it something like: def filter_tree(f, tree): filtered_tree = new_empty_tree() # it's useful if this is *not* None! for element in tree: if f(element): filtered_tree.add(element) return filtered_tree Regardless, removal of individual, even internal, nodes from trees is of course possible without removing entire subtrees. The details depend very much on the actual kind of tree, but you can start at https://en.wikipedia.org/wiki/Binary_tree#Deletion https://en.wikipedia.org/wiki/Binary_tree#Deletion

super_mario 7y ago

A leaf is a node that has no children. So you don't need to represent it directly. Just check both children and if they are both None, it's a leaf. Empty tree can be represented with root node that is a leaf and has no data.

tom_mellior 7y ago
You forgot to include your Haskell code.
- super_mario 7y ago
  I'm talking about how you could do this in Python. Don't know much about Haskell.