COMS W3134 Lecture Notes - Lecture 16: Glossary Of Arithmetic And Diophantine Geometry, Hash Table
Document Summary
Announcements: hw 4 on chapter 5 & 6 topics, due 11/21, do readings & can start on hw after next wed"s lecture, midterm questions for both sections posted, midterm solutions will be posted later this week. Takes in avlnode t, returns avlnode: root will change if rotation is done. Invoke height function on t. left and t. right, if the height differences is larger than 1, then there is imbalance and we know which side it"s on. Compares two children of left hand side, if left subtree has the imbalance to determine if it is zig-zig or zig-zag Compares two children of right hand side, if right subtree has the imbalance to determine if it is zag-zag or zag-zig Carry out rotations correspondingly (single or double) Find new height by finding max of heights of left and right subtrees and add 1. rotatewithleftchild method. Takes in avlnode k2, and returns avlnode k2 k1 c.