Tree

Tree is a data structure that could look like in real life tree. See 202112102054# on how to traverse a tree.

Tree can be used for:

  • directory structure

There are several implementations of tree:

Characteristics

  • N nodes = root + (N - 1) edges
  • Every node except root must have one parent
  • Path of length 0 is the path the node lead to itself
  • Exactly one path exists for root to every node

Analysis

  • Most methods could result in \(O(\log N)\)
Links to this page
  • Traversal

    To traverse a data structure for example #tree or #graph, one could use several methods:

  • Spanning Tree

    Spanning Tree is a #202112101956, often seen in #202204112045 where it covers every vertex in the graph without forming a circle (acyclic).

  • Prefix Coding

    A much easier approach to identify whether a code set is a prefix code, is by inspecting whether the code set’s decision Tree#. If there is no code symbol get in the way, that is none of the symbol is the ancestor for another symbol, then the code set is a prefix code. Notice that the symbols are the leaves of the tree.

  • Linux Directory Structure

    The layout of Linux Directory Structure is a Tree# where the root is named “/”, thus the name root directory. In the root directory, there exists several directories that are mandatory like /bin, /boot, /dev, /etc, /lib, /tmp, /usr, and /var, and those that are optional such as /home, /mnt, and /root.

  • Linked List Tree

    A #202112101956 that implemented in #202110191729

  • Depth First Search (DFS)
    The work runtime complexity for it is \(O(\vert E \vert \times \vert V \vert)\). This could be improved to \(O(\vert E \vert)\) if the data structure is a 202112101956.

    Depth First Search is an algorithm that could do a pre-order 202112102054# search on either 202112101956 or 202204112045.

  • Binary Tree

    Binary Tree is a #202112101956 where every node could have at most 2 children.

  • B-Tree

    B-Tree of order M is a #202112101956 that has the following Characteristics.

#data-structure #tree