Lesson 6: Trees Flashcards by Queen Glace

Tree is a __________ data structure. (choices: linear, non-linear)

non-linear

How well did you know this?

Not at all

Perfectly

Tree imposes a __________ structure, on a collection of items

Hierarchial

How well did you know this?

Not at all

Perfectly

collection of nodes

Tree

How well did you know this?

Not at all

Perfectly

If not empty, a tree consists of: (clue: RSE)

node R (the ROOT)
zero or more non-empty SUBTREES
each subtree is connected by a directed EDGE from R

How well did you know this?

Not at all

Perfectly

[Tree Terminologies]
—mother node of a tree structure
—does not have parent
—first node in hierarchical arrangement

Root

How well did you know this?

Not at all

Perfectly

[Tree Terminologies]
—stores the data and its role is the same as in the linked list
—connected by the means of links with other nodes

Node

How well did you know this?

Not at all

Perfectly

[Tree Terminologies] immediate predecessor of a node

Parent

How well did you know this?

Not at all

Perfectly

[Tree Terminologies] When a predecessor of a node is parent then all successor nodes are called __________ nodes.

Child

How well did you know this?

Not at all

Perfectly

[Tree Terminologies]
—connects the two nodes
—pointer to node in a tree structure

Link/Edge

How well did you know this?

Not at all

Perfectly

[Tree Terminologies]
—locates at the end of the tree
—does not have any child

Leaf

How well did you know this?

Not at all

Perfectly

[Tree Terminologies] The highest number of nodes that is possible in a way starting from the first node (ROOT) to a leaf node

Height

How well did you know this?

Not at all

Perfectly

[Tree Terminologies] rank of tree hierarchy

Level

How well did you know this?

Not at all

Perfectly

[Tree Terminologies] the level of the root node

Level 0

How well did you know this?

Not at all

Perfectly

[Tree Terminologies] The child node of same parent

Sibling

How well did you know this?

Not at all

Perfectly

[Tree Terminologies] Another term for sibling nodes

Brother nodes

How well did you know this?

Not at all

Perfectly

[Tree Terminologies] The maximum number of children that exists for a node

Degree of a Node

How well did you know this?

Not at all

Perfectly

[Tree Terminologies] The node with degree zero

Terminal node

How well did you know this?

Not at all

Perfectly

[Tree Terminologies] number of successive edges from source node to destination node

Path length

How well did you know this?

Not at all

Perfectly

[Tree Terminologies] maximum level of any leaf of a tree

Depth

How well did you know this?

Not at all

Perfectly

[Tree Terminologies] group of disjoint trees

Forest

How well did you know this?

Not at all

Perfectly

any node that has at least one non-empty child

internal node

How well did you know this?

Not at all

Perfectly

Simplest form of tree

Binary Tree

How well did you know this?

Not at all

Perfectly

A binary tree consists of: (clue: NS)

NODE (root node)
SUBTREES (left and right)

How well did you know this?

Not at all

Perfectly

A tree is binary if each node has a maximum of __________ branches.

Two

How well did you know this?

Not at all

Perfectly

When every non-leaf node in binary tree is filled with left and right sub-trees, the tree is called ____________

Strictly binary tree

A tree in which each level of the tree is completely filled, except the bottom level

Complete binary tree

Operations on Binary Tree (clue: CELRPSIDSCT)

Create Empty Lchild Rchild Parent/Father Sibling Insert Deletion Search Copy Tree Traversal

[Operations on Binary Tree] create an empty binary tree

Create

[Operations on Binary Tree] return true when binary tree is empty, else return false

Empty

[Operations on Binary Tree] A pointer is returned to left child of a node, when a node is without left child, NULL pointer is returned

Lchild

[Operations on Binary Tree] A pointer is returned to right child of a node, when a node is without left child, NULL pointer is returned

Rchild

[Operations on Binary Tree] a pointer to father of a node is returned

Father/parent

[Operations on Binary Tree] A pointer to brother of the node is returned or else NULL pointer is returned

Sibling

[Operations on Binary Tree] to insert a node

Insert

[Operations on Binary Tree] to delete a node

Deletion

[Operations on Binary Tree] to search a given node

[Operations on Binary Tree] copy one tree to another

Copy

Used to display/access the data in a tree in a certain order

Traversal of a Binary Tree

In traversing, _____ sub-tree is always traversed after _____ sub-tree

right, left

Three methods of traversing (clue: PIP)

Preorder Traversing Inorder Traversing Postorder Traversing

[Methods of Traversing] ---Root-Left-Right ---Prefix expression

Preorder Traversing

[Methods of Traversing] ---Left-Root-Right ---Infix expression

Inorder Traversing

[Methods of Traversing] ---Left-Right-Root ---Postfix expression

Postorder Traversing

Stores keys in the nodes in a way so that searching, insertion and deletion can be done efficiently

Binary Search Tree

Left child should be _______ than the value of the root. (choices: greater than, less than, equal to)

Less than

Right child should be _______ than the value of the root. (choices: greater than, less than, equal to)

Greater than or equal to

balanced binary search tree in which balance factor of every node is either -1, 0 or +1

AVL Tree

difference between the heights of the left and right subtrees of that node

Balance factor

When was the AVL tree introduced and who introduced it?

1962 G.M. Adelson-Velsky, E.M. Landis.

process of moving nodes either to left or to right to make the tree balanced

Rotation

Two types of rotations (clue: SD)

Single Rotation Double Rotation

Rotations under Single Rotation

Single Left Rotation (LL Rotation) Single Right Rotation (RR Rotation)

Rotations under Double Rotation

Left Right Rotation (LR Rotation) Right Left Rotation (RL Rotation)

[Rotations] Every node moves one position to left from the current position

Single Left Rotation (LL Rotation)

[Rotation] Every node moves one position to right from the current position

Single Right Rotation (RR Rotation)

[Rotation] A sequence of single left rotation followed by a single right rotation

Left Right Rotation (LR Rotation)

[Rotation] A sequence of single right rotation followed by a single left rotation

Right Left Rotation (RL Rotation)

AVL Tree Operations (clue: SID)

Search Insertion Deletion

A special tree-based data structure and is considered as a complete binary tree

Heap Tree

Two types of heap (clue: MM)

Min-heap Max-heap

[Types of heap] the smallest element is the root of the tree and each node is greater than or equal to its parent

Min-heap

[Types of heap] the largest element is the root of the tree and each node is less than or equal to its parent

Max-heap

The common implementation of a heap data structure

Binary Heap

Properties of binary heap

---A complete binary tree when all the levels are completely filled except possibly the last level and the last level has its keys as much left as possible ---Can be a min-heap or max-heap

A binary heap is a complete _____ tree and can best be represented as an _____

binary, array

Operations on Binary Heap (minimum heap) (clue: IDDEG)

Insert() Delete() decreasekey() extractMin() getMin() Note: For maximum heap, the operations reverse accordingly.

[Operations on Binary Heap (minimum heap)] Inserts a new key at the end of the tree. Depending on the value of the key inserted, the heap can be adjusted, without violating the heap property.

Insert() Note: For maximum heap, the operations reverse accordingly.

[Operations on Binary Heap (minimum heap)] Deletes a key.

Delete() Note: For maximum heap, the operations reverse accordingly.

[Operations on Binary Heap (minimum heap)] Decreases the value of the key. There might have the need to maintain the heap property when this operation takes place.

decreasekey() Note: For maximum heap, the operations reverse accordingly.

[Operations on Binary Heap (minimum heap)] Removes the minimum element from the min-heap. It needs to maintain the heap property after removing the minimum element.

extractMin() Note: For maximum heap, the operations reverse accordingly.

[Operations on Binary Heap (minimum heap)] Returns the root element of the min-heap.

getMin() Note: For maximum heap, the operations reverse accordingly.

Applications of Heaps (clue: HPGW)

Heapsort Priority Queues Graph algorithms Worst-case complexity of quicksort algorithm can be overcome by using heap sort

[Applications of Heaps] binary heap supports all the operations required for successfully implementing the priority queues in O(log n) time

Priority Queues

An application of binary trees and priority queues

Huffman Coding