Trees with more than 2 branches

[matthew-dean]

Thanks again for a great library. I'm still trying to figure it out / understand it and scale it for my needs.

I was poking around a bunch in the documentation this weekend, and one thing that keeps coming up is the apparent lack of a tree structure that is not binary. It's somewhat confusing to me because there are lots of node trees that have multiple children, such as any sort of structured document (HTML, XML, CSS). Is it just that this is out of the scope of this library? There are no performance benefits to be had?

For example, I was seeing if I could build a tree with multiple children that would "auto-collapse" like a linked list if all the children nodes were removed. For example, Like:

      A
    /    \
   B       C
 / | \   / | \
 D E F  G  H  I  

So if nodes D, E, & F are removed, I want B to auto-remove. If nodes G & H are removed, I want to add logic to remove C and have A point to I to "auto-heal" like a linked list. In other words, to never have orphan edges / nodes.

Am I just describing a DirectedGraph, but in a tree shape? I guess I'm used to in general programming, a "tree" being any number of branches, but I'm not super well-versed in graph theory, so maybe it means something different elsewhere. Related: I thought about using a DIrectedGraph, but it's not documented what happens when you delete multiple vertices at different points in the graph. Do you just get orphan edges? Or is there any way to auto-bridge edges or run custom functions for what to do with specific logic cases?

[zrwusa]

First, our library is an implementation of foundational data structures in TypeScript. These data structures are generally considered fundamental to most programming languages and are often included at the language level or in officially recommended libraries. Unfortunately, JavaScript was originally designed as a scripting language for simple DOM manipulation and did not account for such features. Moreover, the Array data structure in JavaScript is highly flexible, making it unnecessary to implement many other data structures in JS. However, as JavaScript has gained prominence in both front-end and back-end development, the importance of foundational data structures has resurfaced.

In general, basic data structures are used to solve algorithmic problems and improve efficiency. The simplest examples are Stack and Queue, which are commonly used in programming. While Array can simulate these two data structures, using Array to simulate a Queue is a suboptimal solution, especially for large datasets.

Back to your question: When we talk about "trees" in data structures, it usually refers to BinaryTree (essentially a binary linked list), which is quite different from the "trees" we discuss in front-end contexts like HTML, XML, or front-end components. A BinaryTree is designed to dynamically maintain ordered data, reducing the time complexity of operations like insertion, deletion, and lookup from O(n) to O(log n). This represents a significant improvement when working with large datasets. However, the implementation you mentioned appears to be a more application-layer, functional data structure.

The Graph data structure, on the other hand, is essentially a more loosely connected version of a LinkedList. It is often used to represent complex relationships and connections, such as in networks, where it is applied to determine paths between a source and a target. Most programming languages do not natively provide this data structure.

In summary, your application-level functional tree data structure needs to be implemented manually. Foundational data structures like these are specifically designed to solve algorithms or improve data query efficiency.

[matthew-dean]

In summary, your application-level functional tree data structure needs to be implemented manually. Foundational data structures like these are specifically designed to solve algorithms or improve data query efficiency.

This is a helpful answer, thank you!