## Lecture 06. Data Structures - Part 3
- Trees
- Binary Trees
- Expression Tree and RPN
---
### Tree
- A **hierarchical** form of data structure: there is a parent-child relationship between items
- Terminologies: Parent Node, Child Node, Root Node, Leaf Node (External Node), Internal Node, Ancestor of a Node, Descendant, Sibling, Level of a node, Subtree
---
#### Tree
<img src="https://cdn.ucode.vn/uploads/1/upload/MQDBRcTx.png" class="element-left content-img" />
---
#### Tree: Properties
- **Number of edges**: $N$ nodes, $N-1$ edges. There is only **one path** between each pair of nodes
- **Depth of a node**: the length of the path from the root to that node
- **Height of a node**: the length of the longest path from the node to a leaf node of the tree
- **Height of the Tree**: the length of the longest path from the root to a leaf node of the tree
- **Degree of a Node**: count of subtrees attached to that node
- **Degree of a Tree**: maximum degree of its nodes
---
#### Tree types
- General tree
- Binary tree
- Balanced tree
- Binary search tree
---
#### General Tree Node in Python
```python=
class Node:
def __init__(self, data):
self.data = data
self.children: List[Node] = []
```
---
#### Tree Node in Python
```python=
root = Node(1)
root.children = [Node(2), Node(3), Node(4)]
root.children[0].children = [Node(5), Node(6)]
root.children[2].children.append(Node(7))
```
<img src="https://cdn.ucode.vn/uploads/1/upload/ORHFyWtU.png" class="element-left content-img" />
---
### Binary Tree
- Tree of degree $2$: each parent node can have at most $2$ children
- Types of Binary Tree:
- Full Binary Tree
- Complete Binary Tree
- Perfect Binary Tree
- Degenerate or Pathological Tree
- Skewed Binary Tree
---
#### Full Binary Tree
- Every internal node has exactly **two** children.
<img src="https://cdn.ucode.vn/uploads/1/upload/TJIfHsmu.png" class="element-left content-img" />
---
#### Full Binary Tree
- $i$ = number of internal nodes $= \frac{n-1}{2}$ $= l-1$
- $n$ = total number of nodes $= 2i+1$ $= 2l+1$
- $l$ = number of leaves $=i+1$ $= \frac{n+1}{2}$, at most $2^{λ-1}$
- $λ$ = number of levels
<img src="https://cdn.ucode.vn/uploads/1/upload/TJIfHsmu.png" class="element-left content-img" />
---
#### Perfect Binary Tree
- Every internal node has exactly two child nodes
- All the leaf nodes are at the same level
<img src="https://cdn.ucode.vn/uploads/1/upload/QptFyEfx.png" class="element-left content-img" />
---
#### Perfect Binary Tree
- $h$ = height of tree = $\log(n+1) - 1$
- $n$ = total number of nodes $= 2^{h + 1} – 1$
- $l$ = number of leaves $= 2^h$
- Average depth of a node: $O(log(n))$
<img src="https://cdn.ucode.vn/uploads/1/upload/QptFyEfx.png" class="element-left content-img" />
---
#### Complete Binary Tree
- All the levels of the tree are filled completely except the lowest level nodes (All the leaf nodes are at the same level)
- The lowest level is filled from as left as possible
<img src="https://cdn.ucode.vn/uploads/1/upload/FQtKAjeL.png" class="element-left content-img" />
---
#### Complete Binary Tree
<img src="https://cdn.ucode.vn/uploads/1/upload/xpiDspkn.png" class="element-left content-img" />
---
#### Complete Binary Tree
<img src="https://cdn.ucode.vn/uploads/1/upload/fpFxeGgP.png" class="element-left content-img" />
---
#### Complete Binary Tree
<img src="https://cdn.ucode.vn/uploads/1/upload/HNMpCfVu.png" class="element-left content-img" />
---
#### Complete Binary Tree
<img src="https://cdn.ucode.vn/uploads/1/upload/mEGHNbAz.png" class="element-left content-img" />
---
#### Degenerate or Pathological Tree
- Each node has a single child, either left or right
<img src="https://cdn.ucode.vn/uploads/1/upload/BcpbQtMs.png" class="element-left content-img" />
---
#### Skewed Binary Tree
- A degenerate tree, in which the tree is either dominated by the left nodes or the right nodes.
- Can be left-skewed or right-skewed
<img src="https://cdn.ucode.vn/uploads/1/upload/dWVzjiyB.png" class="element-left content-img" />
---
#### Binary Tree Node in Python
```python=
class Node:
def __init__(self, data):
self.data = data
self.right: Node | None = None
self.left: Node | None = None
```
---
#### Binary Tree Node in Python
```python=
root = Node(1)
root.left = Node(12)
root.right = Node(9)
root.left.left = Node(5)
root.left.right = Node(6)
```
<img src="https://cdn.ucode.vn/uploads/1/upload/crhDkJEQ.png" class="element-left content-img" />
---
#### Tree Traversal: Inorder
```python=
def inorder(root):
if root:
inorder(root.left)
print(root.data, "->", end=' ')
inorder(root.right)
```
---
#### Tree Traversal: Inorder
<img src="https://cdn.ucode.vn/uploads/1/upload/crhDkJEQ.png" class="element-left content-img" />
```shell=
5 -> 12 -> 6 -> 1 -> 9 ->
```
---
#### Tree Traversal: Preorder
```python=
def preorder(root):
if root:
print(root.data, "->", end=' ')
preorder(root.left)
preorder(root.right)
```
---
#### Tree Traversal: Preorder
<img src="https://cdn.ucode.vn/uploads/1/upload/crhDkJEQ.png" class="element-left content-img" />
```shell=
1 -> 12 -> 5 -> 6 -> 9 ->
```
---
#### Tree Traversal: Postorder
```python=
def postorder(root):
if root:
postorder(root.left)
postorder(root.right)
print(root.data, "->", end=' ')
```
---
#### Tree Traversal: Postorder
<img src="https://cdn.ucode.vn/uploads/1/upload/crhDkJEQ.png" class="element-left content-img" />
```shell=
5 -> 6 -> 12 -> 9 -> 1 ->
```
---
#### Tree: Array Representation
<img src="https://cdn.ucode.vn/uploads/1/upload/pLtJJREL.png" class="element-left content-img" />
---
#### Tree: Array Representation
<img src="https://cdn.ucode.vn/uploads/1/upload/pLtJJREL.png" class="element-left content-img" />
<img src="https://cdn.ucode.vn/uploads/1/upload/jTMisPjd.png" class="element-left content-img" />
---
#### Tree: Array Representation
<img src="https://cdn.ucode.vn/uploads/1/upload/pLtJJREL.png" class="element-left content-img" />
<img src="https://cdn.ucode.vn/uploads/1/upload/jTMisPjd.png" class="element-left content-img" />
---
#### Tree: Array Representation
<img src="https://cdn.ucode.vn/uploads/1/upload/hCSAAnsH.png" class="element-left content-img" />
---
#### Tree: Array Representation
<img src="https://cdn.ucode.vn/uploads/1/upload/MnGQKjLT.png" class="element-left content-img" />
<img src="https://cdn.ucode.vn/uploads/1/upload/nfyQKuQp.png" class="element-left content-img" />
---
#### Tree: Array Representation
<img src="https://cdn.ucode.vn/uploads/1/upload/pLtJJREL.png" class="element-left content-img" />
- Left child of node $i$ is node $2i + 1$
- Right child of $i$ is node $2i + 2$
- Parent of $i$ is node $\lfloor \frac{i-1}{2} \rfloor$
---
#### Tree: Array Representation
- (+) Easy to implement
- (+) Memory efficient (for complete binary trees)
- (+) Random access to nodes, Traversals are efficient
- (-) Difficult to insert and delete nodes
- (-) Limited to complete trees
---
### Expression Tree
<img src="https://cdn.ucode.vn/uploads/1/upload/EdNUwlus.png" class="element-left content-img" />
$(\frac{6}{2} + 3) \times (7-4)$
---
#### Expression Tree: calculation
<img src="https://cdn.ucode.vn/uploads/1/upload/EdNUwlus.png" class="element-left content-img" />
```python=
def evaluate(node):
if node.data not in operators:
return node.data
# operator node: OP
L = evaluate(node.left)
R = evaluate(node.right)
return OP(L, R)
```
---
#### Expression Notations
<img src="https://cdn.ucode.vn/uploads/1/upload/EdNUwlus.png" class="element-left content-img" />
- Infix (inorder traversal): `6 / 2 + 3 × 7 - 4`
- Prefix (preorder traversal): `× + / 6 2 3 - 7 4`
- Postfix (postorder traversal): `6 2 / 3 + 7 4 - ×` $\rightarrow$ RPN (Reverse Polish Notation)
---
#### Reverse Polish Notation
<img src="https://cdn.ucode.vn/uploads/1/upload/EdNUwlus.png" class="element-left content-img" />
```python
L = evaluate(node.left)
R = evaluate(node.right)
return OP(L, R)
```
- `6 2 / 3 + 7 4 - ×` $\rightarrow$ same processing order as the function above
---
#### Reverse Polish Notation
- `6 2 / 3 + 7 4 - ×`
- Brackets are not required
- Can be read and processed from left to right
- Easy implementation using a stack
---
#### Reverse Polish Notation
- `6 2 / 3 + 7 4 - ×`
- If a **value** appears next in the expression, **push** this value on to the stack.
- If an **operator** appears next, **pop two** items from the top of the stack and **push the result** of the operation on to the stack.
---
#### Reverse Polish Notation
```python=
def evaluate(exp):
stack = []
for token in exp.split():
if token not in '/*+-':
stack.append(int(token))
else:
v2, v1 = stack.pop(), stack.pop()
if token == '+': stack.append(v1 + v2)
elif token == '-': stack.append(v1 - v2)
elif token == '*': stack.append(v1 * v2)
elif token == '/': stack.append(int(v1 / v2))
return stack.pop()
print(evaluate("6 2 / 3 + 7 4 - *")) # 18
```
---
#### From Infix to Postfix
- `(6 / 2 + 3) × (7 - 4)`
- $\rightarrow$ `6 2 / 3 + 7 4 - *`
---
#### From Infix to Postfix
```python=
operators = {'+', '-', '*', '/', '(', ')'}
precedences = {'+': 1, '-': 1, '*': 2, '/': 2}
def infix_to_postfix(exp):
stack = []
rpn = []
for token in exp.split():
if token not in operators:
rpn.append(token)
elif token == '(':
stack.append('(')
elif token == ')':
while stack and stack[-1] != '(':
rpn.append(stack.pop())
stack.pop()
else:
while stack and stack[-1] != '(' and precedences[token] <= precedences[stack[-1]]:
rpn.append(stack.pop())
stack.append(token)
while stack:
rpn.append(stack.pop())
return " ".join(rpn)
print(infix_to_postfix('( 6 / 2 + 3 ) * ( 7 - 4 )')) # 6 2 / 3 + 7 4 - *
```
---
## The End
---
{"metaMigratedAt":"2023-06-17T19:46:11.306Z","metaMigratedFrom":"YAML","title":"Thuc Nguyen's ADSA Course - Lecture 06. Data Structures - P3","breaks":true,"description":"View the slide with \"Slide Mode\".","slideOptions":"{\"theme\":\"white\"}","contributors":"[{\"id\":\"476f9158-9a39-4a2d-bb09-ce08dd7eb978\",\"add\":11642,\"del\":1098}]"}