Trees Flashcards
What is a binary search tree?
A binary search tree (BST) is a binary tree where each node has a Comparable key (and an associated value) and satisfies the restriction that the key in any node is larger than the keys in all nodes in that node’s left subtree and smaller than the keys in all nodes in that node’s right subtree.
What’s a red-black tree?
A red-black tree is a binary search tree with one extra attribute for each node: the colour, which is either red or black.
What are the properties of a red-black tree?
- The root is black
- Every node is either red or black.
- Every leaf (NULL) is black.
- If a node is red, then both its children are black.
- Every simple path from a node to a descendant leaf contains the same number of black nodes.
- The height is never greater than 2 log2(n), where n is the number of nodes.
What are the steps of inserting into a red-black tree?
- Insert as you would into a BST, coloring the node red.
- If the parent of the node you just inserted was red, you have a double-red problem which you must correct.
- Color the root node black.
What are the 4 types of restructuring?
Right, left, right-left, left-right.
Code for adding a node into a red-black tree.
Code for removing node in a red-black tree.
Code for adjusting for insertion of a red-black tree.
Code for adjusting for removal of node in a red-black tree.
What is a heap?
A heap is a specialized tree-based ADT that satisfies the heap property –> if A is a parent of node B, then the key of A is order with respect to the key of node B with the same ordering applying across the heap.
What is a min heap?
In a min heap, the keys of parent nodes are less than or equal to those of the children and the lowest key is in the root node.
What is a max heap?
In a max heap, the keys of parent nodes are always greater than or equal to those of the children and the highest key is in the root node.
What is a binary heap?
A binary heap is a heap data structure created using a binary tree. It can be seens as a binary tree with two additional constraints:
- Shape property –> A binary heap is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.
- Heap property –> All nodes are either greater than or equal to or less than or equal to each of its children, according to a comparisonpredicate defined for the heap.
How are heaps normally implemented?
Heaps are usually implemented in an array (fixed size or dynamic array), and do not require pointers between elements. After an element is inserted into or deleted from a heap, the heap property is violated and the heap must be balanced by internal operations.
