Module 4 Flashcards
Examination
STANDS AS A PIVOTAL NONLINEAR DATA STRUCTURE
IS EITHER EMPTY OR CONSISTS OF A ROOT NODE AND ZERO OR MORE SUBTREES.
Tree
Type of Trees
- ORDERED TREE
- ORIENTED TREE
- FREE TREE
FINITE SET OF NODES WHERE ONE IS THE ROOT AND THE REST ARE PARTITIONED INTO ORDERED SUBTREES, PRESERVING THE SIGNIFICANCE OF NODE ORDER.
ORDERED TREE
A TREE WHERE THE ORDER OF SUBTREES FOR EACH NODE DOESN’T HOLD SIGNIFICANCE.
ORIENTED TREE
HAS NO NODE DESIGNATED AS THE ROOT AND THE ORIENTATION FROM A NODE TO ANY OTHER NODE IS INSIGNIFICANT.
FREE TREE
A FREE TREE WITH A DESIGNATED ROOT TRANSFORMS INTO AN ORIENTED TREE
WHEN A FREE TREE IS DESIGNATED A ROOT NODE, IT BECOMES AN ORIENTED TREE. WHEN THE ORDER OF THE NODES ARE DEFINED IN AN ORIENTED TREE, IT BECOMES AN ORDERED TREE.
Tree Progression
Types of Representations
Link Representations
Binary Representations
o UTILIZES LINKS TO DEPICT TREE STRUCTURES, WHERE EACH NODE CONTAINS LINKS TO ITS POSSIBLE SONS.
Link Representations
o AN ALTERNATIVE STRUCTURE, PRIMARILY FOR BINARY TREES, USING LEFT AND RIGHT POINTERS TO DESIGNATE THE LEFTMOST SON AND THE NEXT YOUNGER BROTHER
Binary Representations
- ASSEMBLING DISJOINT TREES FORMS A _______
- WHEN ZERO OR MORE DISJOINT TREES ARE TAKEN TOGETHER, THEY ARE KNOWN AS A ______.
Forest
- A PROCESS CONVERTING AN ORDERED FOREST INTO A UNIQUE BINARY TREE AND VICE VERSA USING A SPECIFIC METHOD,
Natural Correspondence
A HIERARCHICAL DATA STRUCTURE CONSISTING OF NODES ORGANIZED IN A SPECIFIC ARRANGEMENT
Binary Tree Structure
Binary Tree Structure KEY CHARACTERISTICS ARE
o NODES
o ROOTS NODES
o CHILD NODES
o LEAVES OR TERMINAL NODE
o INTERNAL NODE
CONTAINS:
o DATA OR PAYLOAD.
o REFERENCES OR POINTERS TO AT MOST TWO CHILD NODES, TYPICALLY DENOTED AS THE LEFT CHILD AND THE RIGHT CHILD.
IN A BINARY TREE CAN HAVE ZERO, ONE, OR TWO CHILDREN.
Node
- THE TOPMOST NODE OF THE TREE.
- IT SERVES AS THE STARTING POINT FOR ACCESSING ALL OTHER NODES IN THE TREE.
Root Node
- EVERY NODE (EXCEPT THE LEAVES) HAS AT MOST TWO CHILDREN - A LEFT CHILD AND A RIGHT CHILD.
- THESE ______ ARE CONNECTED DOWNWARDS FROM THEIR PARENT NODE.
Chilld Node
- NODES WITHOUT ANY CHILDREN ARE TERMED AS _________.
LEAVES OR TERMINAL NODES
- NODES THAT HAVE AT LEAST ONE CHILD ARE CONSIDERED _________.
INTERNAL NODES
Node Relationships in a Binary Tree
Root Node
Parent and Children Nodes
Leaves or Terminal Nodes
Internal Nodes
Siblings
Ancestors and Descendants
- THE TOPMOST NODE IN THE BINARY TREE.
- DOES NOT HAVE A PARENT NODE AND SERVES AS THE STARTING POINT FOR TRAVERSING THE TREE.
Root Node
- EACH NODE (EXCEPT THE ROOT) HAS A PARENT NODE.
- NODES MAY HAVE AT MOST TWO CHILDREN, KNOWN AS THE LEFT CHILD AND THE RIGHT CHILD.
Parent and Children Nodes
- NODES WITHOUT CHILDREN ARE THE __________.
- THEY DO NOT HAVE ANY FURTHER DESCENDANTS.
Leaves or Terminal Node
- NODES WITH AT LEAST ONE CHILD ARE _______.
- THEY SERVE AS INTERMEDIARIES BETWEEN THE ROOT AND THE LEAVES.
Internal Nodes
- NODES THAT SHARE THE SAME PARENT ARE CALLED __________.
- THEY ARE ON THE SAME LEVEL OF THE TREE AND HAVE THE SAME PARENT NODE.
Siblings
- _________ OF A NODE ARE ALL THE NODES PRESENT ON THE PATH FROM THE ROOT TO THAT PARTICULAR NODE.
- ____________ OF A NODE ARE ALL THE NODES REACHABLE FROM THAT NODE, INCLUDING ITS CHILDREN, GRANDCHILDREN, AND SO FORTH.
Ancestors and Descendants
Types of Binary Trees
Skewed Binary Tree
Strict Binary Tree
Full Binary Tree
o EVERY NODE HAS NO LEFT (RIGHT) SUBTREE, CREATING A LINEAR STRUCTURE.
Skewed Binary Tree
- EACH NODE EITHER HAS TWO CHILDREN OR NONE AT ALL
Strict Binary Tree
- EVERY INTERNAL NODE HAS EXACTLY TWO CHILDREN.
Full Binary Tree
Complete Binary Tree
* CONSTRUCTED BY SYSTEMATICALLY DELETING NODES FROM A FULL BINARY TREE IN A SPECIFIC ORDER (RIGHT TO LEFT, BOTTOM TO TOP).
Complete Binary Tree
Properties of Binary Trees
Level and Height
Internal and External Nodes
Number of Nodes
Terminal Nodes
o NODES’ DISTANCE FROM THE ROOT. THE ROOT IS AT LEVEL 0, AND EACH LEVEL MOVES FURTHER AWAY FROM THE ROOT.
Level
o THE LENGTH OF THE LONGEST ROOT-TO-LEAF PATH. IT SIGNIFIES THE MAXIMUM DEPTH OF THE TREE.
Height
o NODES WITH AT LEAST ONE CHILD.
Internal Node
o NODES WITHOUT CHILDREN, ALSO KNOWS AS TERMINAL OR LEAF NODES.
External Node
- THE MAXIMUM NUMBER OF NODES FOR A DEPTH OF K IS 2^K - 1, AND THE MINIMUM NUMBER IS 2^K+1 – 1.
Number of nodes
- THE COUNT OF ______ (N0) OR LEAVES IN RELATION TO NODES WITH DEGREE 2 (N2) IS GIVEN BY N0 = N2 + 1.
- THIS RELATION HOLDS IN ANY BINARY TREE, WHERE THE NUMBER OF LEAVES IS ONE MORE THAN THE NUMBER OF NODES WITH EXACTLY TWO CHILDREN.
Terminal Nodes
- IS THE PROCESS OF VISITING AND PROCESSING EACH NODE IN A BINARY TREE IN A SYSTEMATIC ORDER.
Binary Tree Traversal
(Root -> Left -> Right)
Pre-Order Traversal
(Left -> Root -> Right)
In-Order Traversal
( Left -> Right -> Root).
Post-Order Traversal
Advance Concepts and Variants
Self-Balancing Binary Tree
Binary Heaps
- Red-Black Trees, AVL Trees
o TREES THAT AUTOMATICALLY BALANCE THEMSELVES, ENSURING OPTIMAL PERFORMANCE FOR OPERATIONS LIKE INSERTION, DELETION, AND SEARCH.
Self-Balancing Binary Tree
- Mini-Heap, Max-Heaps
o SPECIALIZED BINARY TREES USED FOR PRIORITY QUEUES, ENSURING EFFICIENT ACCESS TO HE MINIMUM OR MAXIMUM ELEMENT.
Binary Heaps
- IS A FUNDAMENTAL DATA STRUCTURE IN COMPUTER SCIENCE THAT ORGANIZES NODES IN A HIERARCHICAL STRUCTURE.
Binary Search Trees
Operation on Binary Search Trees
Searching
Insertion
Deletion
- THE SEARCH OPERATION IN A BST (BINARY SEARCH TREE) INVOLVES COMPARING THE VALUE TO BE FOUND WITH THE VALUE AT THE CURRENT NODE
Searching
- WHEN INSERTING A NEW NODE INTO A BST
- START WITH A SEARCH TO FIND THE APPROPRIATE LOCATION FOR THE NEW NODE.
- IF THE SEARCH REACHES A NULL POSITION, INSERT THE NEW NODE WITH THE VALUE ‘K’ AT THAT POSITION ACCORDING TO THE BST PROPERTY.
Insertion
- DELETING A NODE IN A BST REQUIRES CAREFUL HANDLING TO MAINTAIN THE TREE’S BST PROPERTY:
- IF THE NODE TO BE DELETED IS A LEAF NODE (NO CHILDREN), SIMPLY REMOVE IT BY UPDATING ITS PARENT’S POINTER.
- IF THE NODE HAS ONLY ONE CHILD, REPLACE THE NODE TO BE DELETED WITH ITS CHILD.
- IF THE NODE HAS TWO CHILDREN:
- FIND EITHER ITS IN-ORDER PREDECESSOR OR SUCCESSOR.
- REPLACE THE NODE TO BE DELETED WITH THE PREDECESSOR OR SUCCESSOR.
- ADJUST THE POINTERS TO MAINTAIN THE BST PROPERTY.
Deletion
- HAPPENS WHEN THE TREE IS BALANCED.
- AVERAGE CASE: O(LOG₂ N)
OCCURS WHEN THE TREE IS DEGENERATE (SKEWED, ALL NODES TO ONE SIDE).
- WORST CASE: O(N)
- SIMILAR TO SEARCH, THESE OPERATIONS HAVE O(LOG₂ N) TIME COMPLEXITY ON AVERAGE BUT CAN DETERIORATE TO O(N) IN A DEGENERATE TREE.
Insertion and Deletion
- MAINTAIN O(LOG₂ N) TIME FOR SEARCH, INSERTION, AND DELETION.
BALANCED BSTS
- PERFORM SIMILAR TO A LINKED LIST WITH O(N) TIME COMPLEXITY FOR SEARCH, MAKING THEM LESS EFFICIENT.
UNBALANCED (DEGENERATE) BSTS
- ARE A FUNDAMENTAL TYPE OF SELF-BALANCING BINARY SEARCH TREE NAMED AFTER THEIR INVENTORS, ADELSON-VELSKY AND LANDIS.
AVL trees
Characteristics of AVL Trees
Balance Factor
Balancing Conditions
- EACH NODE IN AN AVL TREE HAS A BALANCE FACTOR, WHICH IS THE DIFFERENCE IN HEIGHT BETWEEN THE LEFT AND RIGHT SUBTREES.
Balance Factor
- FOR ANY NODE IN THE AVL TREE, THE HEIGHT DIFFERENCE (BALANCE FACTOR) BETWEEN ITS LEFT AND RIGHT SUBTREES SHOULD NOT EXCEED 1.
- THIS CONDITION HOLDS TRUE FOR EVERY NODE IN THE TREE.
Balancing Conditions
Operations in AVL Trees
Insertion
Deletion
- WHEN A NEW NODE IS INSERTED INTO AN AVL TREE, THE TREE MIGHT BECOME UNBALANCED.
- AFTER INSERTION, THE BALANCE FACTORS OF NODES ALONG THE INSERTION PATH ARE UPDATED.
- IF THE BALANCE CONDITION IS VIOLATED, ROTATIONS (SINGLE OR DOUBLE) ARE PERFORMED TO RESTORE BALANCE WHILE MAINTAINING THE ORDERING PROPERTY OF THE BST.
Insertion
- DELETING A NODE MAY ALSO LEAD TO AN IMBALANCE IN THE AVL TREE.
- SIMILAR TO INSERTION, AFTER DELETION, THE BALANCE FACTORS OF AFFECTED NODES ARE UPDATED.
- IF NECESSARY, ROTATIONS ARE PERFORMED TO RESTORE BALANCE.
Deletion
Rotations In AVL Trees
Single Rotations
Double Rotations
- LEFT ROTATION:
- RIGHT ROTATION:
Single Rotations
- LEFT-RIGHT ROTATION
- RIGHT-LEFT ROTATION
Double Rotations
