Tree Concepts: Difference between revisions
| Line 20: | Line 20: | ||
:::[[Image:Graph_Forest.png]] | :::[[Image:Graph_Forest.png]] | ||
=Rooted Tree= | |||
A '''rooted tree''' is a [[#Free_Tree|free tree]] in which one of the vertices is distinguished from the others. | |||
:::[[File:Tree_Concepts.png]]</center> | |||
<span id='Root'></span>We call the distinguished vertex the '''root''' of the tree. | |||
<span id='Node'></span>We often refer to the [[Graph_Concepts#Vertex|vertex]] of a rooted tree as a '''node''' of the tree. | |||
<span id='Ancestor'></span><span id='Descendant'></span>For a node x in a rooted tree, we call any node y on the simple path from root to x an '''ancestor''' of x. If y is an ancestor of x, then x is a '''descendant''' of y. Every node is both an ancestor and descendant of itself. If y is an ancestor of x and x ≠ y, then we call y a '''proper ancestor''' of x, and x is a '''proper descendant''' of y. | |||
The '''subtree rooted at x''' is the tree induced by descendants of x, rooted at x. | |||
<span id='Parent'></span><span id='Child'></span>If the last edge on the simple path from the root of the tree to a node x is (y, x), then y is the '''parent''' of x and x is the '''child''' of y. The root is the only node in the tree with no parent. | |||
If two nodes have the same parent, they are '''siblings'''. | |||
<span id='Leaf'></span>A node with no children is a '''leaf''' or an '''external node'''. A non-leaf node is an '''internal node'''. | |||
=Search Tree= | =Search Tree= | ||
=Binary Tree= | =Binary Tree= | ||
Revision as of 20:39, 9 October 2021
Internal
Overview
A tree is a particular case of a graph.
Free Tree
A free tree is a connected, acyclic, undirected graph.
For an undirected graph G = (V, E), the following statements are equivalent:
- G is a free tree.
- Any two vertices in G are connected by a unique simple path.
- G is connected, but if any edge is removed from E, the resulting graph is disconnected.
- G is connected and │E│ = │V│ - 1.
- G is acyclic and │E│ = │V│ - 1.
- G is acyclic, but if any edge is added to E, the resulting graph contains a cycle.
Forest
If the undirected graph is acyclic, but disconnected, it is a forest.
Rooted Tree
A rooted tree is a free tree in which one of the vertices is distinguished from the others.
We call the distinguished vertex the root of the tree.
We often refer to the vertex of a rooted tree as a node of the tree.
For a node x in a rooted tree, we call any node y on the simple path from root to x an ancestor of x. If y is an ancestor of x, then x is a descendant of y. Every node is both an ancestor and descendant of itself. If y is an ancestor of x and x ≠ y, then we call y a proper ancestor of x, and x is a proper descendant of y.
The subtree rooted at x is the tree induced by descendants of x, rooted at x.
If the last edge on the simple path from the root of the tree to a node x is (y, x), then y is the parent of x and x is the child of y. The root is the only node in the tree with no parent.
If two nodes have the same parent, they are siblings.
A node with no children is a leaf or an external node. A non-leaf node is an internal node.