Vocab Flashcards
Preorder (Depth-first)
visit a node and then visit the subtrees rooted at each of its children recursively. a.k.a. Depth First traversal.
Postorder
recursively visit the subtrees rooted at each child of a node and then visit the node.
Breadth - first
visit all nodes at depth d before visiting nodes at depth d + 1.
Inorder
Definition: limited to binary tree - recursively visit left child, root, right child
Binary Tree
An ordered tree wherein every node has at most 2 children, so either child is either left or right
Binary Search Tree
Each node stores a key-value pair. For a given parent, the left child (and the entirety of its subtree) is logically less, and the right child (and the entirety of its subtree) is logically more.
Trie
Tree nodes consist of an array of R == alphabet size slots, and a value. Mid-key node will hold link to next node in appropriate alphabet slot, and a null value, final key node will not hold no link, and the corresponding value.
Heap
Complete binary tree wherein the key of every node is greater than or equal to the key of its children (Heap-Order Property)
2-3 Tree
Tree consisting of 2-nodes (one key, left-link and right-link), and 3-nodes (two keys, left-link, middle-link, right-link).
Red-Black Tree
Definition: Binary search tree implementation, strictly consisting of 2-nodes, that conceptually mirrors 2-3 trees (red links represent horizontal, as opposed to vertical links; ie 2 red-linked 2-nodes = 3-node). Red links must lean to the left, can’t have consecutive red links.
Features/Advantages: Insertion guarantees perfect black balance, and with it near O(logn) search. Nearly as effective as 2-3 Tree, much easier to implement.
B-Tree
Tree wherein every entry e with key k in an internal node has a link to a child node which is the root of a subtree wherein all keys >= k and < the next entry’s key in the same node as e
Root
First node in a tree, no parent node, only children.
Acyclic
There is exactly one path connecting any two nodes in a tree
Path
A sequence of nodes such that any two consecutive nodes in the sequence from an edge
Ancestor
A node reachable by repeatedly proceeding from child to parent
Descendent
A node reachable by repeatedly proceeding from parent to child
Depth
The number of nodes on the path from the node to the root, including the node itself
Height
Height of node V is: if V is a leaf, height == 0, else height = maximum height of its children + 1
Internal
A node with at least one child
Leaf/external
A node with no children
Edge
A pair of nodes, U, V, such that one is a the parent of the other
Ordered
A tree is ordered if there is a meaningful linear order among the children of every node
Isomorphic
Two ordered trees T’ and T’’ are Isomorphic if the following recursive definition is true: Both have no children OR the roots of T’ and T’’ have the same number of children/subtrees (k), and for i = 0,…,k the ith such subtree of T’ has the same number of child subtrees as the ith such subtree of T’’
Proper binary tree
Every node has either 0 or 2 children
Complete Binary Tree
Every level, except the last, must be completely filled and all nodes are as far left as possible
Trie node
node consisting of an array of links corresponding to alphabet of key set, value
2 - Node
Node with one key, two child links (left,right)
3 - Node
Node with two keys, three child links (left, middle, right)
4 - Node
Node with three keys, four child links(Left, left-middle, right-middle, right). Only temporary in 2-3 Tree; meant to be converted into 3, 2 Nodes
Rotation
Step to balance left-leaning Red-Black Tree with right -leaning red link
Color flip
Step to balance left-leaning Red-Black Tree with two red links stemming from a single parent.
Perfect Balance
condition of a 2-3 tree and Red-Black tree that all null links must be the same distance (have the same depth) to the roots
