Topic 5-3 Balanced BST
Data Structures
Copyright By PowCoder代写 加微信 powcoder
Balanced BST
Question: What happens if we insert the following values into a binary search tree?
5, 10, 7, 9, 8, 20, 18, 17, 16, 15, 14, 13, 12, 11
We get an unbalanced tree!
There are two popular Balanced Binary Search Tree: AVL Tree and Red- .
Both offers O(log N) search time.
AVL Tree more suitable for search.
Red- for insertion-deletion.
Red- more popular.
Today’s Goal
Properties
Insertion and Rotations
Implementation
What is a AVL tree
An AVL tree is a binary search tree that uses modified add and remove operations to stay balanced as its elements change.
An AVL tree maintains a “balance factor”
in each node of 0, 1, or -1.
Balance Factor, for a tree node T is the height of T’s right subtree minus height of T’s left subtree.
BF(T) = Height(T.right) – Height(T.left)
At most 1 difference between the height of right subtree and left subtree
Note: some textbooks use “right-left”, some use “left-right”.
5)-> Height Invariant The number of black nodes on every path from the root to each leaf is the same. We call this the black height of the tree
Recall: Height of Node
Height of node – The height of a node is the number of edges on the longest downward path between that node and a leaf.
Leaf has height of 0.
is the number of edges of the path to E, NOT to G. And its height is 3.
Height of Tree
Height of tree –The height of a tree is the number of edges on the longest downward path between the root and a leaf.
So, the height of a tree is the height of its root.
The height of the root is 3
The height of the root is 1
Compute Balance Factor
BF(T) = Height(T.right) – Height(T.left)
Height is not defined for empty tree, here we denote height(empty tree) = -1
Revisit: Big O of BST Search
In the average BST with N values, how many steps are required to find our value?
In the worst case BST with
N values, how many steps are required find our value?
50% eliminated!
50% eliminated!
50% eliminated!
50% eliminated!
log2(N) steps
The height of an AVL tree with N nodes is O(log N)
Let us bound n(h): the minimum (why?) number of nodes of an AVL tree of height h.
We can find: n(0) = 1 n(1) = 2 n(2) = 4
A proof by induction
Invalid AVL!
See robin’s note
The height of an AVL tree with N nodes is O(log N)
Let us bound n(h): the minimum number of nodes of an AVL tree of height h.
We can find: n(0) = 1 n(1) = 2 n(2) = 4
For n>2, an AVL tree (minimum case) of height h contains the root node, one AVL subtree of height h-1 and another of height h-2.
That is, n(h) = 1+ n(h-1) + n(h-2)
A proof by induction
Minimum number of nodes in a tree with height h
That is, n(h) = 1+ n(h-1) + n(h-2)
You can check what happens if you remove any node from T1->Tn, could they still be valid AVL tree with height of h ?
T3(left subtree)
(right subtree)
The height of an AVL tree with N nodes is O(log N)
Let us bound n(h): the minimum number of nodes of an AVL tree of height h.
We can find: n(0) = 1, n(1) = 2, n(2) = 4
For n>2, an AVL tree of height h contains the root node, one AVL subtree of height n-1 and another of height n-2.
That is, n(h) = 1+ n(h-1) + n(h-2)
Knowing n(h-1) > n(h-2), we get n(h) > 2*n(h-2):
n(h) > 2*n(h-2), n(h) > 4*n(h-4) … n(h) > 2i*n(h-2i)
A proof by induction
See robin’s note
The height of an AVL tree with N nodes is O(log N)
n(h) > 2i n(h-2i)
Let’s find an i so that h-2i is guaranteed to be 1 or 2, since this would guarantee that n(h-2i) ≥ 1.
I claim i = ⌈h/2⌉-1 works.
If h is even h-2i = h-(h-2) = 2
If h is odd h-2i = h – (2⌈h/2⌉-2) = h – ((h+1)-2) = 1
Now we plug this value of i
n(h) > 2in(h-2i)
= 2⌈h/2⌉-1n(h-2i)
≥ 2⌈h/2⌉-1(1)
≥ 2(h/2)-1
Taking logs gives log(n(h)) > (h/2)-1 or
h < 2log(n(h))+2
h is O(log N)
Height of node
Height(X) = max(height(X.left), height(X.right))+1
Tracking subtree height
Many of the AVL tree operations depend on height.
Height can be computed recursively by walking the tree; too slow.
Instead, each node can keep track of its subtree height as a field:
left/right
Class TreeNode:
TreeNode left
TreeNode right
AVL tree: Insert one node
For all AVL operations, we assume the tree was balanced before the operation began.
Adding a new node begins the same as with a typical BST，
But adding this new node may unbalance the tree by 1:
AVL_tree.insert(49)
Height(55.right)-Height(55.left)
-> invalid AVL tree!
If a node has become out of balanced in a given direction, rotate it in the opposite direction.
Remember to update the height attribute for touched node!
rotation: A swap between parent and left or right child, maintaining proper BST ordering
4 Imbalanced Cases
Consider the lowest node k that has now become unbalanced.
The new offending node could be in one of the four following grandchild subtrees, relative to k:
1) Left-Left(LL),
2) Left-Right (LR),
3) Right-Left (RL),
4) Right-Right(RR)
Left-Left or Right-Right Imbalance
Insert(small)
Insert(middle)
Insert(tall)
#1 Imbalance caused by either:
Insert into left child’s left subtree
Insert into right child’s right subtree
But, let’s start over…
Insert [SMALL]
Now, [MIDDLE].
Now, [TALL].
Is this tree balanced?
Who do we need at the root?
Alright, let’s pull er up.
Single Rotation
Basic operation used in AVL trees:
A right child could legally have its parent as its left child.
This is the basic operation we’ll use in AVL trees.
Since this is a right child, it could legally have the parent as its left child.
When we finish the rotation, we have a balanced tree!
General Case #1
Note: imbalance is left-left
Here’s the general form of this.
We insert into the red tree. That ups the three heights on the left.
Basically, you just need to pull up on the child.
Then, ensure that everything falls in place as legal subtrees of the nodes.
Notice, though, the height of this subtree is the same as it was before the insert into the red tree.
So, we don’t have to worry about ancestors of the subtree becoming imbalanced; we can just stop here!
Single Rotation
Fixes Case #1 Imbalance
Height of left subtree same as it was before insert!
Height of all ancestors unchanged
We can stop here!
Here’s the general form of this.
We insert into the red tree. That ups the three heights on the left.
Basically, you just need to pull up on the child.
Then, ensure that everything falls in place as legal subtrees of the nodes.
Notice, though, the height of this subtree is the same as it was before the insert into the red tree.
So, we don’t have to worry about ancestors of the subtree becoming imbalanced; we can just stop here!
Bad Insert Case #2:
Left-Right or Right-Left Imbalance
Insert(small)
Insert(tall)
Insert(middle)
Will a single rotation fix this?
BC#2 Imbalance caused by either:
Insert into left child’s right subtree
Insert into right child’s left subtree
There’s another bad case, though.
What if we insert:
Now, is the tree imbalanced?
Will a single rotation fix it?
(Try it by bringing up tall; doesn’t work!)
Double Rotation
Let’s try two single rotations, starting a bit lower down.
First, we rotate up middle.
Then, we rotate up middle again!
Is the new tree balanced?
General Bad Case #2
Note: imbalance is left-right
Double Rotation
Fixes Case #2 Imbalance
Initially: insert into either X or Y unbalances tree (root balance goes to 2 or -2)
“Zig zag” to pull up c – restores root height to h+1, left subtree height to h
Here’s the general form of this.
Notice that the difference here is that we zigged one way than zagged the other to find the problem.
We don’t really know or care which of X or Y was inserted into, but one of them was.
To fix it, we pull c all the way up.
Then, put a, b, and the subtrees beneath it in the reasonable manner.
The height is still the same at the end!
AVL Insert Algorithm
Find spot for value
Insert new node
Search back up looking for imbalance (e.g, a )
If there is an imbalance:
case #1: Perform single rotation
case #2: Perform double rotation
Done! Why?
Those two cases (along with their mirror images) are the only four that can happen!
So, here’s our insert algorithm.
We just hang the node.
Search for a spot where there’s imbalance.
If there is, fix it (according to the shape of the imbalance).
And then we’re done; there can only be one problem!
Insert 15, 20, 24, 10, 13, 7, 30, 36, 25 into an AVL tree
Sample 1: insert 15, 20, 24, 10, 13, 7, 30, 36, 25 into an AVL tree
Step 1: detect unbalanced node
15 is the first unbalanced node, thus set target nodes, i.e., 15, 20, 24
Step 2: what is the type of this case?
Right-right case (the problem of 15 is introduced as we add 24 as the right child of 20, which is the right child of 15)
Step 3: what kind of rotation should we perform?
Left rotation
Step 4: any subtrees? None, 20 becomes the new root, 15 and 24 are the left and right child.
insert 10, still balanced
15, 20, 24, 10, 13, 7, 30, 36, 25
Step 1: detect unbalanced node
15 is the first unbalanced node, thus set target nodes, i.e., 15, 10, 13
Step 2: what is the type of this case?
Left-right case (the problem of 15 is introduced as we add 13 as the right child of 10, which is the left child of 15)
Step 3: what kind of rotation should we perform?
Double ration
Step 4: any subtrees? None, then rearrange three target nodes.
13 becomes the new root, 10 and 15 are the left and right child.
15, 20, 24, 10, 13, 7, 30, 36, 25
Step 1: detect unbalanced node
20 is the first unbalanced node, thus set target nodes, i.e., 20, 13, 10
Step 2: what is the type of this case?
Left-left case (the problem of 20 is introduced as we add 7 to 10 which is the left child of 13, which is the left child of 20).
Step 3: what kind of rotation should we perform?
Right ration, among 10, 13, 20, 13 becomes the new root, 10 and 20 are the left and right child.
Step 4: any subtrees? Yes,
15, 20, 24, 10, 13, 7, 30, 36, 25
Step 4: any subtrees? Yes,
Subtree A: 24
Subtree B: 15
Subtree C: None
Subtree D: 7
How to rearrange ABCD?
15, 20, 24, 10, 13, 7, 30, 36, 25
Step 4: any subtrees? Yes,
Subtree A: 24
Subtree B: 15
Subtree C: None
Subtree D: 7
How to rearrange ABCD?
fix the positions of three target nodes
Then subtree B should be the left child of node 20.
15, 20, 24, 10, 13, 7, 30, 36, 25
Step 1: detect unbalanced node
24 is the first unbalanced node, thus set target nodes, i.e., 24,30,36
Step 2: what is the type of this case?
Right-right case (the problem of 24 is introduced as we add 36 as the right child of 30, which is the right child of 24)
Step 3: what kind of rotation should we perform?
left ration
Step 4: any subtrees? None, fix positions of three target nodes. 30 becomes the new root, 24 and 36 are the left and right child.
15, 20, 24, 10, 13, 7, 30, 36, 25
Step 1: detect unbalanced node
20 is the first unbalanced node, thus set target nodes, i.e., 20, 30, 24
Step 2: what is the type of this case?
Right-left case (the problem of 20 is introduced as we add 25 to 24 which is the left child of 30, which is the right child of 30).
Step 3: what kind of rotation should we perform?
Double ration, among 20, 30, 24, 24 becomes the new root, 20 and 30 are the left and right child.
Step 4: any subtrees? Yes,
Subtree A: 15
Subtree B: 36
Subtree C: 25
Subtree D: None
How to rearrange ABCD?
Step 4: any subtrees? Yes,
How to rearrange ABCD?
->Subtree C should be the left child of node 30.
Double rotation, fix new positions for 20,24,30 then
Subtree A: 15
Subtree B: 36
Subtree C: 25
Subtree D: None
How to update height?
class AVL_Tree(object):
# Recursive function to insert key in subtree rooted with node and returns new root of subtree.
def insert(self, root, key):
# Step 1 – Perform normal BST
if not root:
return TreeNode(key)
elif key < root.val:
root.left = self.insert(root.left, key)
root.right = self.insert(root.right, key)
# Step 2 - Update the height of the ancestor node
root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right))
# Step 3 - Get the balance factor
balance = self.getBalance(root)
# Step 4 - If the node is unbalanced, then try out the 4 cases
return root
https://www.geeksforgeeks.org/avl-tree-set-1-insertion/
# Generic tree node class
class TreeNode(object):
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.height = 0
# Case 1 - Left Left
if balance < -1 and key < root.left.val:
return self.rightRotate(root)
# Case 2 - Right Right
if balance > 1 and key > root.right.val:
return self.leftRotate(root)
# Case 3 – Left Right
if balance < -1 and key > root.left.val:
root.left = self.leftRotate(root.left)
return self.rightRotate(root)
# Case 4 – Right Left
if balance > 1 and key < root.right.val:
root.right = self.rightRotate(root.right)
return self.leftRotate(root)
If the node is unbalanced, then try out the 4 cases
Left and right rotate
def leftRotate(self, A):
B = A.right
beta = B.left
# Perform rotation
B.left = A
A.right = beta
# Update heights
A.height = 1 + max(self.getHeight(A.left),
self.getHeight(A.right))
B.height = 1 + max(self.getHeight(B.left),
self.getHeight(B.right))
# Return the new root
def rightRotate(self, B):
beta = A.right
# Perform rotation
A.right = B
B.left = beta
# Update heights
B.height = 1 + max(self.getHeight(B.left),
self.getHeight(B.right))
A.height = 1 + max(self.getHeight(A.left),
self.getHeight(A.right))
# Return the new root
B is the unbalanced node
Given the AVL tree below, answer the following four questions:
(a)What is the balance factor for the following nodes in the AVL
tree: 14, 21, 35, and 41?
(b)Show the AVL tree after inserting 3 into the provided tree.
(c)Show the AVL tree after inserting 36 into your answer from
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com