Trees_AVL.pdf
Document Details
Uploaded by IncredibleGalaxy1978
Camarines Sur Polytechnic Colleges
Tags
Full Transcript
class AVLNode: def __init__(self, data): self.left = None self.right = None self.data = data self.height = 1 insert(7) insert(7) insert(7) insert(7) insert(7) insert(7) insert(7) insert(7) insert(7) (1) NULL (...
class AVLNode: def __init__(self, data): self.left = None self.right = None self.data = data self.height = 1 insert(7) insert(7) insert(7) insert(7) insert(7) insert(7) insert(7) insert(7) insert(7) (1) NULL (-1) (0) insertNode(){ algorithm for inserting a node. update height of nodes. fixUp() } fixUp(){ start at the node inserted and travel up the tree: if an imbalance is found, check the four cases and do the appropriate rotation. update height of the nodes. } fixUp() rotation is made where the imbalance is found. fixUp(){ start at the node inserted and travel up the tree: if an imbalance is found, if pivot is left leaning and root is left leaning do a right rotation on root. update height of the nodes. } 2 1 0 0 0 insert(7) 3 2 0 1 0 0 insert(7) 2 1 1 0 0 0 insert(7) fixUp(){ start at the node inserted and travel up the tree: if an imbalance is found, if pivot is right leaning and root is right leaning do a left rotation on root. update height of the nodes. } 1 0 insert(21) 2 1 0 insert(21) 2 -1 NULL 1 0 insert(21) 1 0 0 insert(21) fixUp(){ start at the node inserted and travel up the tree: if an imbalance is found, if pivot is right leaning and root is left leaning do a left rotation on pivot. do a right rotation on root. update height of the nodes. } 2 1 1 0 0 insert(3) 3 2 1 1 0 0 insert(3) 3 2 1 1 -1 NULL 0 0 insert(3) 3 2 1 1 0 0 insert(3) 2 1 1 0 0 0 insert(3) fixUp(){ start at the node inserted and travel up the tree: if an imbalance is found, if pivot is left leaning and root is right leaning do a right rotation on pivot. do a left rotation on root. update height of the nodes. } 3 1 2 0 0 0 1 0 0 insert(18) 4 1 3 0 0 0 2 1 0 0 insert(18) 4 1 3 0 0 0 2 1 0 0 insert(18) 4 1 3 0 0 0 2 1 0 0 insert(18) 3 1 2 0 0 1 1 0 0 0 insert(18) insert(1) insert(2) insert(3) insert(4) insert(5) insert(6) insert(7) insert(15) insert(14) insert(13) insert(1) insert(1) insert(2) insert(3) insert(4) insert(5) insert(6) insert(7) insert(15) insert(14) insert(13) insert(2) insert(1) insert(2) insert(3) insert(4) insert(5) insert(6) insert(7) insert(15) insert(14) insert(13) insert(3) insert(1) insert(2) insert(3) insert(4) insert(5) insert(6) insert(7) insert(15) insert(14) insert(13) insert(3) insert(1) insert(2) insert(3) insert(4) insert(5) insert(6) insert(7) insert(15) insert(14) insert(13) insert(3) insert(1) insert(2) insert(3) insert(4) insert(5) insert(6) insert(7) insert(15) insert(14) insert(13) insert(4) insert(1) insert(2) insert(3) insert(4) insert(5) insert(6) insert(7) insert(15) insert(14) insert(13) insert(5) insert(1) insert(2) insert(3) insert(4) insert(5) insert(6) insert(7) insert(15) insert(14) insert(13) insert(5) insert(1) insert(2) insert(3) insert(4) insert(5) insert(6) insert(7) insert(15) insert(14) insert(13) insert(5) insert(1) insert(2) insert(3) insert(4) insert(5) insert(6) insert(7) insert(15) insert(14) insert(13) insert(6) insert(1) insert(2) insert(3) insert(4) insert(5) insert(6) insert(7) insert(15) insert(14) insert(13) insert(6) insert(1) insert(2) insert(3) insert(4) insert(5) insert(6) insert(7) insert(15) insert(14) insert(13) insert(7) insert(1) insert(2) insert(3) insert(4) insert(5) insert(6) insert(7) insert(15) insert(14) insert(13) insert(7) insert(1) insert(2) insert(3) insert(4) insert(5) insert(6) insert(7) insert(15) insert(14) insert(13) insert(7) insert(1) insert(2) insert(3) insert(4) insert(5) insert(6) insert(7) insert(15) insert(14) insert(13) insert(15) insert(1) insert(2) insert(3) insert(4) insert(5) insert(6) insert(7) insert(15) insert(14) insert(13) insert(14) insert(1) insert(2) insert(3) insert(4) insert(5) insert(6) insert(7) insert(15) insert(14) insert(13) insert(14) insert(1) insert(2) insert(3) insert(4) insert(5) insert(6) insert(7) insert(15) insert(14) insert(13) insert(14) insert(1) insert(2) insert(3) insert(4) insert(5) insert(6) insert(7) insert(15) insert(14) insert(13) insert(14) insert(1) insert(2) insert(3) insert(4) insert(5) insert(6) insert(7) insert(15) insert(14) insert(13) insert(14) insert(1) insert(2) insert(3) insert(4) insert(5) insert(6) insert(7) insert(15) insert(14) insert(13) insert(13) insert(1) insert(2) insert(3) insert(4) insert(5) insert(6) insert(7) insert(15) insert(14) insert(13) insert(13) insert(1) insert(2) insert(3) insert(4) insert(5) insert(6) insert(7) insert(15) insert(14) insert(13) insert(13) insert(1) insert(2) insert(3) insert(4) insert(5) insert(6) insert(7) insert(15) insert(14) insert(13) insert(13) insert(1) insert(2) insert(3) insert(4) insert(5) insert(6) insert(7) insert(15) insert(14) insert(13) insert(13) insert(1) insert(2) insert(3) insert(4) insert(5) insert(6) insert(7) insert(15) insert(14) insert(13) deleteNode(){ if the node is a leaf, simply remove it. if the node is not a leaf, replace it with either its predecessor or its successor and recursively delete that node. perform fixup() (the insert fixup) on the parent of the repacement up to the root. } delete(15) delete(2) delete(7) delete(14) delete(5) delete(15) delete(2) delete(7) delete(14) delete(5) delete(15) delete(15) delete(2) delete(7) delete(14) delete(5) delete(15) delete(15) delete(2) delete(7) delete(14) delete(5) delete(2) delete(15) delete(2) delete(7) delete(14) delete(5) delete(2) delete(15) delete(2) delete(7) delete(14) delete(5) delete(7) delete(15) delete(2) delete(7) delete(14) delete(5) delete(7) delete(15) delete(2) delete(7) delete(14) delete(5) delete(14) delete(15) delete(2) delete(7) delete(14) delete(5) delete(14) delete(15) delete(2) delete(7) delete(14) delete(5) delete(14) delete(15) delete(2) delete(7) delete(14) delete(5) delete(5) delete(15) delete(2) delete(7) delete(14) delete(5) delete(5) delete(15) delete(2) delete(7) delete(14) delete(5) delete(15) delete(2) delete(7) delete(14) delete(5)
