Data Structure - Binary Search Tree

AVL-Trees (Part 1)

AVL-Trees (Part 1)

AVLTrees/Slide2Data,a set ofelementsData structure,a structured set of elementslinear, tree, graph,Linear: a sequence of elements, array, linkedlistsTree:nested sets ofelements,...Binary treeBinary search treeHeap

AVL Trees / Slide 2 Data, a set of elements Data structure, a structured set of elements, linear, tree, graph, . Linear: a sequence of elements, array, linked lists Tree: nested sets of elements, . Binary tree Binary search tree Heap

AVLTrees/Slide3Binary Search TreeReviewof“insertion'and'deletion'forBSTSequentially insert3,2,1,4,5,6toanBSTTreeIf we continue to insert 7,16, 15,14,13,12, 11,10,8,9

AVL Trees / Slide 3 Binary Search Tree If we continue to insert 7, 16, 15, 14, 13, 12, 11, 10, 8, 9 Sequentially insert 3, 2, 1, 4, 5, 6 to an BST Tree Review of ‘insertion’ and ‘deletion’ for BST

AVLTrees/Slide4Balance Binary Search TreeWorst case height of binary search tree: N-1Insertion,deletion canbe O(N)in the worst caseWe want a tree with small heightHeight of a binary tree with N node is at least@(log N)Goal: keep the height of a binary search treeO(log N)Balanced binary search treesExamples:AVLtree,red-blacktree

AVL Trees / Slide 4 Balance Binary Search Tree Worst case height of binary search tree: N-1 Insertion, deletion can be O(N) in the worst case We want a tree with small height Height of a binary tree with N node is at least (log N) Goal: keep the height of a binary search tree O(log N) Balanced binary search trees Examples: AVL tree, red-black tree

AVLTrees/Slide5Balanced Tree?Suggestion 1: the left and right subtrees of root havethe sameheightDoesn'tforcethetreetobe shallowSuggestion 2:every node musthave left and rightsubtrees of the same heightOnlycompletebinarytreessatisfyToo rigidtobeusefulOur choice:for each node,the height of the left andrightsubtrees candifferatmost1

AVL Trees / Slide 5 Balanced Tree? Suggestion 1: the left and right subtrees of root have the same height Doesn’t force the tree to be shallow Suggestion 2: every node must have left and right subtrees of the same height Only complete binary trees satisfy Too rigid to be useful Our choice: for each node, the height of the left and right subtrees can differ at most 1