CPT 102_ LEC 20

1. Tree

1.1. Introduction to Trees

1.1.1. Basic

• Used for non-linear data structures
  • Family trees
  • Organisational charts
• Trees offer an alternative
  • Representation
  • Implementation strategy
  • Set of algorithms

1.1.2. Binary Tree

• A binary tree
  • empty
  • a root node together with two binary trees
    • left subtree
    • right subtree

1.1.3. What is a tree exactly?

• Models the parent/child relationship between different elements
  • Each child only has one parent
  • Each parent has ? children
• From mathematics
  • A “Directed Acyclic Graph”【 Directed acyclic graph 】 (DAG)
  • At most one path from any one node to any other node

1.1.4. Some Concepts

• Level                    --> Equivalent to the “row” that a value is in
• Depth                   --> The number of levels in the tree
• Leaf Nodes          --> A node with no children
• Non-leaf Nodes
• Balanced             --> All leaf nodes are on levels n and (n+1), for some value of n 

1.1.5. How many types of tree are there?

• Examples
  • Red-Black Tree
  • AVL Tree
  • ...
• Different types are used for different things
  • To improve speed
  • To improve the use of available memory
  • To suit particular problems

1.1.6. Trees and Recursion

• Recursively defined data structure
• Recursion is very natural for trees – important!
• Recursion tree
• If you don’t use recursion then use iteration

1.1.7. What is a tree useful for?

• Artificial Intelligence
  • planning
  • navigating
  • games
• Representing things
  • Simple file systems
  • Class inheritance and composition
  • Classification
  • HTML pages
  • Parse trees for languages
  • Essential in compilers like Java, C# etc
  • 3D graphics (e.g. BSP trees)

1.1.8. Some Example

• Tic Tac Toe【 Jingzi chess 】
• N-Queen【N Queen 】
• Decision Tree

1.1.9. Conclusion

• Data representation of tree is important
• Efficiently adding, accessing and removing data from a tree is important
• Trees can be made efficient and help you organise data
• Trees are useful in
  • Computer graphics
  • Artificial Intelligence
  • Databases