Data Structure - Tree

Tree

A tree is a data structure composed of nodes.

• Each tree has a root node -> Actually a root node isn't necessary in graph theory, but it's usually how we use trees in programming.
• Root node has zero or more child nodes. Each child node has zero or more child nodes, and so on
• The tree cannot contain cytcles. The nodes may or may not be in a particular order, they could ahve any data type as values, and they may or may not have links back to their parent nodes.

Binary Tree vs. Binary search Tree

• A binary search tree is a binary tree in which every node fits a specific ordering property ->All left descendents <= n < all right descendents. This must be true for each node n
• The definition of a binary search tree can vary slightly with respect to equality. Under some definitions, the tree cannot have duplicate values. In others, the duplicate values will be on the right or can be on either side. All are valid definitions.

Balanced vs. Unbalanced

a "balanced" tree really means something more like "not terribly imbalanced".

Complete Binary Trees
A complete binary tree is a binary tree in which every level of the tree is fully filled, except for perhaps the last level(leaf node). To the extent that the last level is filled it is filled left to right

Full binary Trees

A full binary tree is a binary tree in which every node has either zero or two children. That is, no nodes have only one child.

Perfect Binary Trees

A perfect binary tree is one that is both full and complete. All leaf nodes will be at the same level, and this level has the maximum number of nodes -> it is rare in real life, as a perfect tree must have exactly 2ᵏ-1 nodes(k is the number of levels)

Binary Tree Traversal

• In-Order Traversal this means to "visit"(often, print) the left branch, then the current node, and finally, the right branch. When performed on a binary search tree, it visits the nodes in ascending order
• Pre-Order Traversal this visits the current node before its childnodes. In a pre-order traversal, the root is always the first node visited.
• Post-Order traversal Post-Order traversal visits the current node after its child nodes. The root is always the last node visited.

Binary Heaps

there are min-heaps and max-heaps. Max-heaps are essentially equivalent, but the elements are in descending order rather than ascending order.

A min-heap is a complete binary tree(that is, totally filled other than the rightmost elements on the last level) where each node is smaller than its children. Therefore the foot is the minimum element in the tree.

two key oerations on a min-heap -> insert and extract_min

1. insert when we insert into a min-heap, we always start by inserting the element at the bottom. We insert at the rightmost spot so as to maintain the complete tree property. Then we "fix" the tree by swapping the new element with its parent, until we find an appropriate spot for the element. We essentially bubble up the minimum element. This takes O(log n) time, where n is the number of nodes in the heap.
2. Extract Minimum Element First we remove the minimum element and swap it with the last element in the heap(the last element -> the bottommost, rightmost element). -> (Remove the root (minimum element), and move the last element to the root position.) Then we bubble down this element, swapping it with one of its children until the min-heap property is restored. Do we swap it with the left child or the right child -> that depends on their values. There's no inhent ordering between the left and right element, but you'll need to take the smaller one in order to maintain the min-heap ordering. This algorithm will also take O(log n) time.

Tries (Prefix Trees)

• A tries is a variant of an n-ary tree in which characters are stored at each node. Each path down the tree may represent a word. The *nodes(sometimes called "null nodes") are often used to indicate complete words. -> For example, the fact that there is a *node under MANY indicates that MANY is a complete word. The existence of the MA path indicates there are words that start with MA. The actual implementation of these * nodes might be a special type of child(such as a Terminating TrieNode, which inherits from TrieNode).
• Very commonly, a trie is used to store the entire (English) language for quick prefix lookups. While a hash table can quickly look up whether a string is a valid word, it cannot tell us if a string is a prefix of any valid words. A trie can do this very quickly