3. Trees 1
Express hierarchical structure.
3. 1. Heap
- It should be a complete binary tree.
- Heap Property must be satisfied. (Max Heap or Min Heap)
Heap can be expressed in a one-dimensional array. A[1…n]
- Root Node = A[1]
- Parent of A [i] = A [i / 2]
- Left child of A [i] = A [2i]
- Right child of A [i] = A [2i + 1]
3. 2. Max Heap / Min Heap
- Max Heap — Parent is greater than or equal to child.
- Min Heap — The parent is less than or equal to the child.
Heapify — O(logN)
If the left sub tree and the right sub tree are both Heap and the Root Node does not satisfy the Heap, the operation method that makes the entire tree Heap.
- If the larger of the two children is greater than or equal to the Exchange,
func maxHeapify(_ i:Int,_ n:Int){
var left : Int? = nil
var right : Int? = nil
var k = 0
if i*2 <= n {
left = data[i*2]
}
if i*2+1 <= n {
right = data[i*2+1]
}
if left == nil && right == nil {
return
}
if right == nil || left! > right! {
k = i*2
} else {
k = i*2+1
}
if data[i] >= data[k] {
return
} else {
let temp = data[i]
data[i] = data[k]
data[k] = temp
}
maxHeapify(k, n)
}3. 3. Segment Tree
When the entire section is [0, N-1], that is, when there are N spaces
Thus, leaf nodes have each interval of length 1, the parent nodes have the sum of its child’s intervals, and all the intervals must be contiguous.
The root will contain the entire section.
This is a data structure in which each node stores information about a section or its section.
Normally, a complete binary tree is used so that the entire recursive structure is repeated. If the number of values is not 2^n, fill the remaining interval with meaningless values and use it in the form of a saturated binary tree.
This ensures that when the value is N, the height of the tree is balanced to O (logN).
And as with the heap, the root index starts at 1, making it easy to access your parent, left / right child, by node numbering in the order of the level order.
That is, 1 for [0, 7], 2 for [0, 3], 3 for [4, 7], 4 for [0, 1], and leaf nodes are 8, 9, 10, …15 ,(get N ~ 2N-1). You might think of the number as an index.
3. 4. Binary Index Tree
In a binary tree, each node has a maximum of two children.
Each child node is specified whether it is the left child or the right child of the parent.
Linked Structure
Traversal of Binary Tree
- Inorder Traversal O(N):
1 traverse TL, 2 traverse Root, and 3 traverse TR.
- Preorder Traversal:
1 traverse Root, 2 traverse TL , and 3 traverse TR.
- Postorder Traversal:
1 traverse TL, 2 traverse TR, and 3 traverse Root
- Level-order Traversal:
Use queue. Visits in order of level, from left to right in the same level.
public func traverseInOrder(process: (T) -> Void) {
left?.traverseInOrder(process: process)
process(value)
right?.traverseInOrder(process: process)
}
public func traversePreOrder(process: (T) -> Void) {
process(value)
left?.traversePreOrder(process: process)
right?.traversePreOrder(process: process)
}
public func traversePostOrder(process: (T) -> Void) {
left?.traversePostOrder(process: process)
right?.traversePostOrder(process: process)
process(value)
}3. 5.Binary Search Tree (BST)
Search Structure (Dynamic Set)
Store multiple keys
Insert — Insert new key
Search — key navigation
Delete — Delete key
An implementation of Search Structure in the form of a Tree. Generally, search, insert, and delete operations have time complexity proportional to the height of the tree.
A tree that satisfies the following three conditions is called an advanced search tree.
- Binary tree
- Store one key on each node
- For each node v, the keys in the left subtree of that node are less than or equal to key [v], and the value in the right subtree is equal to or greater than.
- Search — O(h)
public func search(x: T) -> BinarySearchTree? {
switch self {
case .Empty:
return nil
case .Leaf(let y):
return (x == y) ? self : nil
case let .Node(left, y, right):
if x < y {
return left.search(x)
} else if y < x {
return right.search(x)
} else {
return self
}
}
}- Successor — O(H)
A value with the size immediately following node x
Case 1: If the right subtree of node x exists, the minimum value of the right subtree
Case 2: If there is no right subtree, the value of the node y whose maximum value of the left subtree is x. (A node that becomes the first child of someone else to go up to the root along the parent)
Case 3: There is no successor if node y does not exist. (That is, x is the maximum value)
public func successor() -> BinarySearchTree<T>? {
if let right = right {
return right.minimum()
} else {
var node = self
while let parent = node.parent {
if parent.value > value { return parent }
node = parent
}
return nil
}
}- Insert — O(H)
When adding a new node, the position of existing nodes is not changed.
It is implemented using two pointers, X and Y. Y is always positioned after one of the X’s so that the current position can be remembered even if X becomes Nil.
public func insert(newValue: T) -> BinarySearchTree {
switch self {
case .Empty:
return .Leaf(newValue)
case .Leaf(let value):
if newValue < value {
return .Node(.Leaf(newValue), value, .Empty)
} else {
return .Node(.Empty, value, .Leaf(newValue))
}
case .Node(let left, let value, let right):
if newValue < value {
return .Node(left.insert(newValue), value, right)
} else {
return .Node(left, value, right.insert(newValue))
}
}
}- Delete — O(H)
Case 1: If there are no child nodes, just delete them.
Case 2: If there is one child, it links its child node to its original location.
Case 3:
If there are two children, leave only their own node and delete only their own data. Then, move the data of the Successor node to original node. Since the successor node does not have the left child and has 0 or 1 child, delete the successor node by Case 1 or Case 2 method.
private func reconnectParentTo(node: BinarySearchTree?) {
if let parent = parent {
if isLeftChild {
parent.left = node
} else {
parent.right = node
}
}
node?.parent = parent
}public func minimum() -> BinarySearchTree {
var node = self
while let next = node.left {
node = next
}
return node
}
public func maximum() -> BinarySearchTree {
var node = self
while let next = node.right {
node = next
}
return node
}@discardableResult public func remove() -> BinarySearchTree? {
let replacement: BinarySearchTree?
// Replacement for current node can be either biggest one on the left or
// smallest one on the right, whichever is not nil
if let right = right {
replacement = right.minimum()
} else if let left = left {
replacement = left.maximum()
} else {
replacement = nil
}
replacement?.remove()
// Place the replacement on current node's position
replacement?.right = right
replacement?.left = left
right?.parent = replacement
left?.parent = replacement
reconnectParentTo(node:replacement)
// The current node is no longer part of the tree, so clean it up.
parent = nil
left = nil
right = nil
return replacement
}
3. 6. Red Black Tree — O(logN)
One of Binary Search Tree.
A tree that balances the tree‘s height so that the height maintains logN.
Insert and delete operations O (logN) even in the worst case.
- Each node stores the address of one Key, Left, Right, and P
- If there is no child node, there is a special node called Nil node.
- Therefore, every leaf node is a Nil node
- It is assumed that the parent of the root is also a Nil node
- Nodes are classified as internal nodes and Nil nodes
Red-Black Tree is a Binary Search Tree that satisfies the following conditions.
- Each node is red or black.
- The root node is black.
- All leaf nodes (Nil nodes) are black.
- The child nodes of the red node are all black. (That is, red nodes do not appear consecutively)
- For all nodes, there are the same number of black nodes in all paths from that node to the descendant leaf node.
The black height (BH) of the node with the height H is BH ≥ H/2
An arbitrary Subtree rooted at node X contains at least 2 ^ BH (x) -1 internal nodes
The height of the red black tree having N internal nodes is 2 log (N + 1) or less.
Search : Same as Binary Search Tree
Left and Right Rotation- O(1)
Insert
- Insert nodes as in normal BST.
- Let the new node z be the red node.
- Call RB-Insert-Fixup.
RB-Insert-Fixup
If the z node is the root node, change it to black.
If the parent node of the z node is red, follow the rules below.
- case 1: When P [z] is the left child of P [P [z]], && z’s uncle (grandfather’s right child) is red -> change parents and uncle to black, change grandfather to red, .
- case 2: When P [z] is the left child of P [P [z]] && If my uncle is Black && z is the right child -> Left-rotate P [z] and set P [z] to z -> Run case 3.
- case 3: When P [z] is the left child of P [P [z]] && If my uncle is Black && z is the left child -> Change P [z] to black, and P [P [z]] to red -> Right-rotate P [P [z]]
- case 4~6 : same as case 1~3 with changing left to right
Delete
- Delete as usual binary search.
- If the deleted node y was red, then exit.
- Call RB-DELETE-Fixup when y is black.
3. 7. Treap
Like Red-Black and AVL Trees, Treap is a Balanced Binary Search Tree, but not guaranteed to have height as O(Log n). The idea is to use Randomization and Binary Heap property to maintain balance with high probability. The expected time complexity of search, insert and delete is O(Log n).
Every node of Treap maintains two values.
1) Key Follows standard BST ordering (left is smaller and right is greater)
2) Priority Randomly assigned value that follows Max-Heap property.
Search
Perform standard BST Search to find x.
Insert
1)Create new node with key equals to x and value equals to a random value.
2) Perform standard BST insert.
3) Use rotations to make sure that inserted node’s priority follows max heap property.
Delete
1) If node to be deleted is a leaf, delete it.
2) Else replace node’s priority with minus infinite ( -INF ), and do appropriate rotations to bring the node down to a leaf.
