Tree Models

Game turns/choices

  • Each state of the game is a vertex, and each indicates a legal move/play to get to a new state.
  • We saw it with tic-tac-toe, but it applies equally well to chess, checkers, go (圍棋), …
  • Even to card games or board games, but it's not usually as useful for those: the random element (shuffling/dice) makes it harder to model/analyze.
  • To make it a tree, we need to either have states reachable in only one way, or to decide that states include the history of the game but just the current appearance of the board.
  • The “root” will be the starting state of the game.

Computer Networks

  • In theory, computer networks can be any graph: as long as things are connected, they can communicate.
    • But in practice, most networks you'll see are trees.
    • … at least on the scale of a building (or even campus) or smaller.
    • Ethernet and wifi are almost the only technologies people use on that scale.
    • They are usually set up so that each computer knows its “gateway”.
    • The gateway will be the node's parent if we think of it as a tree.
    • (Ethernet can handle non-tree configurations, but they aren't common outside of data centres.)
  • Since everybody has a unique parent, we get a rooted tree.
    • … where the root is the connection between this network and the outside world.
    • The leaves are computers that people use.
    • The non-leaves (interior vertices) are hubs/routers/switches.
  • Something we know about trees: there is exactly one path between nodes.
    • That means there is no fault-tolerance in such a network.
    • If a node or edge disappears (because of hardware failure or something), then somebody is disconnected.
    • That might not be a great property for a network to have, but it's cheap to build.
    • That's why non-tree networks happen in data centres and other infrastructure places: they want redundant connections.
  • But in the tree, decisions about routing are easy.
    • If the message is to anybody but your descendants, send it up.
    • … so no/little computing power needed to make routing decisions.
    • Again, it's cheaper to build an easier to configure.

Data Structures

  • If we have any data structure in a programming language with pointers/references, we can think of it as a graph.
    typedef struct node {
        struct node *parent;
        char *data;
    } node;
  • There's a pretty good chance we won't allow cycles in the graph: it makes the data structure harder to work with.
    • We can't just traverse the data structure in the obvious way, or we'd enter an infinite loop.
    • So, we get a rooted tree.
  • The above struct assumes we're keeping pointers to the parent, but that might not be what we want.
    • It would be much easier to keep a pointer to the root node, and be able to follow pointers from there to the other data.
  • So, we'd end up with something like this:
    typedef struct node {
        struct node *child1;
        struct node *child2;
        struct node *child3;
        char *data;
    } node;
    • Then if we keep a pointer to the root, we an find anything else in the tree by following some chain of pointers.
    • … somehow. There's a lot more to say about that.

Tree Properties