Leftist Tree, Tries and Hashing

Question 1

Leftist Tree adalah?

Answer 1

variant dari heap yang dapat mencari smallest or largest element in tree. lebih mudah dengan linked-list. advantages: kalau mau merge dua heap ke dalam satu heap

Question 2

binary tree with external node is called?

Answer 2

extended binary tree

Question 3

Tries (prefix tree) adalah?

Answer 3

ordered tree data structure yang digunakan untuk menyimpan associative array (strings)

Question 4

Hashing?

Answer 4

suatu transformasi dari sebuah string kedalam ukuran yang lebih pendek atau key yang me representasikan original string. untuk menyimpan dan mengambil item dalam database

Question 5

Collision pada Hashing adalah?

Answer 5

several string yang mana punya hash key yang sama.

Question 6

2 cara untuk menhandle collisions?

Answer 6

1. linear probing, mencari ruang kosong berikutnya dan menyimpan string disana
2. chaining, menyimpan string ke sebuah slot sebagai list yang telah dikaitkan.

Question 7

Disadvantages Linear probing?

Answer 7

bad search complexity kalau banyak collisions

Question 8

Trie berasal dari kata?

Answer 8

reTRIEval

Question 9

cara-cara untuk hash a string into a key?

Answer 9

1. mid-square
   kuadratkan string dan gunakan angka bits yang sesuai dari hasil tengah kuadrat untuk mendapatkan hash key
2. division (most common)
   membagi string dengan operator modulus
3. folding
   partisi string kedalam beberapa bagian. lalu menambahkan bagian tersebut untuk mendapatkan hash key.

Question 10

2 jenis leftist tree?

Answer 10

1. min leftist tree - setiap node lebih kecil dari anaknya

2. max leftist tree - setiap node lebih besar dari anaknya

Question 11

what is trie?

Answer 11

a tree dimana setiap vertex merepresentasikan single word or prefix

Question 12

root dari trie?

Answer 12

represent empty character