## Lecture 09. Advanced Trees
- Binary Search Tree
- Self-balanced Search Tree
- AVL Tree
- Red-Black Tree
- Segment Tree
- Interval Tree
- Range Tree
- Binary Indexed (Fenwick) Tree
---
### Binary Search Tree
BST is a binary tree $T$, in which **each** node $p$ storing a key $k$, such that:
- Keys stored in the **left** subtree of $p$ are **less** than $k$
- Keys stored in the **right** subtree of $p$ are **greater** than $k$
<img src="https://cdn.ucode.vn/uploads/1/upload/WYQiKqwu.png" width="60%" />
---
#### Binary Search Tree
- An **inorder** traversal of a binary search tree visits positions in **increasing** order of their keys.
<img src="https://cdn.ucode.vn/uploads/1/upload/eXwRUOrG.png"/>
---
#### BST Operations
- Traversal
- Find min/max value
- Search for a key
- Insert a new key
- Delete a key
```python=
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
```
---
#### BST Operations
- Traversal
<img src="https://cdn.ucode.vn/uploads/1/upload/FgVHSrBR.png" class="element-left content-img" />
```python=
def inorder(root):
if root is not None:
inorder(root.left)
print(str(root.key) + "->", end=' ')
inorder(root.right)
# 1-> 3-> 4-> 6-> 7-> 8-> 10-> 14->
```
---
#### BST Operations
- Min value
```python=
def min_value_node(root):
current = root
while(current.left is not None):
current = current.left
return current
```
---
#### BST Operations
- Search for a key
```python=
def search(root, key):
if not root:
return None
if root.key == key:
return key
if key < root.key:
return search(root.left, key)
return search(root.right, key)
```
---
#### BST Operations
- Insert a new key
<img src="https://cdn.ucode.vn/uploads/1/upload/dcqcBfiX.png" class="element-left content-img" />
---
#### BST Operations
- Insert a new key
```python=
def insert(root, key):
if root is None: # new tree
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
else:
root.right = insert(root.right, key)
return root
```
---
#### BST Operations
- Delete a key:
- The node has no children
- The node has one child
- The node has two children
---
#### BST Operations
- Delete a key: Node $A$ has no children
<img src="https://cdn.ucode.vn/uploads/1/upload/afXJIghn.png" class="element-left content-img" />
---
#### BST Operations
- Delete a key: The node $6$ has one child
<img src="https://cdn.ucode.vn/uploads/1/upload/DsXwWMrr.png" class="element-left content-img" />
---
#### BST Operations
- Delete a key: The node $9$ has two children
- Find the next smalless descedent of node $9$ from the right sub-tree
<img src="https://cdn.ucode.vn/uploads/1/upload/ZSCYNXqK.png" class="element-left content-img" />
---
#### BST Operations
- Insert a new key
```python=
def deleteNode(root, key):
if root is None: return root
if key < root.key:
root.left = deleteNode(root.left, key)
elif(key > root.key):
root.right = deleteNode(root.right, key)
else:
if root.left is None: # only right child
temp = root.right
root = None
return temp
elif root.right is None: # only left child
temp = root.left
root = None
return temp
# If the node has two children,
temp = min_value_node(root.right)
root.key = temp.key
root.right = deleteNode(root.right, temp.key)
return root
```
---
#### BST Operations: complexity
- $h$: the height of the BST
- Search, insert, delete, min, max: $O(h)$
- $\rightarrow$ optimize $h$?
---
### Self-balanced Search Tree
- Maintain the tree height to a minimum
- Ensuring that its operations will maintain a worst-case time complexity of $O(\log n)$.
---
### Self-balanced Search Tree
- The **balance factor** $k$ of a BST is the difference between heights of left and right subtrees $\rightarrow$ **minimize** $k$
<img src="https://cdn.ucode.vn/uploads/1/upload/kXtqdBCA.png" width="60%" />
---
### Types of Self-balanced Search Tree
- 2–3 tree
- AA tree
- **AVL tree**
- B-tree
- **Red–black tree**
- Scapegoat tree
- Splay tree
- Tango tree
- Treap
- Weight-balanced tree
Note:
- B-tree: generalizes the binary search tree, allowing for nodes with more than two children
---
#### Self-balanced Search Tree
Perform **rotations** after the execution of an insert and delete operations:
- Left rotation
- Right rotation
---
#### Self-balanced Search Tree
Left rotation:
<img src="https://cdn.ucode.vn/uploads/1/upload/dgWlpkLN.png" class="element-left content-img" />
---
#### Self-balanced Search Tree
Right rotation:
<img src="https://cdn.ucode.vn/uploads/1/upload/CSYzrTGZ.png" class="element-left content-img" />
---
### AVL Tree
- AVL (Adelso-Velskii and Landis - two Soviet inventors) tree,
- It's a self-balancing binary search tree and was the first (1962) such data structure to be invented
- For all nodes: the difference between left subtree and right subtree height is at most one (balance factor $k$ is -1, 0 or 1)
---
#### AVL Tree Operations
- Search: same as BST
- Find min/max: same as BST
- Traversal: same as BST
- Insert: use rotations to maintain self-balanced
- Delete: use rotations to maintain self-balanced
---
#### AVL Tree node
```python=
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1
```
---
#### AVL Tree Operations
Four rotations to rebalance when $|k|>1$:
- Single rotations:
- Left rotation
- Right rotation
- Double rotations:
- Left-Right rotation
- Right-Left rotation
---
#### AVL Tree Operations
Left rotation:
<img src="https://cdn.ucode.vn/uploads/1/upload/xCFJUAhK.png" class="element-left content-img" />
<img src="https://cdn.ucode.vn/uploads/1/upload/uXVmhojK.png" class="element-left content-img" />
---
#### AVL Tree Operations
Left rotation:
<img src="https://cdn.ucode.vn/uploads/1/upload/eCdQziTL.png" class="element-left content-img" />
<img src="https://cdn.ucode.vn/uploads/1/upload/swcYmkmq.png" class="element-left content-img" />
---
#### AVL Tree Operations
Left rotation:
<img src="https://cdn.ucode.vn/uploads/1/upload/NANHhAsg.png" class="element-left content-img" />
---
#### AVL Tree Operations
Left rotation:
```python=
def left_rotate(root):
y = root.right
tmp = y.left
y.left = root
root.right = tmp
root.height = 1 + max(root.left.height,
root.right.height)
y.height = 1 + max(y.left.height, y.right.height)
return y
```
---
#### AVL Tree Operations
Right rotation:
<img src="https://cdn.ucode.vn/uploads/1/upload/fIZBdqNA.png" class="element-left content-img" />
<img src="https://cdn.ucode.vn/uploads/1/upload/DSZFNYav.png" class="element-left content-img" />
---
#### AVL Tree Operations
Right rotation:
<img src="https://cdn.ucode.vn/uploads/1/upload/VgrxGerZ.png" class="element-left content-img" />
<img src="https://cdn.ucode.vn/uploads/1/upload/NGPReYAC.png" class="element-left content-img" />
---
#### AVL Tree Operations
Right rotation:
<img src="https://cdn.ucode.vn/uploads/1/upload/SRvtkKaN.png" class="element-left content-img" />
---
#### AVL Tree Operations
Right rotation:
```python=
def right_rotate(root):
y = root.left
tmp = y.right
y.right = root
root.left = tmp
root.height = 1 + max(root.left.height,
root.right.height)
y.height = 1 + max(y.left.height, y.right.height)
return y
```
---
#### AVL Tree Operations
Left-right rotation:
<img src="https://cdn.ucode.vn/uploads/1/upload/VzramqqO.png" class="element-left content-img" />
---
#### AVL Tree Operations
Left-right rotation:
<img src="https://cdn.ucode.vn/uploads/1/upload/cwvIYxwH.png" class="element-left content-img" />
---
#### AVL Tree Operations
Left-right rotation:
<img src="https://cdn.ucode.vn/uploads/1/upload/HPuAdhgB.png" class="element-left content-img" />
---
#### AVL Tree Operations
Left-right rotation:
```python=
root.left = left_rotate(root.left)
right_rotate(root)
```
---
#### AVL Tree Operations
Right-left rotation:
<img src="https://cdn.ucode.vn/uploads/1/upload/UvPeCfVT.png" class="element-left content-img" />
---
#### AVL Tree Operations
Right-left rotation:
<img src="https://cdn.ucode.vn/uploads/1/upload/zpYMgDRi.png" class="element-left content-img" />
---
#### AVL Tree Operations
Right-left rotation:
<img src="https://cdn.ucode.vn/uploads/1/upload/wRAVAYWx.png" class="element-left content-img" />
---
#### AVL Tree Operations
Right-left rotation:
```python=
root.right = right_rotate(root.right)
left_rotate(root)
```
---
#### AVL Tree Operations
Insert:
- 1. Inserted as a **leaf node** as normal
- 2. Update balance factor of the nodes
- 3. Rebalance the nodes if needed
---
#### AVL Tree Operations
Insert: 1. Inserted as a **leaf node**, ex: insert node with value $9$
<img src="https://cdn.ucode.vn/uploads/1/upload/teRuOIyJ.png" width="60%"/>
---
#### AVL Tree Operations
Insert: 1. Inserted as a **leaf node**, ex: insert node with value $9$
<img src="https://cdn.ucode.vn/uploads/1/upload/dZgBbMVI.png" width="60%"/>
---
#### AVL Tree Operations
Insert: 2. Update balance factor of the nodes
<img src="https://cdn.ucode.vn/uploads/1/upload/yPFQBSKM.png" width="60%"/>
---
#### AVL Tree Operations
Insert: 3. Rotate to rebalance
- If $left.height > right.height$ ($balanceFactor > 1$):
- If $newKey < leftChildKey$: **right** rotation
- Else: **left-right** rotation
<img src="https://cdn.ucode.vn/uploads/1/upload/yPFQBSKM.png" width="60%"/>
---
#### AVL Tree Operations
Insert: 3. Rotate to rebalance: $balanceFactor > 1$ and $newKey > leftChildKey$ --> **left-righ** rotation
<img src="https://cdn.ucode.vn/uploads/1/upload/ZvKmDGgd.png" class="element-left content-img" />
---
#### AVL Tree Operations
Insert: 3. Rotate to rebalance: $balanceFactor > 1$ and $newKey > leftChildKey$ --> **left-righ** rotation
<img src="https://cdn.ucode.vn/uploads/1/upload/xdCpAmNC.png" class="element-left content-img" />
---
#### AVL Tree Operations
Insert: Final tree
<img src="https://cdn.ucode.vn/uploads/1/upload/ErUHLCEP.png" class="element-left content-img" />
---
#### AVL Tree Operations
Insert: 3. Rotate to rebalance
- If $balanceFactor < -1$:
- If $newKey > leftChildKey$: **left** rotation
- Else: **right-left** rotation
---
#### AVL Tree Operations: Insert
```python=
def insert_node(root, key):
# insert the key at right position
if not root:
return Node(key)
elif key < root.key:
root.left = insert_node(root.left, key)
else:
root.right = insert_node(root.right, key)
root.height = 1 + max(root.left.height, root.right.height)
# Update the balance factor and balance the tree
balance_factor = get_balance(root)
if balance_factor > 1:
if key < root.left.key:
return right_rotate(root)
else:
root.left = left_rotate(root.left)
return right_rotate(root)
if balance_factor < -1:
if key > root.right.key:
return left_rotate(root)
else:
root.right = right_rotate(root.right)
return left_rotate(root)
return root
```
---
#### AVL Tree Operations
Delete:
- 1. Locate the $p$ with the key to be deleted
- 2. Delete the node as in normal BST
- 3. Update the balance factor of the nodes
- 4. Rebalance the nodes if needed, similar to insert algorithm
---
#### AVL Tree Operations
Delete: 1. Locate the node that needs to be deleted
<img src="https://cdn.ucode.vn/uploads/1/upload/ZCioxECU.png" class="element-left content-img" />
---
#### AVL Tree Operations
Delete: 2. Delete the node: find the inorder successor ($w$)
<img src="https://cdn.ucode.vn/uploads/1/upload/cQjItiAL.png" class="element-left content-img" />
---
#### AVL Tree Operations
Delete: 2. Delete the node: Substitute the contents of $p$ with that of $w$
<img src="https://cdn.ucode.vn/uploads/1/upload/sDhCgcbu.png" class="element-left content-img" />
---
#### AVL Tree Operations
Delete: 2. Delete the node: find the inorder successor
<img src="https://cdn.ucode.vn/uploads/1/upload/kOBuqPlF.png" class="element-left content-img" />
---
#### AVL Tree Operations
Delete: 3. Update the balance factors
<img src="https://cdn.ucode.vn/uploads/1/upload/JlThRXpB.png" class="element-left content-img" />
---
#### AVL Tree Operations
Delete: 4. Rebalance: check the balance factor of current node
- If $balanceFactor > 1$:
- If balance factor of **left** child >= 0: do **right** rotation
- Else: do **left-right** rotation
- If $balanceFactor < -1$:
- If balance factor of **right** child >= 0: do **left** rotation
- Else: do **right-left** rotation
---
#### AVL Tree Operations
Delete: 4. Rebalance: check the balance factor of current node
<img src="https://cdn.ucode.vn/uploads/1/upload/lenQldKW.png" class="element-left content-img" />
---
#### AVL Tree Operations
Delete: final tree
<img src="https://cdn.ucode.vn/uploads/1/upload/XUQbpDcr.png" class="element-left content-img" />
---
#### AVL Tree: full implementation
```python=
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1
class AVLTree:
def insert_node(self, root, key):
# Find the correct location and insert the node
if not root:
return Node(key)
elif key < root.key:
root.left = self.insert_node(root.left, key)
else:
root.right = self.insert_node(root.right, key)
root.height = 1 + max(self.get_height(root.left),
self.get_height(root.right))
# Update the balance factor and balance the tree
balance_factor = self.get_balance(root)
if balance_factor > 1:
if key < root.left.key:
return self.right_rotate(root)
else:
root.left = self.left_rotate(root.left)
return self.right_rotate(root)
if balance_factor < -1:
if key > root.right.key:
return self.left_rotate(root)
else:
root.right = self.right_rotate(root.right)
return self.left_rotate(root)
return root
# Function to delete a node
def delete_node(self, root, key):
# Find the node to be deleted and remove it
if not root:
return root
elif key < root.key:
root.left = self.delete_node(root.left, key)
elif key > root.key:
root.right = self.delete_node(root.right, key)
else:
if root.left is None:
temp = root.right
root = None
return temp
elif root.right is None:
temp = root.left
root = None
return temp
temp = self.get_min_node(root.right)
root.key = temp.key
root.right = self.delete_node(root.right,
temp.key)
if root is None:
return root
# Update the balance factor of nodes
root.height = 1 + max(self.get_height(root.left),
self.get_height(root.right))
balance_factor = self.get_balance(root)
# Balance the tree
if balance_factor > 1:
if self.get_balance(root.left) >= 0:
return self.right_rotate(root)
else:
root.left = self.left_rotate(root.left)
return self.right_rotate(root)
if balance_factor < -1:
if self.get_balance(root.right) <= 0:
return self.left_rotate(root)
else:
root.right = self.right_rotate(root.right)
return self.left_rotate(root)
return root
# Function to perform left rotation
def left_rotate(self, root):
y = root.right
T2 = y.left
y.left = root
root.right = T2
root.height = 1 + max(self.get_height(root.left),
self.get_height(root.right))
y.height = 1 + max(self.get_height(y.left),
self.get_height(y.right))
return y
# Function to perform right rotation
def right_rotate(self, root):
y = root.left
T3 = y.right
y.right = root
root.left = T3
root.height = 1 + max(self.get_height(root.left),
self.get_height(root.right))
y.height = 1 + max(self.get_height(y.left),
self.get_height(y.right))
return y
# Get the height of the node
def get_height(self, root):
if not root:
return 0
return root.height
# Get balance factore of the node
def get_balance(self, root):
if not root:
return 0
return self.get_height(root.left) - self.get_height(root.right)
def get_min_node(self, root):
if root is None or root.left is None:
return root
return self.get_min_node(root.left)
# Print the tree
def print_tree(self, currPtr, indent, last):
if currPtr != None:
sys.stdout.write(indent)
if last:
sys.stdout.write("R----")
indent += " "
else:
sys.stdout.write("L----")
indent += "| "
print(currPtr.key)
self.print_tree(currPtr.left, indent, False)
self.print_tree(currPtr.right, indent, True)
my_tree = AVLTree()
root = None
nums = [33, 13, 52, 9, 21, 61, 8, 11]
for num in nums:
root = my_tree.insert_node(root, num)
my_tree.print_tree(root, "", True)
key = 13
root = my_tree.delete_node(root, key)
print("After Deletion: ")
my_tree.print_tree(root, "", True)
```
---
### Red-black tree
- A self-balancing binary search tree
- Each node contains an **extra bit**: the **color** of the node (red or black)
---
### Red-black tree
```python=
class Node():
def __init__(self, key):
self.key = key
self.parent = None
self.left = None
self.right = None
self.color = 1
```
Note:
https://www.programiz.com/dsa/red-black-tree
---
#### Red-black tree properties
- **Red/Black Property**: Every node is colored, either red or black.
- **Root Property**: The root is black.
- **Leaf Property**: Every leaf (NIL node) is black.
- **Red Property**: Children of red nodes must be black
- **Depth Property**: Any simple path from a node to any of its descendant leaf has the same black-depth (the number of black nodes).
---
#### Red-black tree properties
<img src="https://cdn.ucode.vn/uploads/1/upload/nUEodsPC.png" class="element-left content-img" />
---
#### Red-black Tree vs AVL Tree
- AVL ensures **strickly balanced** tree, Red-black tree does not. Max. height in AVL tree is $1.44\log n$. For red-black tree it's $2\log n$.
- AVL may require more rotations when insert/delete nodes - $O(\log n)$. Red-black tree requires **at most 2** rotations per operation - $O(1)$
---
#### Red-black Tree vs AVL Tree
- AVL tree gives better performance there are more consultation (reads) than manipulation (modifications).
- Red-black tree gives better performance in general cases, when there is balance between consultation (read) and manipulation (modification).
---
#### Red-black Tree vs AVL Tree
- `set`, `map` and equivalent data structures in C++, Java, C# are implemented by **red-black tree**.
- Database indices usually use **AVL tree** (or **B-tree**)
Note:
B-tree is not a binary tree. A typical use-case here is with databases on disk, where it is expensive to go down a level in the tree to find an item. B-tree better leverages cache.
---
### Segment Tree (statistic tree)
- A tree data structure to store information about **segments** (or intervals).
- Allows querying which of the stored segments contain a given point.
- The segment tree can be generalized to **higher dimension** spaces.
---
#### Segment Tree application examples
- Finding the sum of consecutive array elements $a[l \dots r]$ , or finding the minimum element in a such a range in $O(\log n)$ time.
---
#### Segment Tree application
Finding the sum of consecutive array elements $a[l \dots r]$.
- **Algo #1**: loop from $l$ to $r$ $\rightarrow$ $O(n)$
- **Algo #2**: prefix sum
- $s[i] =$ sum of elements from $0$ to $i$ $\rightarrow$ $O(n)$
- result = $s[r] - s[l-1]$
- $O(1)$, but the update operation take $O(n)$
- **Algo #3**: **Segment tree**
- Build tree: $O(n)$
- Query: $O(\log n)$
- Update: $O(\log n)$
---
#### Segment Tree
- Leaf Nodes are the elements of the input array.
- Each internal node represents some merging of the leaf nodes (ex. sum of leaf nodes under a node).
---
#### Segment Tree
<img src="https://cdn.ucode.vn/uploads/1/upload/OblrLwMC.png" class="element-left content-img" />
---
#### Segment Tree
```python=
class Node(object):
def __init__(self, start, end):
self.start = start
self.end = end
self.total = 0
self.left = None
self.right = None
```
---
#### Segment Tree: build the tree
```python=
def createTree(arr, l, r):
if l == r: # leaf node
n = Node(l, r)
n.total = arr[l]
return n
mid = (l + r) // 2
root = Node(l, r)
root.left = createTree(arr, l, mid)
root.right = createTree(arr, mid + 1, r)
root.total = root.left.total + root.right.total
return root
root = createTree(arr, 0, len(arr) - 1)
```
---
#### Segment Tree: query
```python=
def rangeSum(root, i, j):
# the range exactly matches the root
if root.start == i and root.end == j: return root.total
mid = (root.start + root.end) // 2
if j <= mid: # the entire interval lies in the left subtree
return rangeSum(root.left, i, j)
elif i >= mid + 1: # the entire interval lies in the right subtree
return rangeSum(root.right, i, j)
else: # the interval is split
return rangeSum(root.left, i, mid) + rangeSum(root.right, mid + 1, j)
return rangeSum(self.root, i, j)
```
---
#### Segment Tree: update
```python=
def updateVal(root, i, val):
if root.start == root.end: # update in a leaf
root.total = val
mid = (root.start + root.end) // 2
if i <= mid: # that leaf must be in the left subtree
updateVal(root.left, i, val)
else: # Otherwise, the right subtree
updateVal(root.right, i, val)
# Propogate the changes after recursive call returns
root.total = root.left.total + root.right.total
```
---
#### Segment Tree: full code
```python=
class Node(object):
def __init__(self, start, end):
self.start = start
self.end = end
self.total = 0
self.left = None
self.right = None
class RangeSumQuery(object):
def __init__(self, arr):
def create_tree(arr, l, r):
if l > r:
return None
if l == r:
n = Node(l, r)
n.total = arr[l]
return n
mid = (l + r) // 2
root = Node(l, r)
root.left = create_tree(arr, l, mid)
root.right = create_tree(arr, mid + 1, r)
root.total = root.left.total + root.right.total
return root
self.root = create_tree(arr, 0, len(arr) - 1)
def update(self, i, val):
def update_val(root, i, val):
if root.start == root.end:
root.total = val
return val
mid = (root.start + root.end) // 2
if i <= mid:
update_val(root.left, i, val)
else:
update_val(root.right, i, val)
root.total = root.left.total + root.right.total
return root.total
return update_val(self.root, i, val)
def range_sum(self, l, r):
def sum_range(root, l, r):
if root.start == l and root.end == r:
return root.total
mid = (root.start + root.end) // 2
if r <= mid:
return sum_range(root.left, l, r)
elif l >= mid + 1:
return sum_range(root.right, l, r)
else:
return sum_range(root.left, l, mid) + \
sum_range(root.right, mid + 1, r)
return sum_range(self.root, l, r)
arr = [1, 2, 3, 4, 5, 6, 7, 8]
rsq = RangeSumQuery(arr)
print(rsq.range_sum(0, 1))
rsq.update(1, 10)
print(rsq.range_sum(1, 2))
```
---
### Interval Tree & Range tree
- Segment tree **stores intervals**, and optimizes for "which of these intervals **contains a given point**" queries.
- Interval tree **stores intervals**, and optimizes for "which of these intervals **overlap with a given interval**" queries.
- Range tree **stores points**, and optimized for "which **points fall within** a given interval"
Note:
Interval trees are more generic. It can also be used for point queries - similar to segment trees.
---
### Binary Indexed (Fenwick) Tree - BIT
- A data structure that can efficiently update elements and calculate **prefix sums** in a table of numbers.
- An alternative to segment tree, and requires les space and is easier to implement.
- $O(\log n)$ for both query and update operations.
Note:
BIT không tổng quát bằng Segment tree, tất cả các bài có thể giải bằng BIT, đều có thể giải bằng Segment tree
---
#### Binary Indexed Tree
- Considering array $A[n]$ of $n$ elements. The corresponding Fenwick tree has $n+1$ nodes with an implicit node $0$ at the root.
- Each level $k$ of the tree contains nodes with indices corresponding to sums of $k$ distinct powers of $2$ (nodes with $k$ bits in binary representation).
- The parent of a given node can be found by clearing the last set bit (LSB) in its index, corresponding to the smallest power of 2 in its sum
---
#### Binary Indexed Tree
<img src="https://cdn.ucode.vn/uploads/1/upload/rVAtTrit.png" class="element-left content-img" />
---
#### Binary Indexed Tree
- LSB of $i$: $i \& (-i)$ (bitwise $AND$ operator)
- Parent of node $i$: $parent(i) = i - (i \& (-i))$
- Value of node $i$: range sum of elements in $A(parent(i), i]$
Note:
- Two's complement = one's complement + 1; one's complement = reverse all bit
---
#### Binary Indexed Tree
<img src="https://cdn.ucode.vn/uploads/1/upload/tlmOvySv.png" class="element-left content-img" />
---
#### Binary Indexed Tree
Range sum from the beginning upto $index$:
```python=
def sum(index):
_sum = 0
while index > 0:
_sum += bit[index]
index = index - (index & (-index))
return _sum
```
---
#### Binary Indexed Tree
Range sum from $left$ to $right$:
```python=
def range_sum(self, left, right):
return self.sum(right) - self. sum(left-1)
```
---
#### Binary Indexed Tree:
- Update an item: $delta = A[i]_{new} - A[i]_{old}$
- Update the index by adding LSB: ${\displaystyle i\leftarrow i+(i\ \&\ (-i))}$
```python=
def add(self, index, delta):
while index < len(self.bit):
self.bit[index] += delta
index = index + (index & (-index))
```
Note:
Intuitively, this can be thought of as updating each node (starting with i and iterating in increasing order) whose range of responsibility includes A[i].
---
#### Binary Indexed Tree
Building the tree:
- Initialize the tree values to $0$
- Perform $n$ point updates
---
#### BIT vs Segment tree
- BIT: store cumulative sums only
- Segment tree: more generics: sum, min, max, gcd...
- BIT is faster and more simple to implement
---
#### BIT: full code
```python=
class BIT:
def __init__(self, arr):
self.bit = [0] * (len(arr) + 1) # the binary indexed tree
for i in range(len(arr)):
# We fill the binary indexed from index 1
self.add(i + 1, arr[i])
# Find the sum of elements from the beginning upto right.
def sum(self, index):
_sum = 0
while index > 0:
_sum += self.bit[index]
index = index - (index & (-index))
return _sum
# Find the sum of array elements from left upto right.
def range_sum(self, left, right):
return self.sum(right) - self. sum(left-1)
# Update the binary index tree element(s) at index
def add(self, index, delta):
while index < len(self.bit):
self.bit[index] += delta
index = index + (index & (-index))
def print_bit(self):
print("\nBinary Indexed Tree array ... ")
print(str(self.bit))
if __name__ == "__main__":
arr = [4, -5, 7, 1, -1, 2, 3, 4, -2, 6, 5, -3, 8, -6, 10]
print("Array")
print(arr)
b = BIT(arr)
b.print_bit()
print("\n\nSum of first (14) " + str(b.sum(14)))
print("Sum of first (2) " + str(b.sum(2)))
print("Sum of first (1) " + str(b.sum(1)))
print("\nRange Sum : (0...4) " + str(b.range_sum(0, 4)))
print("Range Sum : (4...5) " + str(b.range_sum(4, 5)))
print("Range Sum : (1...2) " + str(b.range_sum(1, 2)))
print("Range Sum : (5...5) " + str(b.range_sum(5, 5)))
print("Range Sum : (5...7) " + str(b.range_sum(5, 7)))
pos = 5
delta = 2
print("\nAdding 2 to element at position 5 in array")
arr[pos-1] = arr[pos-1] + delta
print("Updating the binary indexed tree .. ")
b.add(pos, delta)
print("Array")
print(arr)
b.print_bit()
print("\nSum of first (14) " + str(b.sum(14)))
```
---
## The End
---
{"metaMigratedAt":"2023-06-17T19:46:12.416Z","metaMigratedFrom":"YAML","title":"Thuc Nguyen's ADSA Course - Lecture 09. Advanced Trees","breaks":true,"description":"View the slide with \"Slide Mode\".","slideOptions":"{\"theme\":\"white\"}","contributors":"[{\"id\":\"476f9158-9a39-4a2d-bb09-ce08dd7eb978\",\"add\":36329,\"del\":6058}]"}