Balanced Binary Search Tree

Question 1

Worst Case pada operation BST?

Answer 1

O(n)

Question 2

Balanced Binary Search Tree, contohnya?

Answer 2

AVL Tree, Red Black Tree

Question 3

First self-balancing binary search tree?

Answer 3

AVL Tree

Question 4

AVL Tree Concept?

Answer 4

Height of a node:

1. height of an empty sub tree is 0
2. height of a leaf is 1
3. height of an internal node is the maximum height of its children plus 1

balance factor of all nodes in AVL Tree at most 1

Question 5

Red Black Tree Concept?

Answer 5

1. every node has a color, red or black
2. root is black by default
3. all external nodes are black
4. if a node is red, the both its children are black
5. no red node has a red parent

Question 6

Insertion RBT:

Answer 6

1. if parent is black, no violation

2. if parent is red, violation occured