Please enable JavaScript.
Coggle requires JavaScript to display documents.
TREES, Rooted Trees - Coggle Diagram
TREES
-
Searching and Insertion
When we need to search for an element of a given value v in such a tree, we do it recursively in the following manner.
. If the tree is empty, the search ends in failure.
If the tree is not empty, we compare v with the tree’s root K(r). If they match, a desired element is found and the search can be stopped; if they do not match
we continue with the search in the left subtree of the root if v < K(r) and in the right subtree if v > K(r)
Thus, on each iteration of the algorithm, the problem of searching in a binary search tree is reduced to searching in a smaller binary search tree.
-
-
Rooted Trees
for every two vertices in a tree, there always exists exactly one simple path from one of these vertices to the other.
This property makes it possible to select an arbitrary vertex in a free tree and consider it as the root of the so-called rooted tree
For any vertex v in a tree T , all the vertices on the simple path from the root to that vertex are called ancestors of v.
The vertex itself is usually considered its own ancestor; the set of ancestors that excludes the vertex itself is referred to as the set of proper ancestors
Ordered Trees
An ordered tree is a rooted tree in which all the children of each vertex are ordered. It is convenient to assume that in a tree’s diagram, all the children are ordered left to right
A binary tree can be defined as an ordered tree in which every vertex has no more than two children and each child is designated as either a left child or a right child of its parent;
a number assigned to each parental vertex is larger than all the numbers in its left subtree and smaller than all the numbers in its right subtree. Such trees are called binary search trees.
-
-