binary search trees

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

1/7

encourage image

There's no tags or description

Looks like no tags are added yet.

Study Analytics
Name
Mastery
Learn
Test
Matching
Spaced

No study sessions yet.

8 Terms

1
New cards

binary search trees

  • each node is greater than every node in its left subtree

  • each node is less than every node in its left subtree

2
New cards

what are the BST operations?

  1. insert

  2. search

  3. delete

3
New cards

BST insert

  • start at root

  • always insert as a leaf

4
New cards

BST Search/Find

  • start at root

  • compare to see if less than or greater than root; proceed to corresponding subtree and repeat process

5
New cards

BST delete (leaf node)

  • just delete that specific node

  • does NOT affect the rest of the tree

6
New cards

BST delete (1 child)

  • replace node with its child

    • greater or less based on which subtree it is

<ul><li><p>replace node with its child</p><ul><li><p>greater or less based on which subtree it is</p></li></ul></li></ul><p></p><p></p>
7
New cards

BST delete (2 child)

  • find next higher node

8
New cards

what are the advantages of binary search trees?

  1. speed - O(logn)