[Data Structure (Java)] Tree (1) - Binary Tree

 

https://crane206265.tistory.com/80

 

[Data Structure (Java)] Iterator

드디어 Tree입니다. 생각보다 간단하면서도, 생각보다 많이 복잡하더라고요.

---

Tree

: a set of nodes storing elements hierarchically (*hierarchical : 계층적인)

- parent-child relationship between nodes

- each element has a parent : except - root (topmost node)

- each element has zero or more children

 

Terminology
- root : node without parent
- internal node : node with at least one child
- external node : node without children (leaf)
- depth of a node : # of edges from the root to the node
- height of a tree : maximum # of links on any path from root to a leaf
       -> if single node : height = 0
       - ==> empty tree : height = -1
- subtree : tree consisting of a node and ALL the descendants
- sibling : have the same parent node

 

* order of tree : usually) left to right for siblings, top to bottom

---

Binary Tree

: tree that its every node has at most 2 children

- each child node is labeled as being either a 'left child' or a 'right child'

- a left child precedes a right child in the oreder of a chlidren of a node

 

converting general tree -> binary tree :

Left-Child-Right-Sibling (LCRS) representation
- root : same
- leftmost child -> left-child
- siblings of left child (at general tree : horizontal) -> right-children (at binary tree : "rotate 45 deg")

 

level $d$ : set of all nodes at the same depth $d$

ex) - level $0$ : root

      - level $d$ : at most $2^d$ nodes

 

==> $n$ : # of nodes / $h$ : height

# of nodes : $\mathbf{h+1 \leq n \leq} 1 + 2 + 2^2 + \cdots + 2^h = \mathbf{2^{h+1} - 1}$

# of external nodes : $1 \leq n_E \leq 2^h$

# of internal nodes : $h \leq n_I \leq 1 + 2 + \cdots + 2^{h-1} = 2^h-1$

 

 

how to index the nodes?

"Level-Numbering" : Numbering Nodes
- root : index = $0$
- left child of a node $i$ : index = $2i+1$
- right child of a node $i$ : index = $2i+2$

it is possible to skip index
-> advantage : easy to convert tree <-> array with arithmetic operations
-> disadvantage : memory waste(empty cells) depending on the shape of a tree