CISC 235 Data Structures
Feb 14, Live Session
Review for Tree *Quiz 2
Copyright By PowCoder代写 加微信 powcoder
Time: this Friday, 60 mins Enter time:
Feb 18, 2022 11:30 AM until 11:38 AM
Check practice questions and answers Check quiz 1 answers
What will be covered in Quiz 2?
General Trees
Binary Trees
Binary Search Trees (BST)
Self-balanced BST
– AVL Trees (Trees that always stay balanced using rotation)
– Red- (Trees that always stay balanced using colors)
Review of Trees
1. Concepts–Recursivedefinitionoftree
2. Properties
3. Operations & time complexity
– traversal, search, insert/delete, rotations
4. Implementations
– class variables, functions
5. Applications
– use tree for search purpose, encoding purpose, etc.
• A Tree is a special linked data structure
• The relationships in a tree are hierarchical, with some objects being “above” and some “below” others.
• Parent – children relationship
Hierarchies
Many ways to represent tree-like information
Height vs. Depth vs. Level
Depth -> Downward Direction Height (longest)->Upward Height of root = height of tree = max(height of nodes) = max(depth of nodes)
Compute height of a Binary Tree
height(node) = max(height(node.left), height(node.right)) +1
def height(node):
if node is None: //or “if node is leaf, return 0” return -1
# Compute the height of each subtree lheight = height(node.left)
rheight = height(node.right)
#Use the larger one if lheight > rheight :
return lheight+1 else:
return rheight+1
Time Complexity to find height of a BST?
Time Complexity to find height of a BST
In the average case, for a balanced binary tree
T(n) = 2T(n/2) + Θ(1);
Every recursive call gives you two problems of half the size. By master theorem, this would evaluate to T(n) = Θ(n)
In the worst case, where each node has only one child.
T(n) = T(n-1) + Θ(1)
Which evaluates to T(n) = Θ(n)
class BTNode:
def __init__(self,
self.left = None
self.right = None
self.data = data
BTNode temp
pRoot = BTNode(5)
temp = BTNode(7)
pRoot.left = temp
temp = BTNODE(-3) pRoot.right = temp // etc…
temp-> value left
12100 1000
value 1000 left right
temp-> value
Implementation of Tree
Only reply on one Node class
1100 right
Binary Tree
A binary tree is a special form of tree. In a binary tree, every node has at most two children nodes.
A Binary Tree “carey”
“martha” “milton”
class BTNode:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
Full, Complete, Perfect Binary Trees
If every node has either 0 or 2 children, a binary tree is called full.
If the lowest d-1 levels of a binary tree of height d are filled and level d is partially filled from left to right, the tree is called complete.
If all d levels of a height-d binary tree are filled, the tree is called
Operations on Binary Trees
The following are common operations that we might perform on a Binary Tree:
• Enumerating all the items • Searching for an item
• Adding a new item
• Deleting an item
Tree Traversal
• Pre-order traversal
• In-order traversal
• Post-order traversal
• Level-order traversal
• Implementation (Recursive, iterative) • Time complexity? -> O(n)
Euler Tour :An Easy Way to Remember the Order of Pre/In/Post Traversals
Starting just above-left of the root node, draw a loop counter-clockwise around all of the nodes.
1. Generic traversal- walk around the tree and process each node 3 times on left, from below, on right.
2. Preorder/inorder/postorder traversals are special cases of the Euler tour traversal.
3. Pre/in/post determines when to process current node!!
Level-order Traversal: Level-by-level
In a level order traversal we visit each level’s nodes, from left to right, before visiting nodes in the next level
Level-order:
To determine the order of nodes visited in a level-order traversal…
Start at the top node and draw a horizontal line left-to-right through all nodes on that row.
Repeat for all remaining rows.
The order you draw the lines is the order of the level-order traversal!
Saving and Restoring Binary Trees
Save/reconstruct using pre-order traversal + additional info O(content inside node) +
D(whether the node has left, right, both/neither subtrees)
(A,2) (B,0) (C,R) (F,0)
(A,2) (B,0) (C,R) (F,0)
(E,2) (D,0)
(E,0) (D,2)
Binary Search Trees
Binary Search Trees are a type of binary tree with specific properties that make them very efficient to search for a value in the tree.
All nodes in X’s left sub-tree must be less than X.
All nodes in X’s right sub-tree must be greater than X.
What about duplicates?
Searching a BST
Here are two different BST search algorithms, one recursive and one iterative:
Search(int V, Node ptr):
if root == None:
return false // nope
elif V == ptr.value) return true // found!!!
elif V < ptr.value
return Search(V, ptr.left))
return Search(V, ptr.right))
Search(int V,Node ptr):
while ptr != None if V == ptr.value:
return true
elif V < cur.value)
ptr = ptr.left else
ptr = ptr.right return false // nope
In the average BST with N values, how many steps are required to find our value?
50% eliminated!
50% eliminated!
50% eliminated! eliminated!
Big O of BST Search
log (N) steps 2
In the worst case BST with N values, how many steps are required find our value?
Motivation of having self-balanced BST!! (e.g., AVL and Red-Black tree)
Inserting A Into A BST
To insert a new node in our BST, we must place the new node so that the resulting tree is still a valid BST!
Where would the following new values go?
recursive version vs. it
erative version
Inserting A Into A BST
Given a random array of numbers if you insert them one at a time into a BST, what will the BST look like?
65,93,9,25,58,23,70,36,20,6
Given a ordered array of numbers if you insert them one at a time into a BST, what will the BST look like?
1,2,3,4,5,6,7,8,9,10
Insert a random array of numbers into a BST
If keys are inserted in randomly order, the number of compares in search or insert operation is ~ (2 LogN) on average case, while the worst case is about ~ (4.311 LogN) (proposed by Reed, 2003).
There is a small chance for the height to be ~ (N) in the worst case if the keys are inserted in random order.
Big O of BST Insertion
what’s the big-O of BST Insertion?
Why? Because we have to first use a binary search to find where to insert our node and binary search is O(log2n).
Once we’ve found the right spot, we can insert our new node in O(1) time.
Deleting a Node from a Binary Search Tree
Given a value V to delete from the tree:
1. Find the value V in the tree, with a slightly-modified BST search.
- Use two variables: a cur pointer & a parent pointer
2. If the node was found, delete it from the tree, making sure to preserve its ordering!
- There are three cases, so be careful!
Finding Min & Max of a BST
The minimum value is located at the left-most node. The maximum value is located at the right-most node.
Question: What’s the big-O to find the minimum or maximum element? 26
What is a AVL tree
• AnAVLtreeisabinarysearchtreethatuses modified add and remove operations to stay balanced as its elements change.
• AnAVLtreemaintainsa"balancefactor" in each node of 0, 1, or -1.
Balance Factor, for a tree node T is the height of T's right subtree minus height of T's left subtree.
BF(T) = Height(T.right) - Height(T.left)
• Atmost1differencebetweentheheightof right subtree and left subtree
Note: some textbooks use “right-left”, some use “left-right”. In Quiz, we will give clear definitions if you are asked to compute balance factor.
The height of an AVL tree with N nodes
is O(log N)
A proof by induction Let us bound n(h): the minimum number of nodes of an AVL tree
of height h.
We can find: n(0) = 1 n(1) = 2 n(2) = 4
For n>2, an AVL tree (minimum case) of height h contains the root node, one AVL subtree of height h-1 and another of height h-2.
That is, n(h) = 1+ n(h-1) + n(h-2) n(h-1)
Tracking subtree height
Many of the AVL tree operations depend on height.
– Heightcanbecomputedrecursivelybywalkingthetree;tooslow. – Instead,eachnodecankeeptrackofitssubtreeheightasafield:
Class TreeNode: data
data height left/right
TreeNode left TreeNode right
AVL tree: Insert one node
For all AVL operations, we assume the tree was balanced before the operation began.
– AddinganewnodebeginsthesameaswithatypicalBST, traversing left and right to find the proper location and attaching the new node.
– Butaddingthisnewnodemayunbalancethetreeby1: 55
AVL_tree.insert(49)
Height(55.right)-Height(55.left) =0-2 = -2
-> invalid AVL tree!
What is a Red-Black tree
A red-black tree is a binary search tree in which each node is colored either red or black.
It satisfies the following 5 properties:
1) Everynodeiseitherredorblack.
2) The root is black.
3) Every leaf(NIL) is black.
4) If a node is red, then both its children are black. -> No two consecutive nodes are red.
5) For each node x, all simple paths from the node to descendant leaves contain the same number of black nodes. -> black-height(x).
Red- : Property 1
• The path from the root to the farthest leaf is no more than twice as long as the path from the root to the nearest leaf.
-> The result is that the tree is roughly height-balanced.
Height of a red-black tree
Property 2
A red-black tree with n internal nodes has height:
h <= 2 log2(n + 1) How can we explain it?
2-3-4 tree:
all leaf nodes are at the same depth
Insert/Delete in Red-
The operations INSERT and DELETE cause modifications to the red-black tree:
1. theoperationitself,
2. color changes,
3. restructuring the links of the tree via “rotations”.
R-B tree: Insertion Time Complexity
1. Case1,onlyrecolorsnodes.
2. If Case 2 or Case 3 occurs, perform 1 or 2 rotations, and terminate.
• Running time: O(log n) insert with O(1) (rotations + recolors).
Question Types in Quiz 2
• Two on tree properties (e.g., status of tree after insert a sequence of values)
• Two Tree related Coding questions • One debug question
Sample Question: Property question
Do you agree that “In-order traversal always gives the sorted sequence of the elements in a Binary Search Tree”? Briefly explain why you agree/not agree?
Which sequence can not be an output in-order/pre-order traversal given the following binary tree? Why?
Given the red-black tree shown in Figure X, compute the black height for the root node. Briefly describe how you calculate the value.
Sample Question: code understanding & find the bug
Given the below code for task A, input and output for a testing case, can you find the bug in the code?
Sample Question: Coding
Check if a binary tree is subtree of another binary tree:
Your task is to write a function isSubtree(tree1, tree2) which takes two binary trees as input and checks if tree1 is a subtree of tree2. You can add help functions if needed.
Modify the standard AVL tree so that it can store key,value pairs.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com