Lecture Notes for CSCI 2300 - INTRODUCTION TO ALGORITHMS at Rensselaer (RPI)

Notes Information

Material Type:Class Note
Subject:Computer Science
University:Rensselaer Polytechnic Institute
Term:Spring 2001
  • On the Left
  • On the Right
  • Implementation
  • Binary Search
  • Correctness
  • Average-Case
  • Consideration
  • Right-to-Left
  • Source Code
Login / Sign Up to View Document
Preview Page 1Preview Page 2Preview Page 3Preview Page 4Preview Page 5Preview Page 6

Sample Document Text

CSci 2300 | Data Structures and Algorithms Week 7, Class 13 | February 23, 2001 AVL Trees { Balanced Binary Search Trees Test 1 | General Comments Average 77.2. There was no curve. Remember, if this is your lowest test grade of the semester it will only count 5% toward your overall grade. Questions about grading: { Argue only correctness issues, not about point assignments { Refer all questions about correctness to me. We will go over solutions in class. Solutions will also be posted on the web. Review from Class 12 Binary search tree de nitions Binary search tree class overview Core algorithms: insert, nd, and remove Copying and destroying Binary Search Trees | Analysis Analysis is done in terms of the number of nodes, N, stored in the tree. The key consideration is the height of the root. The worst-case for the unbalanced implementation is O(N). BSTs can become \lopsided" quite easily, since input is often nearly or- dered. The average-case height of a BST is O(logN): {...

Related Documents

On the Right Exam
On the Left Notes
On the Left Notes
On the Left Notes
On the Left Exam
Average-Case Notes
On the Left Notes
On the Left Notes
On the Right Notes
On the Left Notes
On the Right Notes
Spinal Reflex Quiz
On the Left Quiz
On the Right Notes
Qualitative Notes
On the Right Exam
155, "/var/app/current/tmp/"