Trees and Search Trees ♢ COMP2521 ♢ (23T1)

COMP2521(23T1) ♢ Trees, search trees ♢ [0/45]
❖ Searching


Search is an extremely common application in computing

Applications:  Google,  databases, .....
COMP2521(23T1) ♢ Trees, search trees ♢ [1/45]
❖ ... Searching

Many approaches have been developed for the "search" problem

Different approaches determined by properties of data structures:

Search costs:

Array List File
Unsorted O(n)
(linear scan)
O(n)
(linear scan)
O(n)
(linear scan)
Sorted O(log n)
(binary search)
O(n)
(linear scan)
O(log n)
(lseek,lseek,...)
COMP2521(23T1) ♢ Trees, search trees ♢ [2/45]
❖ ... Searching

Maintaining arrays and files in sorted order is costly.

Search trees are efficient to search but also efficient to maintain.

Example: the following tree corresponds to the sorted array [2,5,10,12,14,17,20,24,29,30,31,32]:

[Diagram:Pics/bigtree.png]

COMP2521(23T1) ♢ Trees, search trees ♢ [3/45]
❖ Tree Data Structures

Trees are connected graphs

[Diagram:Pics/tree.png]

COMP2521(23T1) ♢ Trees, search trees ♢ [4/45]
❖ ... Tree Data Structures

Trees are used in many contexts, e.g.


[Diagram:Pics/trees.png]

COMP2521(23T1) ♢ Trees, search trees ♢ [5/45]
❖ ... Tree Data Structures

Real-world example: organisational structure

[Diagram:Pics/trees_example1.png]

Diagram from "Data Structures and Algorithms in Java" (6th ed) by Goodrich et al
COMP2521(23T1) ♢ Trees, search trees ♢ [6/45]
❖ ... Tree Data Structures

Real-world example: hierarchical file system  (e.g. Linux)

[Diagram:Pics/trees_example2.png]

Diagram from "Data Structures and Algorithms in Java" (6th ed) by Goodrich et al
COMP2521(23T1) ♢ Trees, search trees ♢ [7/45]
❖ ... Tree Data Structures

Real-world example: structure of a typical book

[Diagram:Pics/trees_example3.png]

Diagram from "Data Structures and Algorithms in Java" (6th ed) by Goodrich et al
COMP2521(23T1) ♢ Trees, search trees ♢ [8/45]
❖ ... Tree Data Structures

Real-world example: a decision tree

[Diagram:Pics/trees_example4.png]

Diagram from "Data Structures and Algorithms in Java" (6th ed) by Goodrich et al
COMP2521(23T1) ♢ Trees, search trees ♢ [9/45]
❖ ... Tree Data Structures

A binary tree is either

[Diagram:Pics/subtrees.png]

COMP2521(23T1) ♢ Trees, search trees ♢ [10/45]
❖ ... Tree Data Structures

Other special kinds of tree

COMP2521(23T1) ♢ Trees, search trees ♢ [11/45]
❖ Binary Search Trees

Binary search trees (or BSTs) are ordered trees

[Diagram:Pics/three-bin-search-trees.png]

COMP2521(23T1) ♢ Trees, search trees ♢ [12/45]
❖ ... Binary Search Trees

Level of node = path length from root to node

Height (or depth) of tree = max path length from root to leaf

[Diagram:Pics/tree-depth.png]

COMP2521(23T1) ♢ Trees, search trees ♢ [13/45]
❖ ... Binary Search Trees

Some properties of trees ...

Ordered

Perfectly-balanced tree Height-balanced tree
Note:  time complexity of a balanced tree algorithm is typically O(height)
COMP2521(23T1) ♢ Trees, search trees ♢ [14/45]
❖ ... Binary Search Trees


Operations on BSTs:


Notes:
COMP2521(23T1) ♢ Trees, search trees ♢ [15/45]
❖ ... Binary Search Trees

Examples of binary search trees:

[Diagram:Pics/binary-search-trees.png]

Shape of tree is determined by order of insertion.

COMP2521(23T1) ♢ Trees, search trees ♢ [16/45]
❖ Insertion into BSTs

Steps in inserting values into an initially empty BST

[Diagram:Pics/insert0.png]

COMP2521(23T1) ♢ Trees, search trees ♢ [17/45]
❖ ... Insertion into BSTs


[Diagram:Pics/insert1.png]

COMP2521(23T1) ♢ Trees, search trees ♢ [18/45]
❖ ... Insertion into BSTs


[Diagram:Pics/insert2.png]

COMP2521(23T1) ♢ Trees, search trees ♢ [19/45]
❖ ... Insertion into BSTs


[Diagram:Pics/insert3.png]

COMP2521(23T1) ♢ Trees, search trees ♢ [20/45]
❖ Representing BSTs

Binary trees are typically represented by node structures

Most tree algorithms move down the tree.
If upward movement needed, add a pointer to parent.

[Diagram:Pics/tree-rep.png]

COMP2521(23T1) ♢ Trees, search trees ♢ [21/45]
❖ ... Representing BSTs

Typical data structures for trees …

// a Tree is represented by a pointer to its root node
typedef struct Node *Tree;

// a Node contains its data, plus left and right subtrees
typedef struct Node {
   int  data;
   Tree left, right;
} Node;

// some macros that we will use frequently
#define data(node)  ((node)->data)
#define left(node)  ((node)->left)
#define right(node) ((node)->right)

Here we use a simple definition for data ... just a key

COMP2521(23T1) ♢ Trees, search trees ♢ [22/45]
❖ ... Representing BSTs

Abstract data vs concrete data …

[Diagram:Pics/concrete.png]

COMP2521(23T1) ♢ Trees, search trees ♢ [23/45]
❖ Searching in BSTs

Most tree algorithms are best described recursively:

TreeContains(tree,key):
|  Input  tree, key
|  Output true if key found in tree, false otherwise
|
|  if tree is empty then
|     return false
|  else if key < data(tree) then
|     return TreeContains(left(tree),key)
|  else if key > data(tree) then
|     return TreeContains(right(tree),key)
|  else         // found
|    return true
|  end if

COMP2521(23T1) ♢ Trees, search trees ♢ [24/45]
❖ Insertion into BSTs

Insert an item into a tree;  item becomes new leaf node

TreeInsert(tree,item):
|  Input  tree, item
|  Output tree with item inserted
|
|  if tree is empty then
|     return new node containing item
|  else if item < tree->data then
|     tree->left = TreeInsert(tree->left,item)     
|     return tree
|  else if item > tree->data then
|     tree->right = TreeInsert(tree->right,item)     
|     return tree
|  else
|     return tree    // avoid duplicates
|  end if
COMP2521(23T1) ♢ Trees, search trees ♢ [25/45]
❖ Tree Traversal


Iteration (traversal) on …

For binary Trees, several well-defined visiting orders exist:
COMP2521(23T1) ♢ Trees, search trees ♢ [26/45]
❖ ... Tree Traversal


Consider "visiting" an expression tree like:

[Diagram:Pics/tree1.png]

NLR:  + * 1 3 - * 5 7 9    (prefix-order: useful for building tree)
LNR:  1 * 3 + 5 * 7 - 9    (infix-order: "natural" order)
LRN:  1 3 * 5 7 * 9 - +    (postfix-order: useful for evaluation)
Level:  + * - 1 3 * 9 5 7    (level-order: useful for printing tree)

COMP2521(23T1) ♢ Trees, search trees ♢ [27/45]
❖ ... Tree Traversal

Traversals for the following tree:

[Diagram:Pics/bigtree.png]


NLR (preorder):   20   10   5   2   14   12   17   30   24   29   32   31

LNR (inorder):   2   5   10   12   14   17   20   24   29   30   31   32

LRN (postorder):   2   5   12   17   14   10   29   24   31   32   30   20

COMP2521(23T1) ♢ Trees, search trees ♢ [28/45]
❖ ... Tree Traversal

Pseudocode for NLR traversal

showBSTreePreorder(t):
|  Input tree t
|
|  if t is not empty then
|  |  print data(t)
|  |  showBSTreePreorder(left(t))
|  |  showBSTreePreorder(right(t))
|  end if

Recursive algorithm is very simple.

Iterative version less obvious ... requires a Stack.

COMP2521(23T1) ♢ Trees, search trees ♢ [29/45]
❖ ... Tree Traversal

Pseudocode for NLR traversal (non-recursive)

showBSTreePreorder(t):
|  Input tree t
|
|  push t onto new stack S
|  while stack is not empty do
|  |  t=pop(S)
|  |  print data(t)
|  |  if right(t) is not empty then
|  |     push right(t) onto S
|  |  end if
|  |  if left(t) is not empty then
|  |     push left(t) onto S
|  |  end if
|  end while

COMP2521(23T1) ♢ Trees, search trees ♢ [30/45]
❖ Joining Two Trees

An auxiliary tree operation …

Tree operations so far have involved just one tree.

An operation on two trees:   t = TreeJoin(t1,t2)

COMP2521(23T1) ♢ Trees, search trees ♢ [31/45]
❖ ... Joining Two Trees

Method for performing tree-join:

Advantage: doesn't increase height of tree significantly

x ≤ height(t) ≤ x+1, where x = max(height(t1),height(t2))

Variation: choose deeper subtree; take root from there.

COMP2521(23T1) ♢ Trees, search trees ♢ [32/45]
❖ ... Joining Two Trees

Joining two trees:

[Diagram:Pics/join-op.png]

 

Note: t2' may be less deep than t2

COMP2521(23T1) ♢ Trees, search trees ♢ [33/45]
❖ ... Joining Two Trees

Implementation of tree-join:

TreeJoin(t1,t2):
|  Input  trees t1,t2
|  Output t1 and t2 joined together
|
|  if t1 is empty then return t2
|  else if t2 is empty then return t1
|  else
|  |  curr=t2, parent=NULL
|  |  while left(curr) is not empty do     // find min element in t2
|  |     parent=curr
|  |     curr=left(curr)
|  |  end while
|  |  if parent≠NULL then
|  |     left(parent)=right(curr)  // unlink min element from parent
|  |     right(curr)=t2
|  |  end if
|  |  left(curr)=t1
|  |  return curr                  // curr is new root
|  end if
COMP2521(23T1) ♢ Trees, search trees ♢ [34/45]
❖ ... Joining Two Trees


Example tree join:

[Diagram:Pics/treeJoin.png]

COMP2521(23T1) ♢ Trees, search trees ♢ [35/45]
❖ Deletion from BSTs


Insertion into a binary search tree is easy.

Deletion from a binary search tree is harder.

Four cases to consider …

COMP2521(23T1) ♢ Trees, search trees ♢ [36/45]
❖ ... Deletion from BSTs

Case 2: item to be deleted is a leaf (zero subtrees)

[Diagram:Pics/del-k.png]

Just delete the item

COMP2521(23T1) ♢ Trees, search trees ♢ [37/45]
❖ ... Deletion from BSTs

Case 2: item to be deleted is a leaf (zero subtrees)

[Diagram:Pics/del1-k.png]

COMP2521(23T1) ♢ Trees, search trees ♢ [38/45]
❖ ... Deletion from BSTs

Case 3: item to be deleted has one subtree

[Diagram:Pics/del-p.png]

Replace the item by its only subtree

COMP2521(23T1) ♢ Trees, search trees ♢ [39/45]
❖ ... Deletion from BSTs

Case 3: item to be deleted has one subtree

[Diagram:Pics/del1-p.png]

COMP2521(23T1) ♢ Trees, search trees ♢ [40/45]
❖ ... Deletion from BSTs

Case 4: item to be deleted has two subtrees

[Diagram:Pics/del0-m.png]

Version 1: right child becomes new root, attach left subtree to min element of right subtree

COMP2521(23T1) ♢ Trees, search trees ♢ [41/45]
❖ ... Deletion from BSTs

Case 4: item to be deleted has two subtrees

[Diagram:Pics/del1-m.png]

COMP2521(23T1) ♢ Trees, search trees ♢ [42/45]
❖ ... Deletion from BSTs

Case 4: item to be deleted has two subtrees

[Diagram:Pics/del-m.png]

Version 2: join left and right subtree

COMP2521(23T1) ♢ Trees, search trees ♢ [43/45]
❖ ... Deletion from BSTs

Case 4: item to be deleted has two subtrees

[Diagram:Pics/del2-m.png]

COMP2521(23T1) ♢ Trees, search trees ♢ [44/45]
❖ ... Deletion from BSTs

Pseudocode (version 2):

TreeDelete(t,item):
|  Input  tree t, item
|  Output t with item deleted
|
|  if t is not empty then          // nothing to do if tree is empty
|  |  if item < data(t) then       // delete item in left subtree
|  |     left(t)=TreeDelete(left(t),item)
|  |  else if item > data(t) then  // delete item in left subtree
|  |     right(t)=TreeDelete(right(t),item)
|  |  else                         // node 't' must be deleted
|  |  |  if left(t) and right(t) are empty then 
|  |  |     new=empty tree                   // 0 children
|  |  |  else if left(t) is empty then
|  |  |     new=right(t)                     // 1 child
|  |  |  else if right(t) is empty then
|  |  |     new=left(t)                      // 1 child
|  |  |  else
|  |  |     new=TreeJoin(left(t),right(t))  // 2 children
|  |  |  end if
|  |  |  free memory allocated for t
|  |  |  t=new
|  |  end if
|  end if
|  return t
COMP2521(23T1) ♢ Trees, search trees ♢ [45/45]


Produced: 25 Feb 2023