OutlineLast time:• Tree Terminology• Tree Traversal• N-ary TreeToday:• Binary Search Tree (BST)• Binary Space Partition (BSP) Tree• Heap and Priority QueueSugih Jamin ([email protected])Binary Search Tree (BST)What is the difference between a binary tree and a binary search tree?Definition of BST:• all values in Tlis < value on root• all values in Tris > value on root• where ‘<’ and ‘>’ can be user definedSearch algorithm, search for key starting from T.root:• if T.root is null, not found• if key == T.root.value found• if key > T.root.value search T.Tr• if key < T.root.value search T.TlSugih Jamin ([email protected])BST Search Time ComplexityAverage-case search time:successful unsuccessfullinked list:hash table:BST:Expressed in terms of depth (or height),successful search on BST takes O( )unsuccessful search takes O( )Worst-case successful search time on BST: O( )Worst-case unsuccessful search time on BST: O( )Sugih Jamin ([email protected])BST InsertionInsertion of new element:• starting from root, find “appropriate” place for new• insert new• example: build a BST consisting of k, b, m, f, v, z, o, p, a• will the “appropriate” place always be a leaf node?Given a BST, where are the smallest and largest elements?How do you remove an element from a BST?Remove z, b, m from the above BSTSugih Jamin ([email protected])BST RemovalAfter removal of a node, tree must remain a BSTRemoval of an element elt:• search for elt• if elt is a leaf node, just remove it• what if elt is non-leaf?o swap with either the smallest element of Tror the largest element of Tlo if elt is now leaf, remove ito if non-leaf, it should have only one child,replace parent’s pointer to this node withpointer to child and remove the nodeSugih Jamin ([email protected])Problem: Collision DetectionBlue wants to go to object e. Which objects are in the way?afimdecbhkjgnlSugih Jamin ([email protected])Binary Space Partitioning (BSP) TreeWhat is a BSP?A spatial data structure used to help organize geometry in n-dimensionalspaceRoughly: a BST that sorts objects in space by their coordinatesUsed to speed up queries about whether geometric objects overlap orabout the spatial ordering of geometric objectsExample uses:• computer graphics: whether an object is behind another, to determinedisplay• robot motion planning: whether there is obstruction in a path• computer games: collision detection• in general: occlusion culling and collision detectionSugih Jamin ([email protected])BSP Partitions SpaceBlue wants to go to object e. Which objects are in the way?aimdecbhkjgnlx=3014x=452y=30x=523BAECDfSugih Jamin ([email protected])Creating a BSP TreeAlgorithm:• use a plane to divide space in 2• objects to the left of plane are put in Tl• objects to the right of plane are put in Tr• repeat for Tland TrTypes of BSP:• polygon-aligned: pick existing objects (polygons) in space as dividingplanes• axis-aligned: dividing planes placed along x and y axesSugih Jamin ([email protected])BSP Creationaimdecbhkjgnlx=3014x=452y=30x=523BAECDf1x=30Aa, b , gh, i, j, k2y=30Eln3x=52BdDcem4y=45CfSugih Jamin ([email protected])BSP Found Colliding ObjectBlue wants to go to object e. Which objects are in the way?aimdecbhkjgnlx=3014x=452y=30x=523BAECDf1x=30Aa, b , gh, i, j, k2y=30Eln3x=52BdDcem4y=45CfNext check for collision against items ’c’ and ’m’Sugih Jamin ([email protected])BSP and Occlusion CullingWhat can Blue see?aimdecbhkjgnlx=3014x=452y=30x=523BAECDf1x=30Aa, b , gh, i, j, k2y=30Eln3x=52BdDcem4y=45CfSugih Jamin ([email protected])MinHeapMinHeap: an ordered tree with the following properties:• every subtree of T is a heap• the key in the root of T is ≤ the key in every subtree of TBinary heap: must be a complete binary tree (see Preiss Fig. 11.4,note that it is not a representation of the ternary tree in Fig. 11.3)A complete binary tree can be efficiently stored as an arraySugih Jamin ([email protected])Binary MinHeapfindmin(): time complexity O( )enqueue(): must maintain binary heap properties (Fig. 7.6 GTM)• insert new item as the rightmost leaf of the complete tree• percolate up: swap new with parent as long as (new’s key < parent’skey)time complexity: O( )dequeuemin(): (Fig. 7.7 GTM)• remove root• move rightmost item (elt) of lowest level to root• percolate down: swap elt with children with the smallest key untilelt’s key is smaller than children’s or elt is a leaf node.• how to find the rightmost item?time complexity: O( )Sugih Jamin ([email protected])Priority QueuePriority Queue: a list of items with prioritiesExamples:• shortest job first print or cpu queue• simulation of events (in games, for example)• scheduling in generalOnly need the following operations:• enqueue()• findmin() (or findmax())• dequeuemin() (or dequeuemax())Implementation: as a sorted linked list, enqueue() takes O( )What data structure would be good to implement a priority queue?Sugih Jamin ([email protected])Discrete Event SimulationsMost common operations in discrete event simulations(for example, video games):• dequeuemin(): O(log N) for all kinds of heap• enqueue(): Θ(log N) for all kinds of heap except FibHeap (Θ(1))• “hold”, dequeuemin() followed immediately by enqueue():O(log N) for all kinds of heapSugih Jamin