学习算法思想编程内功chapter

算法liuyubobobo二叉搜索树BinarySearchTree查找问题SearchingProblem查找问题是计算机中非常重要的基础问题二分查找法BinarySearch二分查找法BinarySearch对于有序数列，才能使用二分查找法（排序的作用）v<vv>v二分查找法BinarySearch二分查找法的思想在1946年提出。第一个没有bug的二分查找法在1962年才出现。操作：实现二分查找法二分查找法BinarySearch对于有序数列，才能使用二分查找法（排序的作用）v<vv>v使用递归地方式实现二分查找法递归实现通常思维起来更容易。递归在性能上会略差。练习：实现二分查找法的递归实现二分查找法的变种floor和ceilvfloorceilfloor和ceil41floorceil查找4243练习：实现floor和ceil二分搜索树BinarySearchTree二分搜索树的优势查找表的实现-字典数据结构key1value1key2value2key3value3key4value4key5value5key6value6key7value7key8value8key9value9二分搜索树的优势查找元素插入元素删除元素普通数组O(n)O(n)O(n)顺序数组O(logn)O(n)O(n)二分搜索树O(logn)O(logn)O(logn)二分搜索树的优势高效不仅可查找数据；还可以高效地插入，删除数据-动态维护数据可以方便地回答很多数据之间的关系问题：min,max,floor,ceil,rank,select二分搜索树BinarySearchTree28163013222942二分搜索树BinarySearchTree28163013222942二叉树每个节点的键值大于左孩子；每个节点的键值小于右孩子；以左右孩子为根的子树仍为二分搜索树7861534237二分搜索树BinarySearchTree41225815331317285066534237二分搜索树BinarySearchTree41225815331350不一定是完全二叉树操作：二分搜索树基础结构插入新的节点插入新节点insert5342374122581533135060插入新节点insert5342374122581533135060插入新节点insert534237412258153313506028插入新节点insert534237412258153313506028插入新节点insert534237412258153313506028插入新节点insert53423741225815331350602842插入新节点insert53423741225815331350602842插入新节点insert53423741225815331350602842插入新节点insert53423741225815331350602842操作：二分查找树插入新节点：insert练习：insert的非递归写法二分查找树的查找查找search53423741225815331350602842查找search53423741225815331350602842查找search53423741225815331350602842查找search53423741225815331350602842查找search53423741225815331350602859查找search53423741225815331350602859查找search53423741225815331350602859二分搜索树的包含contain和查找search同质操作：二分搜索树的包含contain操作：二分搜索树的查找search练习：search和contain的非递归写法操作：二分搜索树的速度优势二分搜索树的遍历二分搜索树的前中后序遍历前序遍历：先访问当前节点，再依次递归访问左右子树中序遍历：先递归访问左子树，再访问自身，再递归访问右子树后续遍历：先递归访问左右子树，再访问自身节点二分搜索树的遍历左子树右子树前序遍历二分搜索树的前序遍历28163013222942二分搜索树的前序遍历2816301322294228二分搜索树的前序遍历281630132229422816二分搜索树的前序遍历28163013222942281613二分搜索树的前序遍历28163013222942281613二分搜索树的前序遍历28163013222942281613二分搜索树的前序遍历28163013222942281613二分搜索树的前序遍历2816301322294228161322二分搜索树的前序遍历2816301322294228161322二分搜索树的前序遍历2816301322294228161322二分搜索树的前序遍历2816301322294228161322二分搜索树的前序遍历2816301322294228161322二分搜索树的前序遍历281630132229422816132230二分搜索树的前序遍历28163013222942281613223029二分搜索树的前序遍历28163013222942281613223029二分搜索树的前序遍历28163013222942281613223029二分搜索树的前序遍历28163013222942281613223029二分搜索树的前序遍历2816301322294228161322302942二分搜索树的前序遍历2816301322294228161322302942二分搜索树的前序遍历2816301322294228161322302942二分搜索树的前序遍历2816301322294228161322302942二分搜索树的前序遍历2816301322294228161322302942二分搜索树的前序遍历2816301322294228161322302942中序遍历二分搜索树的中序遍历28163013222942二分搜索树的中序遍历28163013222942二分搜索树的中序遍历28163013222942二分搜索树的中序遍历28163013222942二分搜索树的中序遍历2816301322294213二分搜索树的中序遍历2816301322294213二分搜索树的中序遍历281630132229421316二分搜索树的中序遍历281630132229421316二分搜索树的中序遍历28163013222942131622二分搜索树的中序遍历28163013222942131622二分搜索树的中序遍历28163013222942131622二分搜索树的中序遍历2816301322294213162228二分搜索树的中序遍历2816301322294213162228二分搜索树的中序遍历2816301322294213162228二分搜索树的中序遍历281630132229421316222829二分搜索树的中序遍历281630132229421316222829二分搜索树的中序遍历28163013222942131622282930二分搜索树的中序遍历28163013222942131622282930二分搜索树的中序遍历2816301322294213162228293042二分搜索树的中序遍历2816301322294213162228293042二分搜索树的中序遍历2816301322294213162228293042二分搜索树的中序遍历2816301322294213162228293042二分搜索树的中序遍历2816301322294213162228293042后序遍历二分搜索树的后序遍历28163013222942二分搜索树的后序遍历28163013222942二分搜索树的后序遍历28163013222942二分搜索树的后序遍历28163013222942二分搜索树的后序遍历28163013222942二分搜索树的后序遍历2816301322294213二分搜索树的后序遍历2816301322294213二分搜索树的后序遍历2816301322294213二分搜索树的后序遍历2816301322294213二分搜索树的后序遍历281630132229421322二分搜索树的后序遍历28163013222942132216二分搜索树的后序遍历28163013222942132216二分搜索树的后序遍历28163013222942132216二分搜索树的后序遍历28163013222942132216二分搜索树的后序遍历28163013222942132216二分搜索树的后序遍历2816301322294213221629二分搜索树的后序遍历2816301322294213221629二分搜索树的后序遍历2816301322294213221629二分搜索树的后序遍历2816301322294213221629二分搜索树的后序遍历281630132229421322162942二分搜索树的后序遍历28163013222942132216294230二分搜索树的后序遍历2816301322294213221629423028二分搜索树的后序遍历2816301322294213221629423028二分搜索树的遍历左子树右子树操作：二分搜索树的前中后序遍历后续遍历的一个应用：二叉树的销毁操作：二分搜索树的销毁层序遍历二分搜索树的深度优先遍历28163013222942二分搜索树的广度优先遍历（层序）28163013222942front28二分搜索树的广度优先遍历（层序）28163013222942front281630二分搜索树的广度优先遍历（层序）28163013222942front281630二分搜索树的广度优先遍历（层序）28163013222942front2816301322二分搜索树的广度优先遍历（层序）28163013222942front2816301322二分搜索树的广度优先遍历（层序）28163013222942front28163013222942二分搜索树的广度优先遍历（层序）28163013222942front28163013222942二分搜索树的广度优先遍历（层序）28163013222942front28163013222942二分搜索树的广度优先遍历（层序）28163013222942front28163013222942二分搜索树的广度优先遍历（层序）28163013222942front28163013222942二分搜索树的广度优先遍历（层序）28163013222942front28163013222942二分搜索树的广度优先遍历（层序）28163013222942front28163013222942二分搜索树的广度优先遍历（层序）28163013222942front28163013222942二分搜索树的广度优先遍历（层序）28163013222942front28163013222942二分搜索树的广度优先遍历（层序）28163013222942front28163013222942操作：二分搜索树的层序遍历二分搜索树的遍历-O(n)28163013222942二分搜索树删除节点从最简单的，删除二分搜索树的最小值和最大值开始二分搜索树的最小值和最大值28163013222942操作：求二分搜索树的最小值和最大值练习：求二分搜索树的最小值和最大值的非递归实现删除二分搜索树的最小值5342374122581533135013删除二分搜索树的最小值534237412258153350删除二分搜索树的最小值534237412258335022删除二分搜索树的最小值53424158373350删除二分搜索树的最大值635342374122581533135063删除二分搜索树的最大值53423741225815331350删除二分搜索树的最大值53423741225815331350删除二分搜索树的最大值37412258153313534250操作：删除二分搜索树的最小值和最大值练习：删除二分搜索树的最小值和最大值的非递归实现二分搜索树删除节点53423741225815331350删除只有左孩子的节点二分搜索树删除节点37412258153313534250删除只有左孩子的节点二分搜索树删除节点63593741225815331360删除只有右孩子的节点二分搜索树删除节点37412258153313635960删除只有右孩子的节点二分搜索树删除节点63593741225815331360删除左右都有孩子的节点534250二分搜索树删除节点63593741225815331360删除左右都有孩子的节点5342501962年，Hibbard提出-HubbardDeletion二分搜索树删除节点6359415860删除左右都有孩子的节点d534250d二分搜索树删除节点6359415860删除左右都有孩子的节点d找到s=min(d->right)534250ds二分搜索树删除节点6359415860删除左右都有孩子的节点d找到s=min(d->right)s是d的后继534250ds二分搜索树删除节点63415860删除左右都有孩子的节点d找到s=min(d->right)s是d的后继s->right=delMin(d->right)534250d59二分搜索树删除节点63415860删除左右都有孩子的节点d找到s=min(d->right)s是d的后继s->right=delMin(d->right)534250d59二分搜索树删除节点63415860删除左右都有孩子的节点d找到s=min(d->right)s是d的后继s->right=delMin(d->right)s->left=d->left534250d5959二分搜索树删除节点63415860删除左右都有孩子的节点d找到s=min(d->right)s是d的后继s->right=delMin(d->right)s->left=d->left删除d，s是新的子树的根534250d操作：删除二分搜索树的任意一个节点二分搜索树删除节点6359415860删除左右都有孩子的节点d找到s=min(d->right)s是d的后继534250ds二分搜索树删除节点6359415860删除左右都有孩子的节点d找到p=max(d->left)p是d的前驱534250dp练习：使用d的前驱p代替d节点的hibbarddeletion删除二分搜索树的任意一个节点时间复杂度O(logn)二分搜索树的顺序性二分搜索树的顺序性minimum,maximum二分搜索树的顺序性successor,predecessor练习：实现successor,predecessor二分搜索树的顺序性floor,ceil二分搜索树的floor和ceil6353423741225815331350寻找45的floor和ceil二分搜索树的floor和ceil6353423741225815331350寻找45的floor和ceilfloor二分搜索树的floor和ceil635342374