[CSE 565] - 2019-10-02.pdf leftist tree

 

Merge two binary hea takes O(n) time 이게 일반적인 사실이다. 이걸 O(logn)으로 하기 위해서  쓰는게 leftist tree 이다. 

 

rank 라는게 shortest path from v to NULL

 

leftist propoerty -> T 에 있는 vertex 를 가지고 봤을떄 

 

vertex 의 left child 의 rank 가 오른쪽보다 항상 같거나 많다.

 

 Fact - rank(root) = O(logn) 이다 당연하다 이건 

 

그래서 이 둘을 Merge 하기 하려고 한다. 

 

 

쨋든 O(logn) 으로 바뀐다. 그릭 봐서 swap 을 해준다. 

ㅇ

Find Min - return root

 

delete - min 은 root끼리 merge 한다. 

 

insert  - Merge (PQ, new tree with the new node)

u = x 

 

parent 

 

left < right 이면

 

left의 rank + 1 가 될듯 

 

이게 decreasekey 이다 

 

https://www.geeksforgeeks.org/leftist-tree-leftist-heap/