程序代写 CISC 235 Data Structures

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