binary-search-avl-trees.md (4231B)
1 +++ 2 title = "Binary Search & AVL Trees" 3 template = "page-math.html" 4 +++ 5 6 # Binary Search & AVL Trees 7 8 **Binary trees:** 9 10 - can have a linked implementation 11 - traversals, recursive (e.g. preorder to nonrecursive) 12 13 **Binary search** 14 15 - search for key k in sorted array A[l…r] 16 - algorithm search (A, l, r, k): 17 - if l > r, return that k is not present 18 - if l ≤ r, let l := floor( (l+r)/2 ) 19 - compare m := A[i] with k: 20 - if k < m, search k in A[l…i-1] 21 - if k = m, return that k is at i 22 - if k > m, search k in A[i+1…r] 23 - recurrence equation: 24 25 $T(n) = \begin{cases} 26 1 & \text{if $n = 1$}\\\\ 27 T(\frac{n}{2})+1 & \text{if $n>1$}\end{cases}$ 28 29 - in O(logn) 30 31 Lookup table: 32 33 - search in O(logn) 34 - adding and deleting in O(n) 35 36 **Binary search tree:** 37 38 - for a node x with key k, all left nodes are less than k and right greater than k 39 - doesn’t have to be filled left to right like a heap 40 - to find successor (inorder), return minimum of subtree 41 - operations (search, min, max, succ, pred) are all in O(n) 42 - add & remove in 43 44 **AVL tree (balanced)** 45 46 - height of tree == height of root == max path to leaf 47 - BST where for every node, absolute value of difference between left and right height is max 1 48 - as in BST, but balanced: 49 - height is in O(logn) 50 - min, max is in O(h) == O(logn) 51 - succ, pred in O(logn) 52 - search in (logn) 53 - insert/delete are more complicated, have to rebalance: 54 - left-left imbalance — right rotation 55 56 ``` 57 T1, T2, T3 and T4 are subtrees. 58 z y 59 / \ / \ 60 y T4 Right Rotate (z) x z 61 / \ - - - - - - - - -> / \ / \ 62 x T3 T1 T2 T3 T4 63 / \ 64 T1 T2 65 ``` 66 67 - left-right imbalance — left rotation to left-left, then right rotation 68 69 ``` 70 z z x 71 / \ / \ / \ 72 y T4 Left Rotate (y) x T4 Right Rotate(z) y z 73 / \ - - - - - - - - -> / \ - - - - - - - -> / \ / \ 74 T1 x y T3 T1 T2 T3 T4 75 / \ / \ 76 T2 T3 T1 T2 77 ``` 78 79 - right-right imbalance — left rotation 80 81 ``` 82 z y 83 / \ / \ 84 T1 y Left Rotate(z) z x 85 / \ - - - - - - - -> / \ / \ 86 T2 x T1 T2 T3 T4 87 / \ 88 T3 T4 89 ``` 90 91 - right-left imbalance — right rotation to right-right, then left rotation 92 93 ``` 94 z z x 95 / \ / \ / \ 96 T1 y Right Rotate (y) T1 x Left Rotate(z) z y 97 / \ - - - - - - - - -> / \ - - - - - - - -> / \ / \ 98 x T4 T2 y T1 T2 T3 T4 99 / \ / \ 100 T2 T3 T3 T4 101 ```