Computer Science Data Structures
2019-2020
The computer science data structures class offered at Seven Lakes High School is a college-level sophomore year Data Structures and Algorithms based on Labs, Projects, and Tests.
Course Curriculum
Projects
The first project we worked on was an individual UNO project using java graphics tool kits. We then worked on a complex group project in recreating the popular board game "Seven Wonders" graphically using Java as well. Finally, we ended the year replicating "Power Grid" which was even more advanced than Seven Wonders both functionally and creatively.
Red Black Tree
A red-black tree is a kind of self-balancing binary search tree. Each node stores an extra bit representing "color" ("red" or "black"), used to ensure that the tree remains balanced during insertions and deletions.
When the tree is modified, the new tree is rearranged and "repainted" to restore the coloring properties that constrain how unbalanced the tree can become in the worst case. The properties are designed such that this rearranging and recoloring can be performed efficiently.
The re-balancing is not perfect, but guarantees searching in O(log(n)) time, where n is the number of nodes of the tree.
Binary Search Tree
A binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree whose internal nodes each store a key greater than all the keys in the node's left subtree and less than those in its right subtree.
This data structure does not guarantee to search in O(log(n)) time, where n is the number of nodes of the tree.
