Scribd Logo
Upload

Welcome to Scribd!

  • 294 views

    BST PDF

    Uploaded by

    Andrew Lee
    Binary search trees are binary trees where the left child of each node is less than or equal to the parent node and the right child is greater than the parent. The height of an unbalanced binary search tree can range from log2n to n, affecting runtimes of algorithms. Common operations on binary search trees like search, insert, and delete have O(log n) time complexity on average but can be O(n) in the worst case. The document provides details on how to implement various tree traversal and node selection operations.

    Copyright:

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

    BST PDF

    Uploaded by

    Andrew Lee
    294 views2 pages
    Binary search trees are binary trees where the left child of each node is less than or equal to the parent node and the right child is greater than the parent. The height of an unbalanced binary search tree can range from log2n to n, affecting runtimes of algorithms. Common operations on binary search trees like search, insert, and delete have O(log n) time complexity on average but can be O(n) in the worst case. The document provides details on how to implement various tree traversal and node selection operations.

    Original Title

    bst.pdf

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Binary search trees are binary trees where the left child of each node is less than or equal to the parent node and the right child is greater than the parent. The height of an unbalanced binary search tree can range from log2n to n, affecting runtimes of algorithms. Common operations on binary search trees like search, insert, and delete have O(log n) time complexity on average but can be O(n) in the worst case. The document provides details on how to implement various tree traversal and node selection operations.

    Copyright:

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

    BST PDF

    Uploaded by

    Andrew Lee
    Binary search trees are binary trees where the left child of each node is less than or equal to the parent node and the right child is greater than the parent. The height of an unbalanced binary search tree can range from log2n to n, affecting runtimes of algorithms. Common operations on binary search trees like search, insert, and delete have O(log n) time complexity on average but can be O(n) in the worst case. The document provides details on how to implement various tree traversal and node selection operations.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 2

    Binary Search Trees

    Binary Search Trees

    Binary search trees are binary trees that satisfies the search tree property
    that left children are less than or equal to the parent and right children
    are greater than the parent. Note that because root choice is arbitrary, the
    height of an unbalanced BST can be anywhere from log2 n n, which
    means any algorithms operating on binary search trees have to take into
    account average-case and worst-case runtimes.
    Operation
    Select
    Search
    Min/Max
    Pred-/Succ-essor
    Rank
    Output
    Insert
    Delete

    Time
    O(log n)
    O(log n)
    O(log n)
    O(log n)
    O(log n)
    O(n)
    O(log n)
    O(log n)

    Operations
    Minimum

    Traverse the tree going left every time until a leaf node.

    Maximum

    Traverse the tree going right every time until a leaf node.

    Predecessor Called on node k, if k has a successor, return max(left).


    Otherwise, follow parent pointers until reaching a node where key <= cur.
    Successor Called on node k, if k has a successor, return min(right).
    Otherwise, follow parent pointers until reaching a node where key > cur.
    In-Order Traversal Recursively, at the parameter node, recurse on
    the left subtree, append the current node, then recurse on the right subtree.
    Selection and Rank To select the ith order statistic of a BST, first
    augment each node with a size field for the size of the subtree rooted at
    the node. The size of a node will be equal to one plus the sum of its child
    sizes.

    Binary Search Trees


    1

    def select ( x = root , rank ) :


    a = x . left . size
    if a >= i : select ( x . left , rank )
    if a < i - 1: select ( x . right , i - a - 1)
    if a == i - 1: return x

    Deletion
    1

    11

    Deleting a node can go three different ways.

    def delete ( key ) :


    k = find ( key )
    if k . left is NULL and k . right is NULL :
    remove ( k )
    else if k . left is NULL xor k . right is NULL :
    k = child
    remove ( old_k )
    else :
    l = predecessor ( k )
    swap (k , l )
    remove ( k )

    You might also like