Scribd Logo
Upload

Welcome to Scribd!

  • 65 views

    Binary Search Trees: Tim Doolan

    Uploaded by

    Wessel van Dam
    The document discusses binary search trees (BSTs) and balanced binary search trees. It covers: 1) The basic operations of searching, inserting, finding the minimum/maximum elements, and traversing a BST in inorder. 2) Balanced BSTs like AVL trees maintain the height of the tree to be O(log N) through rotations, keeping the balance factor between -1 and 1 for every node. 3) Rotations are used to rebalance the tree during insertions and deletions to maintain the balance property.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Binary Search Trees: Tim Doolan

    Uploaded by

    Wessel van Dam
    65 views14 pages
    The document discusses binary search trees (BSTs) and balanced binary search trees. It covers: 1) The basic operations of searching, inserting, finding the minimum/maximum elements, and traversing a BST in inorder. 2) Balanced BSTs like AVL trees maintain the height of the tree to be O(log N) through rotations, keeping the balance factor between -1 and 1 for every node. 3) Rotations are used to rebalance the tree during insertions and deletions to maintain the balance property.

    Original Description:

    A nice coding assignment to work with binary seach trees

    Original Title

    bst_avl

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses binary search trees (BSTs) and balanced binary search trees. It covers: 1) The basic operations of searching, inserting, finding the minimum/maximum elements, and traversing a BST in inorder. 2) Balanced BSTs like AVL trees maintain the height of the tree to be O(log N) through rotations, keeping the balance factor between -1 and 1 for every node. 3) Rotations are used to rebalance the tree during insertions and deletions to maintain the balance property.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    65 views14 pages

    Binary Search Trees: Tim Doolan

    Uploaded by

    Wessel van Dam
    The document discusses binary search trees (BSTs) and balanced binary search trees. It covers: 1) The basic operations of searching, inserting, finding the minimum/maximum elements, and traversing a BST in inorder. 2) Balanced BSTs like AVL trees maintain the height of the tree to be O(log N) through rotations, keeping the balance factor between -1 and 1 for every node. 3) Rotations are used to rebalance the tree during insertions and deletions to maintain the balance property.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 14

    Binary Search Trees

    Tim Doolan

    University of Amsterdam

    February 28th, 2019


    Maintaining a sorted list

    Complexity of inserting new element?

    I Resizing Array
    I Finding index to insert?
    I Insert element at index?

    I Linked List
    I Insert element into list?
    I Finding place to insert?
    1 def b i n a r y s e a r c h ( elem , s o r t e d l i s t ) :
    2 low , h i g h , h a l f = 0 , l e n ( s o r t e d l i s t ) , 1
    3
    4 while h a l f > 0 :
    5 h a l f = ( h i g h −low ) // 2
    6 mid = low + h a l f
    7
    8 i f elem < s o r t e d l i s t [ mid ] :
    9 h i g h = mid
    10 e l i f elem > s o r t e d l i s t [ mid ] :
    11 low = mid
    12 else :
    13 r e t u r n mid
    14
    15 r e t u r n −1
    Maintaining a sorted list

    Complexity of inserting new element?

    I Resizing Array

    • Binary Search O(log (N))


    • Shifting elements after O(N)

    I Linked List

    • Link node into list O(1)


    • Search through sorted list O(N)
    Binary Search Tree
    Node

    • Key
    • Value

    • Left
    • Right
    • Parent

    Binary Search Tree Property: (holds for every node n)

    ∀n : all keys in left subtree ≤ n.key

    & all keys in right subtree ≥ n.key


    1 def s e a r c h ( r o o t , k e y ) :
    2 i f r o o t == None :
    3 r e t u r n None
    4
    5 e l i f r o o t . k e y == k e y :
    6 return root
    7
    8 e l i f key > r o o t . key
    9 return s e a r c h ( r o o t . r i g h t , key )
    10 else :
    11 return s e a r c h ( r o o t . l e f t , key )
    1 def i n s e r t ( r o o t , node ) :
    2 i f node . k e y > r o o t . k e y
    3 i f r o o t . r i g h t == None :
    4 r o o t . r i g h t = node
    5 else :
    6 i n s e r t ( r o o t . r i g h t , node )
    7 else :
    8 i f r o o t . l e f t == None :
    9 r o o t . l e f t = node
    10 else :
    11 i n s e r t ( r o o t . l e f t , node )
    1 def maximum ( r o o t ) :
    2 i f r o o t . r i g h t == None :
    3 return root
    4 else :
    5 r e t u r n maximum ( r o o t . r i g h t )
    6
    7 def minimum ( r o o t ) :
    8 i f r o o t . l e f t == None :
    9 return root
    10 else :
    11 r e t u r n minimum ( r o o t . l e f t )
    12
    13
    14 def i n o r d e r ( r o o t ) :
    15 in order ( root . l e f t )
    16 p r i n t ( r o o t . key )
    17 in order ( root . right )
    Delete

    I No child nodes?

    I 1 child node?

    I 2 child nodes?
    1 def g e t i t h ( r o o t , i ) :
    2 i f r o o t . l e f t == None and i == 0 :
    3 return root
    4
    5 s = root . l e f t . size
    6 i f s == i :
    7 return root
    8 elif s > i :
    9 return g e t i t h ( root . l e f t , i )
    10 else :
    11 return g e t i t h ( root . right , i − s − 1 )
    Balanced Binary Search Trees

    All BST functions are O(H)


    Best case H = log2 (N)
    Worst case H = N − 1

    If H = O(log (N))
    I All BST functions are O(log (N))

    Balanced tree:
    I Height of the tree is O(log (N))
    AVL Trees
    Height augmentation for node n
    I -1 if n == None
    I 1 + max(n.left.height, n.right.height)

    Balance augmentation for node n


    I n.right.height - n.left.height

    AVL Property:

    BST Property &

    ∀n : |n.balance| ≤ 1

    → root.height = O(log (N))


    Rotations

    You might also like