Princeton Alogorithm COS226 Week

last lecture, we get the average case is log n 's binary search tree. how about worst case is log n.
this lecture we will learn how to implement a balance search tree which search, insert, delete could be in log N in worst case.

image.png

2-3 tree

2-3 tree means one tree node could have one key, two children or two key, three children.
and if we inorder traversal yields keys, it should be in ascending order.

image.png

the third property is that is is a perfect balance tree mean s every path from root to null link has same length

insert to 2-3 tree may call split, delete from 2-3 tree may call merge to keep the property we introduce before.

split like below

image.png image.png

2-3 tree performance

image.png image.png

implementation

direct implementation is complicated,

1. maintaining multiple node type is cumbersome.
2. need multiple compares to move down tree
3. need to move back up the tree to split 4-nodes
4. large number of cases for splitting

Red Black Tree

the red black tree is extended from 2-3 tree. the diff is use 'internal' left-leaning links as 'glue' for 3-nodes.

image.png

so now an equivalent definition is red black tree is that:

1. no nodes has two red links connected to it
2. every path from root to null link has the same number of black links

3. red links lean left

   
   image.png

search

search is the same as for elementary BST(ignore color)

left rotation and right rotation and color flip

image.png
image.png
image.png
image.png
image.png
image.png

insertion in a LLRB tree

this part if u are firstly know it, please learn it from coursera vedio.

image.png

the height of LLRB tree is 2 lgN in the worst case
because every path from root to null link has same number of black links.
never two red links in a row.
so the number of red link is equal to black link in worst case

image.png

B tree

before introduce the B tree, we need to know some knowledge about out file system.
Page = cintiguous block of data(4K)
Probe = first access to a page (from disk to memory)
Property = time required for a probe is much larger than time to access data with in a page.
So our goal is to access data using minimum number of probes.

B tree generalize 2-3 tree by allowing up to M-1 key-link pairs per node.

image.png

seach in a b tree

start at root, find interval for search key and take corresponding link
search terminates in external node

insert

search for new key, insert at bottom, split node with M key-link pairs on the way up the tree

image.png

Quiz

Q1

image.png

solution 1, use bst count if count >= 0 is black, count < 0 is red. we get count, use abs()
solution 2, if left is larger than right, then it is red, if left is lower equal than right, it is black. we need another two NULL node which can make the leaf node have color
solution 3, encode the color info into pointer, can not implemented by java. ok for c and c++

Q2

image.png

this problem could be solved by two pointer, and dynamic programming.
the idea of two pointer is easy, first lock the first query word in document position, then find until the last query word, then from last query word in document position go back to find the first query word.
eg (query word: a,b document word: a,c,c,a,b)
i start at 0, then j end at 4, in the back finding, i end at 3. then this is one possible answer, then move the i to the next a position.

dynamic programing ,we use dp array to save the position.
dp[i][j] means in ith query word, and in the jth document word, the distance to beginning query word position.
the state transition equation is word i = word j, then dp[i][j] = dp[i - 1][j -1] , else
dp[i][j] = dp[i][j - 1]
eg. (a,c,c,a,b) query word(a,b)
dp[0] = {0,1,2,3,4,5}
dp[1] = {0,0, 0, 0, 3, 4}

the ans is that we find the j - dp[2][i] +1 with min value;

Q3

image.png

use a red black tree, key is int, value is queue item. we keep a incresing key. when we append, key++, as the red black tree's key.
remove we just remove the the rbt max.
get i, use red black tree select i then find the key, red black tree get the key.
remove i, get the key by select i, then remove the key.

course quiz and project : https://github.com/yixuaz/algorithm4-princeton-cos226