m22 Flashcards
BST structure, recursive definition
```java
public class Node {
int key;
Node left, right;
public Node(int item) {
key = item;
left = right = null;
} } ~~~
Recursive Insert
public Node insert(Node node, int key) {
if (node == null) {
return new Node(key);
}
if (key < node.key) {
node.left = insert(node.left, key);
} else if (key > node.key) {
node.right = insert(node.right, key);
}
return node;
}
Recursive search
public boolean search(Node root, int key) {
if (root == null) {
return false;
}
if (root.key == key) {
return true;
}
return key < root.key ? search(root.left, key) : search(root.right, key);
}
Generic BST class
public class BST {
private Node root;
private static class Node {
int root;
Node left, right;
public Node(int root) {
this.root = root;
left = right = null;
}
}
Inorder traversal of BST
void inorder() {
inorder(root);
}
void inorder(Node root) {
if (root != null) {
inorder(root.left);
System.out.println(root.key);
inorder(root.right);
}
}
Algorithm + code for BST delete
void deleteKey(int key) {
root = deleteRec(root, key);
}
Node deleteRec(Node root, int key) {
if (root == null) return root;
if (key < root.key)
root.left = deleteRec(root.left, key);
else if (key > root.key)
root.right = deleteRec(root.right, key);
else {
if (root.left == null)
return root.right;
else if (root.right == null)
return root.left;
root.key = minValue(root.right);
root.right = deleteRec(root.right, root.key);
}
return root;
} int minValue(Node root) {
int minv = root.key;
while (root.left != null) {
minv = root.left.key;
root = root.left;
}
return minv;
}
What to do when keys are not unique? (maintain, at every node, a list of all objects with same key)
If keys are not unique, you can store a list of objects at each node.
This will mean changing the structure of your node to hold a list instead of a single value.
Big O worst case analysis for search, insert, delete
The worst case for these operations in a binary search tree is O(n),
where n is the number of nodes in the tree.
This would occur in the case where the tree is a straight line (each node only has a right child or only
has a left child).
traversals: inorder, preorder, postorder
void inorder(Node root) {
if (root != null) {
inorder(root.left);
System.out.println(root.key);
inorder(root.right);
}
}
void preorder(Node root) {
if (root != null) {
System.out.println(root.key);
preorder(root.left);
preorder(root.right);
}
}
void postorder(Node root) {
if (root != null) {
postorder(root.left);
postorder(root.right);
System.out.println(root.key);
}
}
What is a balanced tree?
A balanced tree is a tree structure in which the left and right subtrees of any node differ in height by
no more than one. In other words, elements are evenly distributed across the tree.
Balanced trees are optimized to ensure that operations like search, insert, and delete take the least time
possible.
Red-Black Tree Properties
A Red-Black Tree is a self-balancing binary search tree, and it follows these properties:
- Every node is either red or black.
- The root node is always black.
- All leaves (NULL or NIL nodes) are black.
- If a node is red, then both its children are black (no two consecutive Red nodes).
- For each node, any simple path from this node to any of its descendant leaves has the same number
of black nodes.
These properties ensure that the tree remains approximately balanced, resulting in O(log n) search times.
Rotations
Rotations are operations in balanced BSTs that help maintain their balance while performing insertions
and deletions. There are two types of rotations: left rotation and right rotation.
- Left Rotation: Suppose node x is a node in the tree with a right child, y. A left rotation on x moves y up
to x’s position, moves x down to y’s left child position, and moves y’s original left child to be x’s right child. - Right Rotation: It’s the reverse of the left rotation. Suppose y is a node in the tree with a left child x.
A right rotation on y moves x up to y’s position, moves y down to x’s right child position,
and moves x’s original right child to be y’s left child.
Time complexity of insert, delete, and search in a Red-Black Tree
The search operation in a Red-Black Tree behaves exactly as it does in a binary search tree,
and thus its time complexity is O(log n) in the worst-case scenario.
The insert and delete operations in a Red-Black Tree are more complicated because they may
require rebalancing of the tree and recoloring of the nodes.
Despite this, these operations can be done in O(log n) time in the worst case.
The reason is that the tree remains balanced, i.e., the height of the tree remains proportional to
the logarithm of the number of nodes, and the operations require time proportional to the height of the tree.
Expression tree evaluation: Expression trees can be evaluated using a postorder traversal.
You traverse the tree, when you encounter an operator, you apply it to the results of evaluating its
two subtrees. If you encounter a leaf node (an operand), you simply return its value.
public int evaluate(Node root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return toInt(root.value);
}
int leftSum = evaluate(root.left);
int rightSum = evaluate(root.right);
if (root.value.equals("+")) {
return leftSum + rightSum;
}
if (root.value.equals("-")) {
return leftSum - rightSum;
}
if (root.value.equals("*")) {
return leftSum * rightSum;
}
return leftSum / rightSum; // assuming the root.value is "/" }
Infix, prefix, postfix
These are all notations for writing arithmetic expressions that
eliminate the need for parentheses to indicate the order of operations.
- Infix notation: Operators are written between the operands. Ex:
2 + 3. - Prefix notation (Polish notation): Operators are written before the operands. Ex:
+ 2 3. - Postfix notation (Reverse Polish notation): Operators are written after the operands. Ex:
2 3 +.
