一些树的结构备忘NULL 博文链接：https://richyzhang.iteye.com/blo

文件名称: 一些树的结构备忘

所属分类: 其它

开发工具:

文件大小: 1mb

下载次数: 0

上传时间: 2019-07-29

提供者: weixin_********

下载 (1mb)

不能下载？报告错误

详细说明：NULL 博文链接：https://richyzhang.iteye.com/blog/803019Binary Search and AVL Trees Lawrence M. brown Search Algorithm: Tree Search(k, Input: A search key, k, and a node, v, of a binary search tree, T' Output: The node storing the key, k, or an external node(after all internal nodes with keys k and before all internal nodes with keys > k) if v is an external node then return v find(25) find(76) ifk=key(ν)then∥ node found 44 return y 88 else if k< key( v)then 65 return Tree Search( k, Tleft Child(v)) 28 82 else∥/k>key(v) 76 return Tree Search( k, Tright Child(v)) 20 For this algorithm, the returned node requires one final test for an external node( v is External) 25 September, 1999 3 Binary Search and AVL Trees Lawrence M. brown Insert into a Binary search Tree Algorithm: insert( key-element pair Start by calling Tree Seach(k, T root)on T. Let w be the returned node If w is an external node, then no Item with key k is stored in T Call T.expandexternal( w) Store new Item(k, e)at node(position)w If w is an internal node, then another Item with key k is stored at w Call TreeSearch( k, rightChild( w))and apply the algorithm to the returned node. Duplicates tend to the right 25 September, 1999 Binary Search and AVL Trees Lawrence M. brown Insert into a Binary Search Tree Example Insert Item with key 78 44 28 8 80 8D 78 expandExternalo A new Item will always be added at the bottom"of the search tree, T' Each node visit costs O(1), thus, in the worst case, insert runs in O(h) the height of the tree, t 25 September, 1999 Binary Search and AVL Trees Lawrence M. brown Removal from a Binary Search Tree TreeScarch (k, T root()is called to locate the node w with key k Two complicated situations may arise Case I: The node w is internal with a single leaf child z Call removeAbove External(z)to replace w with the sibling o 44 、双 82 80 80 78 25 September, 1999 6 Binary Search and AVL Trees Lawrence M. brown Removal from a Binary Search Tree Case l: both children of w are internal nodes Save the element stored at w into a temporary variable Find the first internal node, y, in an inorder traversal of the right subtree of w Replace the contents of w with the contents of y Call remove Above External(x)on the left child of Return the element previously stored in w 44 88 76 29 54 82 76 y (a) 25 September, 1999 Binary Search and AVL Trees Lawrence M. brown Time Complexity of Binary Search Tree Searching, insertion and removal of a node in a binary search Tree is O(h), where h is the of the tree height of the tree is n, then the worst-case running time for Insertion removal is o(n)--no better than a To prevent the worst-case running time, a re-balancing scheme is needed to yield a tree that maintains the smallest possible height 25 September, 1999 8 Binary Search and AVL Trees Lawrence M. brown AVL Freest An AVL Tree is a binary tree such that for every internal node v of T, the heights of the children of v can differ by at most 1 44 17 78 32 50 88 48) 62 Every of an avl tree is an av tree del'son el’ skii and l 25 September, 1999 Binary Search and AVL Trees Lawrence M. brown insertion in an avl tree a binary search tree T is balanced if for every node v, the height of v's children differ by at most one Inserting a node into an aVL tree involves performing an expandExternal( w)on T, which may change the height of some nodes in T If an insertion causes T to become unbalanced, then travel up the tree from the newly created node, w, until the first node is reached, x, that has an unbalanced grandparent, z. Note that x could be equal to w Height(y)=Height( sibling (y))+ 2 2 x → Expand external at w 25 September, 1999 10

(系统自动生成,下载前可以参看下载内容)