Transcript Binary Search Trees

Computer Sciences Department
1
Binary Search Trees
Chapter 12
Computer Sciences Department
3
Objectives




The idea of Binary Search Tree
Operations of Binary Search Tree
The run time of Binary Search Tree
Analysis of Binary Search Tree
Computer Sciences Department
4
Search trees -1
 Search trees are data structures that support many
dynamic-set
operations,
including
SEARCH,
MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR,
INSERT, and DELETE.
Computer Sciences Department
5
Search trees - 2
 Basic operations on a binary search tree take time
proportional to the height of the tree.
 For a complete binary tree with n nodes, such operations
run in” O(lg n) = height” worst-case time.
 If the tree is a linear chain “ linear time algorithm” of n
nodes, however, the same operations take O (n) worstcase time (the process will always cover all the nodes = O
(n)).
 The height of the Binary Search Tree equals the number of
links from the root node to the deepest node.
Computer Sciences Department
6
What is a binary tree?
 Property 1: each node can have up to two successor nodes
(children)
 The predecessor node of a node is called its parent
 The "beginning" node is called the root (no parent)
 A node without children is called a leaf
 Property 2: a unique path exists from the root to every other
node
Computer Sciences Department
7
What is a binary search tree?
 a tree can be represented by a linked data structure in
which each node is an object.
Computer Sciences Department
8
key field - 1
 In addition to a key field and satellite data, each node
contains fields left, right, and p that point to the
nodes corresponding to its left child, its right child,
and its parent, respectively.
 If a child or the parent is missing, the appropriate
field contains the value NIL. The root node is the only
node in the tree whose parent field is NIL.
Computer Sciences Department
9
key field -2
 The keys in a binary search tree are always stored in such a
way as to satisfy the binary-search-tree property:
Computer Sciences Department
10
Computer Sciences Department
11
Inorder, preorder, and postorder
 The binary-search-tree property allows us to print out all
the keys in a binary search tree in sorted order by a simple
recursive algorithm, called an inorder tree walk. This
algorithm is so named because the key of the root of a
subtree is printed between the values in its left subtree and
those in its right subtree.
 Similarly, a preorder tree walk prints the root before the
values in either subtree, and
 A postorder tree walk prints the root after the values in its
subtrees.
 It takes O(n) time to walk a tree of n nodes
Computer Sciences Department
12
It takes O(n) time to walk a tree of n nodes
Computer Sciences Department
13
Computer Sciences Department
14
It takes O(n) time to walk a tree of n nodes
Computer Sciences Department
15
It takes O(n) time to walk a tree of n nodes
Computer Sciences Department
16
It takes O(n) time to walk a tree of n nodes
Computer Sciences Department
17
It takes O(n) time to walk a tree of n nodes
Computer Sciences Department
18
It takes O(n) time to walk a tree of n nodes
INORDER-TREE-WALK procedure
 Procedure to print all the elements in a binary search
tree T , we call INORDER-TREE-WALK(root[T ]).
Computer Sciences Department
19
Computer Sciences Department
20
Querying a binary search tree
Computer Sciences Department
21
Search the BST x for a value k
To search for the key 13 in the tree, we follow
the path 15 → 6 → 7 → 13 from the root.
Computer Sciences Department
22
Note: Search operation takes time O(h)
“proportional to the height of the tree”,
where h is the height of a BST
Minimum and maximum
Computer Sciences Department
Note: max and min operations take time O(h)
“proportional to the height of the tree”,
23
where
h is the height of a BST
Successor and predecessor
 Given a node in a binary search tree, it is sometimes
important to be able to find its successor in the
sorted order determined by an in-order tree walk. If
all keys are distinct, the successor of a node x is the
node with the smallest key greater than key[x].
Computer Sciences Department
24
Computer Sciences Department
25
Computer Sciences Department
26
Computer Sciences Department
27
- If the right subtree of node x is nonempty, then the successor of x is just the
leftmost node in the right subtree,
- If the right subtree of node x is empty and x has a successor y, then y is the
lowest ancestor of x whose left child is also an ancestor of x.
- the successor of the node with key 15 in Figure 12.2 is the node with key 17
- the successor of the node with key 13 is the node with key 15.
Computer Sciences Department
28
Insertion and deletion
Computer Sciences Department
29
Insertion and deletion operations take
time proportional to the height of the
tree O(h)
Deletion (in lab.)
Computer Sciences Department
30
Computer Sciences Department
31
Randomly built binary search trees
Self study
Computer Sciences Department
32
Conclusion -1
 Binary search trees come in many shapes. The shape of the
tree determines the efficiency of its operations.
 Logarithmic time is generally much faster than linear time.
For example, for n = 1,000,000: log2 n = 20.
 Using binary search trees to represent sets: insert, search, remove,
…………… O(h) = O(log2 n)
 Using linear data structures to represent sets: insert, search,
remove, …………… O(n)
 Balanced BTS:
 Easier insertion/deletion
 Running time = O(log2 n)
Computer Sciences Department
33
Conclusion -2
Computer Sciences Department
34