# Overview When talking about [Tree](/algorithm-notes/outline/overview-4/overview.md#tree) data structure, we normally omit the term ***free*** that a *free tree* is an acyclic, connected, undirected [graph](/algorithm-notes/outline/overview-3/overview.md). And a possibly disconnected acyclic undirected graph is *forest*. Theorem. 1. A *G = (V, E)* is an undirected graph, then 1. *G* is a *free tree*. 2. any two vertices in *G* are connected through a single path. 3. *G* is connected, but removing an edge will result in a disconnected graph. 4. *G* is connected, acyclic and |*E*| = |*V*| - 1. 5. if adding any single edge to |*E*| will cause the graph to form a cycle. ## Rooted Tree and Ordered Tree A [Rooted Tree](/algorithm-notes/outline/overview-4/overview.md#rooted-tree-and-ordered-tree) is a *free tree* that has a virtual topmost node distinguishable from others which called the *root* of the tree. The children of a tree node is called the *descendant* of that node and every children call their parent node the *ancestor*. Child nodes under the same node call each other *siblings* and node with no children is called *leaf* (external node), a non-leaf node is *internal node*. The length of a path from *root* of a tree to a node x is the ***depth*** of x in the tree (the ***depth*** of *root* is 0). The ***height*** of a node in a tree is the value of longest path leading from that node to a leaf in the tree; it generalizes to a formula for computing: 𝒽(x) = max( 𝒽(*left subtree of x*), 𝒽(*right subtree of x*)) + 1 An [ordered tree](/algorithm-notes/outline/overview-4/overview.md#rooted-tree-and-ordered-tree) is a rooted tree in which children of each node are ordered. e.g. a node in a tree has *k* children, then it has 1th, 2nd, .. kth child. *Note: most of the tree data structure we use is a **rooted tree** for analysis simplicity.* ## Binary and *k*-ary Tree A [Binary tree](/algorithm-notes/outline/overview-4/overview.md#binary-and-k-ary-tree) is defined on a set of nodes that either contains no nodes or is composed with the *root* node, its connected left subtree and a corresponding right subtree. In a binary tree structure, filling all missing children of nodes with empty nodes of no descendants will result in a structure called ***full binary tree***. For trees that have more than 2 children per node, every node (includeing the *root*) in such a tree has no more than *k* number of children. It is termed as a *k*-ary Tree. A ***complete k-ary tree*** is a tree in which all leaves have the same *depth* and all non-leaf nodes have *k* direct children. ## Table of Contents * [AVL Tree](/algorithm-notes/outline/overview-4/balanced-search-tree/avl-tree.md) - a trivial implementation of a balanced binary tree. * [Red-Black Tree](/algorithm-notes/outline/overview-4/balanced-search-tree/red-black-tree.md) - a prevalent balanced binary tree implementation. * [Heap](/algorithm-notes/outline/overview-4/heap.md) - a special tree structure facilitates various applications such as [priority queue](https://en.wikipedia.org/wiki/Priority_queue) and [heap sort](/algorithm-notes/outline/overview-2/heap-sort.md). * [B-Tree](/algorithm-notes/outline/overview-4/balanced-search-tree/b-tree.md) - a disk based tree structure, particularly useful in database design. * [Disjoint-Set](/algorithm-notes/outline/overview-4/disjoint-set.md) - a set operation that finds relevance among data and build up forests for faster manipulations. * [Threaded Binary Tree](/algorithm-notes/outline/overview-4/threaded-binary-tree.md) - a special form of binary tree that connect leaves to parents, useful in designing Morris traversal, which require Ο(1) extra space. * [Segment Tree](/algorithm-notes/outline/overview-4/segment-tree.md) - a binary tree used for storing intervals or segments within a data array to speed up queries such as [Range Minimum Query](/algorithm-notes/outline/overview-4/segment-tree.md). --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://cs-notes.gitbook.io/algorithm-notes/outline/overview-4/overview.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.