Description: [Binary Search Tree Representation (Nodes Manipulation)].In this first video of Trees, we will be introducing the manipulation of nodes as a way to obtain a Tree that can be used to efficiently store data and perform operations that are quick when compared to other ADTs.
ACM CCECC
[Binary Trees and Their Application]
DS-27. Demonstrate how concepts from graphs and trees appear in data structures, algorithms, proof techniques (structural induction), and counting.
AP CS A
N/A
CS2
N/A
Description: Now that we know how to implement a Tree, it is essential to know how to traverse through it in order to implement more useful methods. The three traversing methods that we will be reviewing will be inOrder(), preOrder(), and postOrder().
ACM CCECC
[Implementation of a Binary Tree]
DS-23. Demonstrate different traversal methods for trees and graphs, including pre-, post-, and in-order traversal of trees.
AP CS A
N/A
CS2
N/A
Description: Now that we know how to implement a Tree and also how to traverse it, it is time to start implementing methods that will be useful to demonstrate the characteristics of the show ADT. On this occasion, the two methods that students will implement will be getHeight() and getSize(), which will demonstrate that the height and size of a Tree are two different concepts.
ACM CCECC
[Binary Trees and Their Application]
DS-24. Solve a variety of real-world problems in computer science using appropriate forms of graphs and trees, such as representing a network topology or the organization of a hierarchical file system.
AP CS A
N/A
CS2
N/A
Description: The last method that we will be implementing for a Tree will be countParents(). For that method, the traversing techiques that were showcased in the second video of this section will be essential for the correct implementation of the algorithm to count parents in a Tree.
ACM CCECC
[Binary Trees and Their Application]
DS-24. Solve a variety of real-world problems in computer science using appropriate forms of graphs and trees, such as representing a network topology or the organization of a hierarchical file system.
AP CS A
N/A
CS2
N/A
Description: Now that we have analyzed and implemented a Tree, it is time to start knowing what an AVL Tree can do. In this video, students will be able to implement and perform operations for the mentioned ADT.
ACM CCECC
[Binary Search Trees and Implementation]
DS-28. Describe binary search trees and AVL trees.
[AVL Trees and Implementation]
DS-25. Implement and use balanced trees and B-trees.
AP CS A
N/A
CS2
N/A
Description: One of the main characteristics of an AVL Tree lies in its capability to rotate its leaves to balance the data structure. In this video, students will be able to implement a single rotation to the left.
ACM CCECC
[Binary Search Trees and Implementation]
DS-28. Describe binary search trees and AVL trees.
[AVL Trees and Implementation]
DS-25. Implement and use balanced trees and B-trees.
AP CS A
N/A
CS2
N/A
Description: After having seen how to go from a Binary Search to an AVL Tree, how to implement one, its operations, and how to rotate leaves to balance the data structure, the last rotation we will be reviewing will be a double right-left rotation, which is essential to correctly implement an AVL Tree.
ACM CCECC
[Binary Search Trees and Implementation]
DS-28. Describe binary search trees and AVL trees.
[AVL Trees and Implementation]
DS-25. Implement and use balanced trees and B-trees.
AP CS A
N/A
CS2
N/A