Self-balancing binary search tree

March 18, 2017

Introduction

Julia read this article of binary search, and then she found the article is well-written and also the author brought up a topic called self-balancing search tree. So, Julia will start to read this wiki article, invest 30 minutes first time for the reading.

Article study 

Julia learns to read the wiki article slowly, she knows that in order to be able to give a good reference on codereview, JS1 always referred her to the wiki site. 

Take it seriously, be able to go over the wiki article first, write down new words to learn:

Implementations 

Popular data structures implemented this type of tree include:
2-3 tree
AA tree
AVL tree
Red-black tree
Scapegoat tree
Splay tree
Treap

Applications

self-balancing tree is the main competitor of hash table, since O(logn) almost good enough for most time efficiency compared to O(1), for example, n = 1000, n is the power of 10.

priority queues - implementation using self-balancing binary search tree
associated arrays -
key-value pairs

Line-segment intersection => sweep line algorithm => Hackerrank: Gridland Metro
Point Location => ?

Are you ready for this statement?
1. self-balancing BSTs have better worst-case lookup performance than hash tables (O(log n) compared to O(n)) <=? making sense?

2. but have worse average-case performance (O(log n) compared to O(1))

Log of reading history

1. Time: 1:11pm - 1:40pm, give 30 minutes for reading, March 18, 2017