DSA - Trees Flashcards
What is a Tree?
- Very Flexible and powerful data structure
- Involves connect NODES like LL
- Has a Hierarchal structure unlike linear structure of LL
Define Root:
-Node that has no incoming edges (HAS NO PARENTS)
- Unique node at the base of the tree (TOP)
Give 4 example of Types of Trees
- Unary Tree ==> (0-1 Children) ≈ LL
- Binary Tree ==> (0-2 Children)
- Ternary Tree ==> (0-3 Children)
- Quad Tree ==> (0-4 Children)
Define Leaf:
-Node that has no outgoing edges (HAS NO CHILD NODES)
Define Height:
-Length of longest path from root to leaf
LEVEL ≡ HEIGHT
STARTS AT 0
Define Size:
No. of Nodes
Define Edge:
The Link that connects nodes
What is Height & Size of tree with 1 node?
Height = 0
Size = 1
What is Height & Size of tree with no node?
Height = -1
Size = 0
AKA EMPTY TREE
Name the 3 Tree Implementation Options :
- BASIC
- Sibling List
- Array
Explain Basic implementation?
A Doubly Linked List that has a field value and right and left child pointer
- Prev Pointer points to left child
- Next Pointer points to right child
Explain Sibling list Implementation?
Similar to basic in that it is a Doubly Linked List however, the Prev pointer points to left child and the Next pointer point to the sibling of the left child
(This node should be right child of the parent)
Explain Array Implementation?
Binary Trees
Binary Trees use this Array layout where index 1 is the root and the children of node at index i is 2i & (2i)+1
example:
[X|33|10|30|X|X|21|1|X|X|X|X]
33 is root
10 & 30 are 33’s Children
21 & 1 are 30’s Children
Define Binary Tree ADT
Each Parent has only 2 Child Nodes
What does constructor EmptyTree()?
Returns an empty tree
What does constructor MakeTree(V,L,r)?
Returns a new tree, where root node has value V, left subtree l & right subtree r
What does the accessor isEmpty(t)?
Returns tree if list is empty, otherwise False
What does root(t) do?
Returns the root node value of the tree
What does left(t) do?
Returns the left subtree of the tree
What does right(t) do?
Returns the right subtree of the tree
CODE to Create a Tree?
MakeTree(33,
leaf(10),
MakeTree(30,
MakeTree(21,
EmptyTree,
Leaf(25))),
Leaf(1)))
CODE to Reverse a Tree Order?
reverseTree(t) {
if( isEmpty(t)
return (t)
else
return (MakeTree(root(t)),
reverseTree(right(t))
reverseTree(left(t))
}
What does FLATTEN do to the Tree?
Turns the tree into a list (maybe Linked List)
Usually Starting with Left subtree, Root , Right subtree
CODE to Flatten?
flatten(t) {
if Tree.isEmpty(t)
return EmptyList
else
return append(flatten(left(t)),
MakeTree(root(t), flatten(right(t)))))
}
What Defines a Quad Tree?
- Has 4 Children
- Only Leaf Node holds values
- Internal Nodes Have 4 Children
What is useful about Quad Tree?
Representing 2D data, like images (image compression)
What does the Constructor baseQT do?
Returns a single leaf node quad tree with a value
What does MakeQT(luqt,ruqt,llqt,rlqt) do?
Returns a new quad tree, built for 4 sub-quad trees
What does accessor isValue(qt)do?
returns true if qt is a value node quad Tree
CODE to ROTATE QT?
rotate(qt) {
if( isValue(qt) )
return qt
else
return makeQT( rotate(rl(qt)),
rotate(ll(qt)),
rotate(ru(qt))
rotate(lu(qt))) }
What does the Code to Rotate DO?
90 degree Rotation
Define Binary Search Tree:
- Holds value in such a way that we can quickly search/ insert elements so that we can find them
- VALUES in Left subtree are smaller than the root
- VALUES in Right subtree are larger than the root
- The subtrees are also BST
What happens when a BST is flattened?
The values are returned in ORDER
CODE for Insertion in BST:
insert(v,bst) {
if( isEmpty(bst))
return MakeTree (v, EmptyTree, EmptyTree)
else if ( v < root(bst))
return MakeTree( root(bst), insert(v,left(bst)),
right(bst))
else if (v > root(bst))
return MakeTree(root(bst), left(bst),
insert(v,right(bst)))
else error(“ERROR;_value_already_in_tree”)
What is the problem with the Insertion Code?
Method is insufficient as it requires us to make a new copy of BTS with additional values
What is the CODE for Searching a BST Recursively ?
isIn( value v, tree t) {
if( isEmpty(t) )
return false
else if (v == root)
return true
else if (v < root(t))
return isIn(v, left(t)) // searches recursively on either
else // Right/Left Node depending on if
return isIn(v, right(t)) // it is Smaller / Larger
What is the CODE for Searching a BST Iteratively?
isIn (value v , tree t) {
while (( not isEmpty(t)) and (v != root(t)) )
if (v < root(t) )
t = left(t) // updates t to point to left child
else
t = right(t) // updates t to point to right child
return ( not isEmpty(t))
What is the Complexity of Search for this BST:
1
\
2
\
3
\
4
Also Describe it?
O(n)
The BST in diagram has all its items are inserted linearly with 1 as its root
What is the Complexity of Search for this BST:
4
/ \
2 6
/ \ / \
1 3 5 7
O(log_2(n))
What is Average Search case for BST?
O(log_2(n))
What is Average Insertion case for BST
O(log_2(n))
- Depends on height of BST which is O(log_2(n))
What is Average Height of GENERAL BST?
O( √n )
What are the 2 Options to Delete BST?
First Option:
- Insert all items except the one you want to delete into a new
BST
- COMPLEXITY = O(log_2(n))
- Worse than deleting from an Array: O(n)
Second Option:
- Find the node containing the elements to de DELETED
- If it is a LEAF, REMOVE it
- IF only one of the node’s children is not EMPTY, replace the
node with the root of the non-empty subtree
- Otherwise,
Find the left-Most node in the right subtree replace the value
to be deleted with that of the left-most node and replace the
left-most node with its right child
CODE to DELETE BST:
delete(value v, tree t){
if(isEmpty(t))
error(“ERROR:_given_items_is_not_in_given_tree”)
else
if( v < root(t))
return MakeTree( root(t), delete(v,left(t)),right(t))
else if ( v > root(t))
return MakeTree( root(t), left(t),delete(v,right(t)))
else
if (isEmpty(left(t)))
return right(t)
else if (isEmpty(right(t)))
return left(t)
else
return smallestNode(right(t), left(t),
removeSmallestNode(t))
}
CODE for smallestNode?
smallestNode(tree t) {
if (isEmpty(left(t))) // if empty return root
return root(t)
else
return smallestNode(left(t)) // otherwise check left
}
CODE for removeSmallestNode?
removeSmallestNode(tree t) {
if (isEmpty(left(t))) // if left subtree is empty, your on
return right(t) // the node you want to remove
// may have right child so return that
else
return MakeTree(root(t), removeSmallestNode(left(t)),
right(t))
// Makes a new tree with smallest node removed
// On left subtree everything else is unchanged
}
CODE to check Binary Tree is a BST?
isbst (tree t) {
if ( isEmpty(t) )
return true
else
return (allsmaller(left(t),root(t)) and isbst(left(t) and
allbigger(right(t), root(t)) and isbst(right(t))))
CODE for ALLSMALLER?
allsmaller (tree t , value v) {
if (isEmpty(t))
return true
else
return ((root(t) < v) and allsmaller(left(t),v) and
allsmaller(right(t),v))
CODE for ALLBIGGER?
allbigger (tree t, value v) {
if ( isEmpty(t))
return true
else
return ((root(t) > v) and allbigger(left(t),v) and
allbigger(right(t),v))
CODE for Sorting BST?
printInOrder (tree t) {
if(not isEmpty(t) ){
printInOrder(left(t))
print(root(t))
printInOrder(right(t))
}
} // CODE essentially flattens the tree
sort (array a of size n) {
t = EmptyTree
for i = 0,1,…,n-1
t = insert(a[i],t) // insert elements in treee
printInOrder(t) // prints them in order
}
How do you change the Sorting CODE to insert it into an array?
-REMOVE print(root(t))
- Put List<Integer> BST = new ArrayList<>();
- BST.add(root(t))
- keep everything the same</Integer>
Define AVL tree:
A BST is said to be AVL when it has a balance at every node is either 1,0 or -1
Define Height of a Node:
Height of a node is the length of the longest path from that node to a leaf
How do you Calculate balance of a Tree / At a Node?
Height of Left subtree - Height of Right subtree
What does a balance of -1 mean?
Overweight to right/ Balanced to Right
What does a balance of 1 mean?
Overweight to left/ Balanced to Left
What does a balance of 0 mean?
Right & Left subtree have the same maximum length
What is the MAX size of the tree?
2^(h+1) - 1
What is the MIN size of the tree?
T_h= F_(h+3) -1
- where F is Fibonacci Sequence
- T_h is Fibonacci Tree
- h is height of Tree
How do u make Fibonacci Tree T_n?
T_n = T_(n-1) + T_(n-2) + 1
How do u draw Fibonacci Tree T_n?
- Draw T_(n-1) & T_(n-2)
- Then connect these with 1 external NEW node
What is Binet’s Formula?
F_k = (((√5 +1)/2)^k -((√5 -2)/2)^k ) / √5 = Aprox. O(1.16^k)
Aprox. O(1.16^k) REMEMBER THIS
What is Size of AVL tree in its Height?
EXOPENTIAL
What is Height of AVL tree in its Size?
Logarithmic
What is the Complexity of Insertion, Deletion & Searching of AVL tree?
log(n)
WORST CASE HEIGHT IS LOG IN SIZE
Describe the Complexity of Inserting(x)?
- FIND leaf to insert x ==> Takes O(log(n)) steps
- Insert in leaf ==> O(1) steps
- DO balancing on way up ==> O(log(n)) many times do O(1)
steps
IN TOTAL O(log(n))
DELETE IS SIMILAR TO DO THIS
Describe the Complexity of Searching(x)?
GOES through at MOST O(log(n))- many levels
IN TOTAL O(log(n))
What is AVL tree Invariants?
BALANCE of EVERY NODE is 1,0,-1
When Inserting a new element into the tree we allow breaking the invariant, then amend this by re-balancing the tree.
How does insert work in AVL trees?
- Same a BST Insertion
- Check balance
- Fix if balance it is not 1,0,-1
What the Four Balance cases?
LL,RR,LR,RL
How does delete work in AVL trees?
- Same a BST Deletion
- Check balance
- Fix if balance it is not 1,0,-1
How do you fix Left-Left imbalance (LL)?
Right Rotation from the first node you go Left FROM
How do you fix Right-Right imbalance (RR)?
Left Rotation from the first node you go Right FROM
How do you fix Left-Right imbalance (LR)?
Left rotation from the node you go left into and the one you go Right from after.
- THIS BECOMES AN LL CASE:
Then after the rotation the new root for the subtree, perform a right rotation on it.
How do you fix Left-Right imbalance (RL)?
Right rotation from the node you go right into and the one you go Left from after.
- THIS BECOMES AN RR CASE:
Then after the rotation the new root for the subtree, perform a Left rotation on it.
CODE FOR RR:
Node leftRotate(Node x) {
Node y = x.right;
Node T2 = y.left;
y.left = x;
x.right = T2;
x.height = max(height(x.left), height(x.right)) + 1;
y.height = max(height(y.left), height(y.right)) + 1;
return y;
}
CODE FOR LL:
Node rightRotate(Node y) {
Node x = y.left;
Node T2 = x.right;
x.right = y;
y.left = T2;
y.height = max(height(y.left), height(y.right)) + 1;
x.height = max(height(x.left), height(x.right)) + 1;
return x;
}
AVL tree uses?
-For indexing large records in databases
-For searching in large databases
Idea of BST Insertion?
- Takes val and bst as parameters
- Checks if bst isEmpty if so makes tree with v as root and left , right EmptyTree
- If root is larger than val, makeTree with root, Insert method on v and left subtree, & right subtree
- If root is smaller than val, makeTree with root, left subtree and Insert method on v & right subtree
- else Error value already in tree
Idea of RECURSIVELY Searching a BST?
- isIn takes val & tree as parameters
- Checks if tree is empty , if so returns false
- Checks if root = val, if so true
- Checks if val < root , if do a isIn with val and left subtree
-else do a isIn with val and right subtree
Idea of ITERATIVELY Searching a BST?
- isIn takes val & tree (t) as parameters
- While Tree is not empty and val is not root :
- check if val < root, if so update t to point to left child
- else update t to point to right child
- Return not isEmpty(t), T if value is found/ F if doesn’t exists
Idea of Deleting from BST?
- Takes val & tree t as parameters
- Checks if tree is empty , Returns Error Item is not in tree
- Checks if val < root if so return
makeTree(root, delete(v, left(t)),right(t) - else Checks if val > root if so return
makeTree(root, left(t),delete(v, right(t)) - Otherwise :
- Check if Left OR Right Child are empty and return the other tree (IF LEFT WAS EMPTY RETURN RIGHT) - else return makeTree(smallestNode(right(t),left(t), removeSmallestNode(right(t)))
Idea for Deleting the smallestNode?
- Takes tree t as parameter
- Checks if left child is empty, if so return root
- else return smallestNode(left(t))
// REPEATS TILL NO MORE LEFT SUBTREES
t is non-empty BST
Idea for removeSmallestNode?
- Takes tree t as parameter
- Checks if left child is empty, if so return right child
-else return makeTree(smallestNode(right(t),left(t), removeSmallestNode(right(t)))
// NEW TREE WITH SMALLEST NODE REMOVED FROM LEFT SUBTREE & EVERYHTING ELSE IS UNCHANGE
t is non-empty BST
Idea for checking if Binary Tree is BST
- If tree is empty it is a valid BST
- Otherwise BST if:
- All vals in left branch are < pivot
USE ALLSMALLER with left(t) & root(t) - All vals in right branch are > pivot
USE ALLSMALLER with right(t) & root(t) - Left branch is a valid BST
USE isBST with t - Right Branch is a valid BST
USE isBST with t
- All vals in left branch are < pivot
Idea for isBst?
- Takes tree as parameter
- Checks if tree is empty, if so returns true
- Otherwise
returns allsmaller(left(t),root(t)) & isbst(left(t)) & allbigger(right(t),root(t)) & isbst(right(t))
Idea for allBigger?
- Takes Tree and val as input
- Checks if empty, if so returns true
- Otherwise
return root(t) > v & allBigger(left(t),v) & allBigger(right(t),v)
Idea to Print in Order?
- Take tree as input
- Check if it is not empty if so PrintInOrder left subtree, root and right subtree
//PRINTS RESULTS IN ORDER
Idea of sort in BST?
- Takes an array of size n
- Make t an emptyTree
- Iterate through the array, insert the elements in index i of array into t
- Call PrintInOrder(t) to print values
