Search trees

Search Trees

by dr. Cristian GuasguaCOMP 215

INDEX

Supported Operations

First Concepts

Unsuported Operations

BST

Search Trees vs Sorted Arrays

Height of the three

The Search Property

From the best case O(log n), when the tree is balanced, to the worst case O(n).

1. For every object x, objects in x’s left subtree have keys smaller than that of x.2. For every object x, objects in x’s right subtree have keys larger than that of x.

If you data is dynamic (you add or delete elements), then it is better to use a search tree.

+ INFO

01

Supported Operations

Lorem ipsum dolor sit amet

Search

Min/ Max

Predeccessor

Output Sorted

Successor

Select

Rank

Search

O(height)

1. Start at the root node.2. Repeatedly traverse left and right child pointers, as appropriate (left if k is less than the current node’s key, right if k is bigger). 3. Return a pointer to an object with key k (if found) or “none” (upon reaching a null pointer).

Exercises

MIN/MAX

O(height)

1. Start at the root node.2. Traverse left child pointers (right child pointers) as long as possible, until encountering a null pointer. 3. Return a pointer to the last object visited.

Exercises

Predecessor

O(height)

1. If x’s left subtree is non-empty, return the result of Max applied to this subtree.2. Otherwise, traverse parent pointers upward toward the root. If the traversal visits consecutive nodes y and z with y a right child of z, return a pointer to z. 3. Otherwise, report “none.”

TEAM

Exercises

Sucessor

O(height)

1. If x’s right subtree is non-empty, return the result of Min applied to this subtree.2. Otherwise, traverse parent pointers upward toward the root. If the traversal visits consecutive nodes y and z with y a right child of z, return a pointer to z. 3. Otherwise, report “none.”

Exercises

Output sorted

O(n)

1. Recursively call OutputSorted on the root’s left subtree.2. Output the object at the root. 3. Recursively call OutputSorted on the root’s right subtree.

Exercises

sELECT

O(height)

1. Start at the root and let j be the size of its left subtree. (If it has no left child pointer, then j = 0.)2. Ifi=j+1,returnapointertotheroot. 3. If i < j + 1, recursively compute the ith-smallest key in the left subtree. 4. If i > j+1, recursively compute the (ij1)th smallest key in the right subtree.18

Exercise

Exercise

rank

O(height)

If binary search finds an object with key k in the ith position of the array, or if it discovers that k is in between the keys of the objects in the ith and (i + 1)th positions, the correct answer is i. In Select and Rank we can use InOrder to add the information we need to augment the tree. If we apply InOrder Traversal, we get a O(n).

Exercises

02

UNSupported Operations

Lorem ipsum dolor sit amet

Insert

Delete

Insert

O(height)MODIFIES THE TREE

1. Start at the root node.2. Repeatedly traverse left and right child pointers, as appropriate (left if k is at most the current node’s key, right if it’s bigger), until a null pointer is encountered. 3. Replace the null pointer with one to the new object. Set the new node’s parent pointer to its parent, and its child pointers to null.

Exercises

delete

O(height)

1. Use Search to locate an object x with key k. (If no such object exists, halt.)2. If x has no children, delete x by setting the appropriate child pointer of x’s parent to null. (If x was the root, the new tree is empty.) 3. If x has one child, splice x out by rewiring the appropriate child pointer of x’s parent to x’s child, and the parent pointer of x’s child to x’s parent. (If x was the root, its child becomes the new root.) 4. Otherwise, swap x with the object in its left subtree that has the biggest key, and delete x from its new position (where it has at most one child).

Balanced Search Tree

The difference between any two subtrees is equal or less than 1

The difference between a linear and a logatimic running time is huge. Work on Insert and Delete functions Several types of balanced trees guarantee a height of log n

Rotations

We have left and right rotations

A way to rebalance a tree keeping the search property

Examples of BST

Two types of Balanced Search Trees

AVL Tree

Red/Black Tree

For any node in the tree, if the balance factor, or the difference in the heights of its subtrees (height of the right subtree minus height of the left subtree), is greater than 1 or less than –1, then the subtree with that node as the root needs to be rebalanced.

- The root is black.- All children of a red node are black. - Every path from the root to a leaf contains the same number of black nodes.

+ INFO

+ INFO

Thanks!