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
using namespace std;
template
{
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
void (*action)(BTnode
{
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
void (*action)(BTnode
{
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
void (*action)(BTnode
{
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
BTnode
BTnode
// Create the right subtree
BTnode
BTnode
BTnode
// Create the root node
BTnode
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
{
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
bool BST
{
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
{
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
const T& BST
{
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
const T& BST
{
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
void BST
{
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
void BST
{
}
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
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
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->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.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