| Summary: |
A tree is a hierarchical structure with its data arranged according to some ordering property.
Searching linearly in a list is O(n) and can be expensive for large data. However a binary search for sorted collection is of the order O(log2 n) providing improved performance for large collections of data, for example finding an item from billion items arranged in sorted order requires at most only 30 comparisons. Similarly, binary search tree (BST) organizes the data such that most operations are O(log2 n) on average.
This week we will:
• Introduce the Tree ADT and its usefulness for solving problems
• Learn about tree insertion and deletion strategies
• Learn about tree traversals
• Understand the difference between binary trees, binary search trees and general trees
Trees can have different types:
• General trees – each node can have any number of children
• Binary trees – each node has at most two children
• Binary search tree (BST)– the values are ordered |
| Creators: |
|
| Divisions: |
Academic > School of Computing, Engineering and Built Environment > Department of Computing |
| Copyright holder: |
Copyright © Glasgow Caledonian University |
| Viewing permissions: |
World |
| Depositing User: |
|
| Date Deposited: |
29 Jun 2018 11:12 |
| Last Modified: |
13 Feb 2020 12:42 |
| URI: |
https://edshare.gcu.ac.uk/id/eprint/3806 |
Loading previews...
