程序代写代做代考 data structure COMP2012 Object-Oriented Programming and Data Structures

COMP2012 Object-Oriented Programming and Data Structures
Topic 7: Trees, Binary Trees, and Binary Search Trees
Dr. Desmond Tsoi
Department of Computer Science & Engineering The Hong Kong University of Science and Technology Hong Kong SAR, China
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 1 / 44

Part I
Tree Data Structure
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 2 / 44

Tree
The linear access time of linked lists is prohibitive for large amount of data.
Does there exist any simple data structure for which the average running time of most operations (search, insert, delete) is better than linear time?
Solution: Trees!
We are going to talk about
􏰢 basic concepts of trees
􏰢 tree traversal
􏰢 (general) binary trees
􏰢 binary search trees (BST)
􏰢 balanced trees (AVL tree)
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 3 / 44

Recursive Definition of Trees
A tree T is a collection of nodes connected by edges.
base case: T is empty
recursive definition: If not empty, a tree T consists of
􏰢 a root node r, and
􏰢 zero or more non-empty sub-trees: T1, T2, . . . , Tk
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 4 / 44

Tree Terminologies
Root: the only node with no parents Parent and child
􏰢 every node except the root has exactly only 1 parent
􏰢 a node can have zero or more children
Leaves: nodes with no children
Siblings: nodes with the same parent
Path from node n1 to nk: a sequence of nodes {n1,n2,…,nk} such thatni istheparentofni+1 for1≤i≤k−1.
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 5 / 44

Tree Terminologies ..
Length of a path
– number of edges on the path Depth of a node
– length of the unique path from the root to that node
Height of a node
– length of the longest path from that node to a leaf – all leaves are at height 0
Height of a tree
= height of the root
= depth of the deepest leaf
Ancestor and descendant: If there is a path from n1 to n2 – n1 is an ancestor of n2
– n2 is a descendant of n1
– if n1 ̸= n2, proper ancestor and proper descendant
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 6 / 44

Example 1: Unix Directories in a Tree Structure
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 7 / 44

Part II
Binary Tree
root
10
8
15
5
9
12
17
NULL NULL NULL NULL NULL NULL NULL NULL
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 8 / 44

Binary Trees
Generic binary tree: A tree in which no node can have more than two children.
The height of an ‘average’ binary tree with N nodes is considerably smaller than N.
In the best case, a well-balanced tree has a height of order of log N.
But, in the worst case, the height can be as large as (N − 1).
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 9 / 44

A Typical Implementation of Binary Tree ADT
#include /* File: btree.h */
using namespace std;
template class BTnode
{
public:
BTnode(const T& x, BTnode* L = nullptr, BTnode* R = nullptr)
: data(x), left(L), right(R) { }
̃BTnode() {
delete left;
delete right;
cout << "delete the node with data = " << data << endl; } const T& get_data() const { return data; } BTnode* get_left() const { return left; } BTnode* get_right() const { return right; } }; private: T data; BTnode* left; BTnode* right; // Stored information // Left child // Right child Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 10 / 44 Binary Tree: Inorder Traversal /* File: btree-inorder.cpp * * To traverse a binary tree in the order of: * left subtree, node, right subtree * and do some action on each node during the traversal. */ template
void btree_inorder(BTnode* root,
void (*action)(BTnode* r)) // Expect a function on r->data
{
if (root) {
btree_inorder(root->get_left(), action);
action(root); // e.g. print out root->data
btree_inorder(root->get_right(), action);
} }
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 11 / 44

Binary Tree: Preorder Traversal
/* File: btree-preorder.cpp
*
* To traverse a binary tree in the order of:
* node, left subtree, right subtree
* and do some action on each node during the traversal.
*/
template
void btree_preorder(BTnode* root,
void (*action)(BTnode* r)) // Expect a function on r->data
{
if (root) {
action(root); // e.g. print out root->data
btree_preorder(root->get_left(), action);
btree_preorder(root->get_right(), action);
} }
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 12 / 44

Binary Tree: Postorder Traversal
/* File: btree-postorder.cpp
*
* To traverse a binary tree in the order of:
* left subtree, right subtree, node
* and do some action on each node during the traversal.
*/
template
void btree_postorder(BTnode* root,
void (*action)(BTnode* r)) // Expect a function on r->data
{
if (root) {
btree_postorder(root->get_left(), action);
btree_postorder(root->get_right(), action);
action(root); // e.g. print out root->data
} }
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 13 / 44

Example 2: Binary Tree Creation & Traversal
#include “btree.h” /* File: test-btree.cpp */
#include “btree-preorder.cpp”
#include “btree-inorder.cpp”
#include “btree-postorder.cpp”
template
void print(BTnode* root) { cout << root->get_data() << endl; } int main() // Build the tree from bottom up { // Create the left subtree BTnode* node5 = new BTnode(5);
BTnode* node9 = new BTnode(9);
BTnode* node8 = new BTnode(8, node5, node9);
// Create the right subtree
BTnode* node12 = new BTnode(12);
BTnode* node17 = new BTnode(17);
BTnode* node15 = new BTnode(15, node12, node17);
// Create the root node
BTnode* root = new BTnode(10, node8, node15);
cout << "\nInorder traversal result:\n"; btree_inorder(root, print); cout << "\nPreorder traversal result:\n"; btree_preorder(root, print); cout << "\nPostorder traversal result:\n"; btree_postorder(root, print); cout << "\nDeleting the binary tree ...\n"; delete root; return 0; } Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 14 / 44 Example 3: Unix Directory Traversal Preorder Traversal Postorder Traversal Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 15 / 44 Example 4: Expression (Binary) Trees Above is the tree representation of the expression: (a + b ∗ c) + ((d ∗ e + f ) ∗ g) Leaves are operands (constants or variables). Internal nodes are operators. The operators must be either unary or binary. Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 16 / 44 Expression Tree: Different Notations Preorder traversal: node, left sub-tree, right sub-tree. ⇒ Prefix notation: ++a∗bc ∗+∗defg Inorder traversal: left sub-tree, node, right sub-tree. ⇒Infixnotation: a+b∗c+d∗e+f ∗g Postorder traversal: left sub-tree, right sub-tree, node. ⇒ Postfix notation: abc ∗+de ∗f +g ∗+ Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 17 / 44 Part III Binary Search Tree (BST) Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 18 / 44 Properties of a Binary Search Tree BST is a data structure for efficient searching, insertion and deletion. BST property: For every node x All the keys in its left sub-tree are smaller than the key value in node x. All the keys in its right sub-tree are larger than the key value in node x. Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 19 / 44 BST Example and Counter-Example BST Not a BST but a Binary Tree Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 20 / 44 BSTs May Not be Unique The same set of values may be stored in different BSTs. Average depth of a node on a BST is order of log N. Maximum depth of a node on a BST is order of N. Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 21 / 44 BST Search For the above BST, if we search for a value of 15, we are done at the root. < 15, we would recursively search it with the left sub-tree. > 15, we would recursively search it with the right sub-tree.
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 22 / 44

Example 5: BST Search
Let’s search for the value 9 in the following BST.
Compare
Action
9 vs. 15
continue with the left subtree
9 vs. 6
continue with the right subtree
9 vs. 7
continue with the right subtree
9 vs. 13
continue with the left subtree
9 vs. 9
eureka!
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 23 / 44

Our BST Implementation (different from textbook’s) I
template class BST /* File: bst.h */
{
private:
struct BSTnode
{
T value;
BST left;
BST right;
BSTnode(const T& x) : value(x) { } // A copy constructor for T
// BSTnode(const T& x) : value(x), left(), right() { } // Equivalent
BSTnode(const BSTnode& node) = default; // Copy constructor
// BSTnode(const BSTnode& node) // Equivalent
// : value(node.value), left(node.left), right(node.right) { }
̃BSTnode() { cout << "delete: " << value << endl; } }; BSTnode* root = nullptr; public: BST() = default; ̃BST() { delete root; } // Empty BST // Actually recursive // A node in a binary search tree // Left sub-tree or called left child // Right sub-tree or called right child Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 24 / 44 Our BST Implementation (different from textbook’s) II // Shallow BST copy using move constructor BST(BST&& bst) { root = bst.root; bst.root = nullptr; } BST(const BST& bst) // Deep copy using copy constructor { if (bst.is_empty()) return; root = new BSTnode(*bst.root); // Recursive } bool is_empty() const { return root == nullptr; } bool contains(const T& x) const; void print(int depth = 0) const; const T& find_max() const; // Find the maximum value const T& find_min() const; // Find the minimum value }; void insert(const T&); void remove(const T&); // Insert an item with a policy // Remove an item Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 25 / 44 Our BST Implementation Our implementation really implements a BST as an object. It has a root pointing to a BST node which has a value (of any type) a left BST object: a sub-tree with values smaller than that of the root. a right BST object: a sub-tree with values greater than that of the root. Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 26 / 44 BST Code: Search /* Goal: To check if the BST contains the value x. * Return: (bool) true or false * Time complexity: Order of height of BST */ template /* File: bst-contains.cpp */
bool BST::contains(const T& x) const
{
if (is_empty()) // Base case #1
return false;
if (root->value == x) // Base case #2
return true;
else if (x < root->value) // Recursion on the left sub-tree
return root->left.contains(x);
else // Recursion on the right sub-tree
return root->right.contains(x);
}
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 27 / 44

BST Code: Print by Rotating it -90 Degrees
/* Goal: To print a BST
* Remark: The output is the BST rotated -90 degrees
*/
template
void BST::print(int depth) const
{
if (is_empty())
return;
root->right.print(depth+1);
/* File: bst-print.cpp */
// Base case
// Recursion: right sub-tree
for (int j = 0; j < depth; j++) // Print the node value cout << '\t'; cout << root->value << endl; root->left.print(depth+1); // Recursion: left sub-tree
}
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 28 / 44

BST: Find the Minimum/Maximum Stored Value
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 29 / 44

BST Code: Find the Minimum Stored Value
/* Goal: To find the min value stored in a non-empty BST.
* Return: The min value
* Remark: The min value is stored in the leftmost node.
* Time complexity: Order of height of BST
*/
template /* File: bst-find-min.cpp */
const T& BST::find_min() const
{
const BSTnode* node = root;
while (!node->left.is_empty()) // Look for the leftmost node
node = node->left.root;
return node->value;
}
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 30 / 44

BST Code: Find the Maximum Stored Value
/* Goal: To find the max value stored in a non-empty BST.
* Return: The max value
* Remark: The max value is stored in the rightmost node.
* Time complexity: Order of height of BST
*/
template /* File: bst-find-max.cpp */
const T& BST::find_max() const
{
const BSTnode* node = root;
while (!node->right.is_empty()) // Look for the rightmost node
node = node->right.root;
return node->value;
}
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 31 / 44

BST: Insert a Node of Value x
E.g., insert 13 to the BST.
Proceed down the tree as you would with a search.
If x is found, do nothing (or update something). Otherwise, insert x at the last spot on the path traversed. Time complexity = Order of (height of the tree)
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 32 / 44

BST Code: Insertion
template /* File: bst-insert.cpp */
void BST::insert(const T& x)
{
if (is_empty()) // Find the spot
root = new BSTnode(x);
else if (x < root->value)
root->left.insert(x); // Recursion on the left sub-tree
else if (x > root->value)
root->right.insert(x); // Recursion on the right sub-tree
else // This line is optional; just for illustration
; // x == root->value; do nothing
}
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 33 / 44

BST: Delete a Leaf
Delete the leaf node immediately.
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 34 / 44

BST: Delete a Node with 1 Child
Adjust a pointer from its parent to bypass the deleted node.
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 35 / 44

BST: Delete a Node with 2 Children
You will have 2 choices: replace the deleted node with the
– maximum node in its left sub-tree, or
– minimum node in its right sub-tree (as in the above figure).
Remove the max/min node depending on the choice above.
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 36 / 44

Example 6.1: BST Deletions
Removing 40 from BST(a), replacing it with the min. value in its right sub-tree results in the BST(b).
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 37 / 44

Example 6.2: BST Deletions
Removing 40 from BST(a), replacing it with the max. value in its left sub-tree results in the BST(c).
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 38 / 44

Example 6.3: BST Deletions
Removing 30 from BST(c) and moving 5 from its left sub-tree result in BST(d).
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 39 / 44

BST Code: Deletion
template /* File: bst-remove.cpp */
void BST::remove(const T& x) // leftmost item of its right subtree
{
}
if (is_empty())
return;
if (x < root->value)
root->left.remove(x);
else if (x > root->value)
// Item is not found; do nothing
// Remove from the left subtree
// Remove from the right subtree
root->right.remove(x);
else if (root->left.root && root->right.root) // Found node has 2 children
{
root->value = root->right.find_min(); // operator= defined?
root->right.remove(root->value); // min is copied; can be deleted now
}
else // Found node has 0 or 1 child
{
BSTnode* deleting_node = root; // Save the root to delete first
root = (root->left.is_empty()) ? root->right.root : root->left.root;
// Set subtrees to nullptr before removal due to recursive destructor
deleting_node->left.root = deleting_node->right.root = nullptr;
delete deleting_node;
}
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 40 / 44

BST Testing Code I
#include /* File: test-bst.cpp */
using namespace std;
#include “bst.h”
#include “bst-contains.cpp”
#include “bst-print.cpp”
#include “bst-find-max.cpp”
#include “bst-find-min.cpp”
#include “bst-insert.cpp”
#include “bst-remove.cpp”
int main() {
BST bst;
while (true) {
char choice; int value;
cout << "Action: d/f/i/m/M/p/q/r/s " << "(deep-cp/find/insert/min/Max/print/quit/remove/shallow-cp): "; cin >> choice;
switch (choice) {
case ‘d’: // Deep copy
{
BST* bst2 = new BST(bst);
bst2->print(); delete bst2;
}
break;
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 41 / 44

BST Testing Code II
case ‘f’: // Find a value
cout << "Value to find: "; cin >> value;
cout << boolalpha << bst.contains(value) << endl; break; case 'i': // Insert a value cout << "Value to insert: "; cin >> value;
bst.insert(value);
break;
case ‘m’: // Find the minimum value
if (bst.is_empty())
cerr << "Can't search an empty tree!" << endl; else cout << bst.find_min() << endl; break; case 'M': // Find the maximum value if (bst.is_empty()) cerr << "Can't search an empty tree!" << endl; else cout << bst.find_max() << endl; break; case 'p': // Print the whole tree default: cout << endl; bst.print(); break; Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 42 / 44 BST Testing Code III } } } case 'q': // Quit return 0; case 'r': cout << "Value to remove: "; cin >> value;
bst.remove(value);
break;
case ‘s’: // Shallow copy
{
BST bst3 { std::move(bst) };
bst3.print();
bst.print();
}
break;
Rm 3553, desmond@ust.hk
COMP2012 (Fall 2020) 43 / 44

That’s all! Any questions?
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 44 / 44