Here we give definitions and links to several different types of tree structures

== Basic Definitions ==

=== Vocabulary used to define trees ===

   1. A '''tree''' (or free tree) is a connected, acyclic, undirected graph
   1. If an undirected graph is acyclic, but disconnected, it is called a '''forest'''.
   1. '''rooted''' trees have a distinguished '''node''' called the '''root''' - ''r''.
   1. ''x'' is an '''ancestor''' of ''y'' if ''x'' is on the unique simple path between ''r'' and ''y''.
   1. In the case above, ''y'' is a '''descendent''' of ''x''.
   1. A node is both a descendent and a ancestor to itself. 
   1. If ''x'' is an ancestor to ''y'' and ''x''!=''y'' then ''x'' is a '''proper acestor''' of ''y''. 
   1. Proper descendent is similarly defined.
   1. We use '''child''' and '''parent''' for nodes with edges between them. Likewise we use the term siblings for nodes that have the same parent.
   1. A node with no children is an '''external node'''
   1. A non-leaf node is an '''internal node.'''
   1. The '''subtree rooted at ''x'' '''is the tree induced by descendants of ''x'', rooted at ''x''.
   1. The number of children of a node in a rooted tree ''T'' is called the '''degree of the node'''. 
   1. The length of the path (edges) from the root ''r'' to a node ''x'' is the '''depth of ''x'' in ''T'''''.
   1. The '''height of a ''node''''' in a tree is the number of edges on the longest simple downward path from the node to a leaf.
   1. The '''height of a tree''' is the height of its root.

=== Properties of trees ===

   1. G is a free tree.
   1. Any 2 vertices in G are connected by a unique SimplePath
   1. G is connected, but if any edge is removed from E, the resulting graph is disconnected
   1. G is connected, and |E|=|V|-1.
   1. G is acyclic, and |E|=|V|-1.
   1. G is acyclic, but if any edge is added to E, the resulting graph contains a cycle.

=== Ordered vs. Positional Trees ===

'''Ordered trees''' have a root and are considered ordered from root to leaf. There is no distinction in how siblings are ordered. '''Positional trees''' are what we commonly work with in computer science because we order the siblings as well. A ''k-nary'' tree is a positional tree where the children are numbered 1 - ''k''. 

   1. A '''Full Tree''' is a ''k-nary'' tree in which each node is either a leaf or has degree ''k''.
   1. A '''Complete ''k-nary'' Tree''' is a ''k-nary'' tree in which all the leaves have the same depth.

== Binary Trees ==

A '''Binary Tree''' is a positional tree structure defined recursively on a finite set of nodes that:

   * Contain no nodes, or
   * is composed of three disjoint set of nodes: a '''root''' node, a binary tree called it's '''left subtree''', and a binary tree called its '''right subtree'''.

== Binary Search Trees ==

== Red Black Trees ==

== B-Trees ==