> See also: > - [[Data Structures]] # Tree Data Structures --- **Data Structure Notes:** ```dataview LIST FROM #Data-Structures ``` --- In a **complete binary tree**, nodes are filled in from the left to right. - This causes all levels of the tree to be filled, except for the lowest level. - Allows for easy indexing of nodes; can sometimes be stored as a simple array. ## Properties of Tree Structures ![[Pasted image 20240302213707.png|400]] - The **root** is the starting point of any tree data structure - A **node** is an sub-element which makes up the tree - The **key** is the value(s) within a given node - The distance from the - A subtree is any node of the tree along with its descendant(s) - The *depth of a node* is the total # of edges (root depth is 0) - The *depth of a tree* is the ### Node Relationships ![[Pasted image 20240305074603.png|300]] ## Tree Traversal > See also: [[Recursion]] While [[Linear Data Structures]] only have one logical way of traversing them, tree data structures can be **traversed** in several different ways. There are three primary ways to traverse a tree data structure: - **In-Order:** Performs a recursive call on the left child, then the parent node's value, and finally a recursive call on the right child. - In a balanced BST, this will print out the elements in the sorted order. --- - **Pre-Order:** Prints the current (parent) node’s value before recursively calling the left and right children, respectively. --- - **Post-Order:** 1. Prints recursive call on left and right children, respectively, before printing the 2. parent node’s value. ### Querying `Successor(S,x)` - next larger value `Predecessor(S,x)` - past smaller value ## Binary Search Trees ![[Pasted image 20240302231044.png|400]] ### Operations #### Searching #### Insertion #### Deletion Probabilistic Data Structures: - Treap - Skip List - Bloom Filter ### Self-Balancing Trees