Trees + AVL Flashcards
A tree designed for locating specific keys (values)
Search Trees
Operations of Search Trees
SEARCH
MINIMUM
MAXIMUM
SUCCESSOR
PREDECESSOR
INSERT
DELETE
Is a binary tree that satisfies the following properties:
For any node x:
- the keys in the left subtree of x are <= x.key
- the keys in the right subtree of x are >= x.key
Binary Search Tree (BST)
Search begins at the _________ and traces a __________ path in the tree using BST Property
root, downward
Search Pseudocode: TreeSearch(x,k)
Recursive Approach
TreeSearch(x,k){
if x == NULL or k == x.key
return x
if k < x.key
return TreeSearch(x.left, k)
else
return TreeSearch(x.right, k) }
Search Pseudocode: TreeSearch(x,k)
Iterative Approach
TreeSearch(x,k){
while x != NULL and k != x.key
if k < x.key
x = x.left
else
x = x.right
return x
}
To get the minimum, just follow the ________________ pointers from the root
left-child
Tree-Minimum Pseudocode
TreeMinimum(x){
while x.left != NULL
x = x.left
return x }
To get the maximum, just follow the ________________ pointers from the root
right-child
Tree-Maximum Pseudocode
Tree-Maximum(x){
while x.right != NULL
x = x.right
return x
}
The ______________ of a node is the next node visited in an inorder traversal
Successor
TRUE or FALSE
If all keys are distinct, the successor of a node x is the node with the smallest key greater than x.key
TRUE
If the right subtree of node x is non-empty, then the successor of x is the ___________________________.
leftmost node in x’s right subtree (minimum of right-subtree)
If the right subtree of node x is empty, then the successor of x is the ______________ of x whose ______________ is also an ancestor of x.
lowest ancestor, left-child
Tree-Successor Pseudocode
Tree-Succcessor(x){
if x.right != NULL
return Tree-Minimum(x.right)
else
y = x.parent
while y != NULL and x == y.right
x = y
y = y.parent
return y }
The ______________ of a node is the previous visited node in an inorder traversal
Predecessor
If the left subtree of node x is non-empty, then the predecessor of x is the ___________________________.
rightmost node in x’s left subtree (maximum of left subtree)
If the left subtree of node x is empty, then the predecessor of x is the ______________ of x whose ______________ is also an ancestor of x.
lowest ancestor, right-child
Tree-Predecessor Pseudocode
Tree-Predecessor(x){
if x.left != NULL
return Tree-Maximum(x.left)
else
y = x.parent
while y != NULL and x == y.left
x = y
y = y.parent
return y }
___________ and ___________ operations change BST in a way that the BST property is preserved
Insertion, Deletion
_________ searches for a NULL to replace with the new node Z
Insertion
Tree-Insert Pseudocode
Tree-Insert(T,x){
x = T.root
y = NULL
while x != NULL
y = x
if z.key <= x.key
x = x.left
else
x = x.right
z.p = y
if y == NULL
T.root = z
else if z.key <= y.key
y.left = z
else
y.right = z }
3 Cases for Node Deletion in BST
Case 1: No Children
Case 2: Has 1 Child
Case 3: Has 2 Children
Case 1 (No Children) deletion fix-up
Remove it by replacing its parent’s child pointer to NULL
Case 2 (1 Child) deletion fix-up
Elevate the child to take z’s position in the tree. Modify z’s parent to replace z with z’s child
(z here is the node to be deleted)
Case 3 (2 children) deletion fix-up
Find z’s successor y (in z’s right subtree) and replace z’s key with y’s.
Perform delete operation on y (case 1 or 2)
A BST that is height balanced
Adelson-Velsky and Landis (AVL) Tree
AVL Meaning
Adelson-Velsky and Landis Tree
In AVL, for each node, the heights of its left and right subtrees differ by __________.
at most 1
In AVL, whenever the height differs by more than 1, _________ is done
rebalancing
The height of an empty tree (or subtree) is ___.
-1
Insertion could disrupt the AVL height balance property. We fix this via ___________
rotation
AVL Insertion Steps
- Do BST Insert
- from the node inserted up to the root, we update the balance and do fix up when necessary
4 Types of Rotations
Single Rotation (Left and Right)
Double Rotation (Left-Right and Right-Left)
Node where height imbalance occured
Critical node (C)
Child of critical node that is an ancestor of the inserted node
Pivot node (P)
Child of pivot node that is an ancestor of the inserted node
Q node (Indi ko alam tawag T.T)
4 Fix Up cases
Left-Left Leaning
Right-Right Leaning
Left-Right Leaning
Right-Left Leaning
Left-Left Leaning Fix Up
Right Rotate at Critical node
Right-Right Leaning Fix Up
Left Rotate at Critical Node
Left-Right Leaning Fix Up
Left Rotate at Pivot
Right Rotate at Critical node
Right-Left Leaning Fix Up
Right rotate at Pivot
Left Rotate at Critical node
is a connected, acyclic, undirected graph.
Free Tree
is a free tree in which one of the vertices is distinguished
from the others (root).
Rooted Tree
The _______________ is the number of edges on the path.
path length
The _________ of a node is the length of the longest downward path from that node to a leaf.
height
The _________ of a node is the length of the path from the root to that node.
depth
Any node y on the path from root to a node x is an ___________ of x.
ancestor
If y is an ancestor of x, then x is a _____________ of y.
descendant
TRUE or FALSE:
Every node is both an ancestor and a descendant of itself.
TRUE
If y is an ancestor of x and x ≠ y, then y is a ________________ of x and
x is a __________________ of y.
proper ancestor, proper descendant
The _________________ is the tree induced by descendants of x, rooted at x.
subtree rooted at x
TRUE or FALSE
A tree consists of the root (r) and one or more subtrees T1, T2, … , Tk each of whose roots are children of r.
FALSE, a root can have no subtree but still be a tree
The number of edges in a tree is equal to the ________________ .
number of nodes – 1.
Tree Applications
file systems
parsing / parse trees
decision trees
databases
A binary tree T is a structure defined
on a finite set of nodes that either
- contains no nodes, or
- is composed of a root node, a
binary tree called its left subtree,
and a binary tree called its right
subtree
IDK T.T
A binary tree is a rooted tree in which every node has ___________ children.
at most two
Level i is full if there are exactly _________ at that level.
2^i nodes
TRUE or FALSE:
A binary tree of height k is full if level k is full.
TRUE
A tree traversal refers to the process of __________________.
visiting each node
aka tree search or walking the tree
Tree Traversal
A binary tree used to represent expressions.
Binary Expression Trees
leaves –> ________________
internal nodes –> _______________
operands
operators
