Binary Search

0.0(0)
studied byStudied by 0 people
0.0(0)
full-widthCall with Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/9

encourage image

There's no tags or description

Looks like no tags are added yet.

Study Analytics
Name
Mastery
Learn
Test
Matching
Spaced
Call with Kai

No study sessions yet.

10 Terms

1
New cards

Requirements

  • Must maintain BST property: left subtree keys ≤ node key ≤ right subtree keys

  • Internal nodes store keys or key-value pairs

  • External nodes (leaves) are empty/don't store items

2
New cards

Elements

  • Must be a total order relationship

  • Must be comparable

3
New cards

Ideal/Worst Tree Structures

Ideal: Balanced tree with height O(log n)

Worst: Linear/degenerate tree with height O(n) (resembles linked list)

4
New cards

Time Complecity of Binary Search

Balanced - O(logn)

Unbalanced - O(n)

In arrays in all cases - O(logn)

5
New cards

Space Complexity

O(n)

  • For both BST and arrays

6
New cards

Binary Search (Array) Requirements

  • Sorted array

7
New cards

Binary Search - Remove

No kids: Just cut

One kid: Promote

Two kids: Inorder swap

8
New cards

Binary Tree - Insert

Search, Reach Leaf, Plant New Node

9
New cards

Binary Search - Search

Compare, Left-Right, Repeat

10
New cards

Binary Search Methods - Time Complexity

Worst Case: O(n)

Best Case: O(logn)

(O(1) - for removal if one node)