Please enable JavaScript.
Coggle requires JavaScript to display documents.
M7 (Tree: Connected acyclic graph) - Coggle Diagram
M7
Tree: Connected acyclic graph
The number of edges in a tree is always one less than the number of its vertices
Rooted Trees
One of its many applications is describing hierarchies
The depth of a vertex v is described as the length of the simple path from the root of the tree to v
A tree's height is equal to the length of the simple path from the root of the tree to a leaf
When analysing tree algorithms, it helps to draw the tree's extension, replacing empty subtrees with special nodes. These nodes are called external, while the original nodes are called internal. By definition, the extension of the empty binary tree is a single external node.
Ordered Trees
A rooted tree in which all the children of each vertex are ordered
For conveniency, assume all the children are ordered left to right
Binary Trees
An ordered tree in which every vertex has no more than two children, and each child is designated as left or right child of its parent
Binary Trees may also be empty
The divide-and-conquer technique is easily applied to Binary Trees, given that by definition, it already divides itself into two smaller structures of the same type
Binary Search Trees
BSTs are Binary Trees in which each vertex has a number assigned to them, and each parental vertex has a number higher than all the numbers in its left subtree, and lower than all the numbers in its right subtree
Searching and Insertion
Recursively:
2 more items...
Traversals
Inorder Traversal: Left Subtree > Root > Right Subtree
Preorder Traversal: Root > Left Subtree > Right Subtree
Postorder Traversal: Left Subtree > Right Subtree > Root
Full Binary Tree: Every node has either zero or two children
Not completely connected acyclic graph: Forest
Each of a forest's connected components are trees