K tree

It is about advanced tree

1. K- Tree Prepared by:- Suraksha Sanghavi

2. Invented in 1970s by Jon Bentley It is a binary tree K-tree is also known as KD tree (k- diamensional ) Where D=1,2,3…… But we have in study is 2D Tree Each level has a “ cutting dimension” Each node contains a point P = ( x,y )

3. Complexity Insert: Average and balanced trees: O(log N) Worst case: O(N ) Print: Range query: for M matches Perfectly balanced tree: K-D trees: O(M + k N (1-1/k) ) 2-D trees: O(M + N)

4. Its left side with space known as left subtree Its right side with points known as right subtree Its first node is root (Grand parent) While inserting its child (parent) it checks with x- cordinate While inserting next node at next level it checks with y-co- dinate

5. General idea for reprsenting tree It is reprsenting in two way 1)Tree 2)Graph 0 level - x- alinged (vertical line)-compare with x-co-ordinate. 1-level – y- alinged (horizontal line –it depend on child on which side) – compare with y-co-ordinate. 2-level – x- alinged -compare x- cordinate . 3-level – y alinged -compare y – corinate .

6. Applications Nearest neighbour Search Database Queries

7. Thank you