BALANCED BINARY TREE
Konsep AVL Tree :
- Height dari sub tree yang kosong adalah 0.
- Height dari leaf adalah 1.
- Height dari internal node adalah max height dari anaknya + 1.
Balance Factor :
- Perbedaan height dari subtree kiri dan kanan.
- Selisih ketinggian hanya boleh bernilai 1 / 0.
Jenis rotasi dibagi menjadi 2 :
- Single rotation
- Double rotation
Delete node pada AVL TREE
- Jika remove node adalah leaf, langsung remove
- Jika remove node cuma punya 1 child, maka remove node akan langsung digantikan oleh child tersebut.
- Jika remove node punya 2 child :
- Pilih node terkecil dari subnode kanan
- Atau pilih node terbesar dari subnode kiri
GUEST LECTURE – SELVAKUMAR MANICKMAN
Node structure : A tree node should look like the below structure. It has data part and references to its left and right child nodes.
Treee terminology :
- rooted tree : 1 vertex designates as rot and every edge directed away.
- parent : u is the parent of v. iff there is an edge from u to v.
- child : v is called the child of u.
Every non root node has a unique parent.
The level of vertex v in a rooted tree is the height of vertex max levels of its vertices.
M-ary Trees : rooted tree where every vertex has no more than ‘m’ children. Full m-ary if every internal vertex has exactly ‘m’ children. m-2 gives a binary tree.
3-ary tree :
- every internal vertex has max 2 children.
- an ordered rooted tree is a rooted tree where the children of each internal vertex are ordered.
- in an order IOT, the 2 possible children of a vertex are called the left and right child, if they exist.