Trees Flashcards
A non-linear data structure that consists of nodes
and is connected by edges with a hierarchical
organization
Trees
The nodes in a tree are arranged in a ________________
parent-child
relationship
The topmost node in a tree is called the ______
root node
It contains some data and
may have references to its child nodes.
Node
Each element in tree
Node
the first node of the tree. And is the initial node of the tree in data structures.
Root
T or F
In the tree data structure, there must be only one root node.
T
Represents a connection between two nodes. It defines the relationship between a parent node and its child node. A line connecting the nodes.
Edge
A node that has one or more child nodes. It is located above its child nodes in the hierarchy.
Parent
A node that has a parent node. It is located below
its parent node in the hierarchy.
Child
Nodes that share the same parent. They are at
the same level in the tree.
Siblings
A node that does not have any child nodes.
It is
also known as a terminal node.
Leaf
Nodes that have one or more child
nodes. They are neither leaf nodes nor the root node.
Internal Nodes
the total number of children of a node.
DEGREE
The
highest degree of the node among all the nodes in a tree.
Degree of Tree
the distance of a node from the root.
LEVEL
The number of edges from the leaf node to the
particular node in the longest path is known as the height
of that node.
Height
the height of the root node
“Height of Tree”.
many edges from the root node to the particular
node
Depth
In the tree, the total
number of edges from the root node to the leaf node in
the longest path
“Depth of Tree”.
the sequence of nodes and edges from one node to another node is called the path between those two
nodes. The length of a this is the total number of nodes in this.
PATH
TYPES OF TREES:
• GENERAL TREE:
• BINARY TREE:
• BINARY SEARCH TREE:
• AVL TREE:
• B-TREE:
Properties
It follows all properties of the tree data structure.
A node can have any number of nodes.
GENERAL TREE:
Properties
Follows all properties of the tree data structure.
It can have at most two child nodes.
These two children are called the left child and the right child
BINARY TREE
Properties
Left node value<= root node <= right node value
Follows all properties of the tree data structure
has a unique property known as the binary search property.
BINARY SEARCH TREE
Properties
Follows all properties of the tree data structure.
Self-balancing.
Each node stores a value called a balanced factor, which is the difference in the height of the left sub-tree and right sub-tree.
All the nodes in the ________ must have a balance factor of -1, 0, and 1.
AVL TREE: (Georgy Adelson-Velsky and Landis - inventor)
Properties
is a special kind of self-balancing search tree in which each node can contain more than one key and can have more than two children.
is also known as a height-balanced m-way tree.
B-TREE
• a process of visiting each node and prints their value.
TREE TRAVERSAL
LRN
Post-Order Traversal
LNR
In-Order Traversal
NLR
Pre-Order Traversal
Can construct a unique binary tree from pre-order and Post-Order
Cannot!
Can construct a unique binary tree from In-Order and Pre-Order ?
Can
Can construct a unique binary tree from In-Order and Post-Order?
Can
