c++ - 数据结构:关于二叉查找树(BinarySearchTree)的删除算法的疑问?
天蓬老师
天蓬老师 2017-04-17 11:18:16
0
2
656

Mark Allen Weiss的《数据结构与算法分析》第4章中讲到二叉查找树这种数据结构,关于删除的代码是这样的:

// 删除以t为根的BST中值为x的节点 void remove(int x, BinaryNode*& t) { if ( t == NULL) { return ; } if (x < t->data) { remove(x, t->left); } else if (x > t->data) { remove(x, t->right); } // 左右都有节点的情况 else if (t->left != NULL && t->right != NULL) { t->data = findMin(t->right)->data; // 右子树最小的节点 remove(t->data, t->right); } else { BinaryNode* oldNode = t; t = (t->left != NULL) ? t->left : t->right); delete oldNode; } }

二叉树的基本性质是节点大于其左子树的所有节点,小于其右子树的所有节点,
在这个删除算法中,当删除的节点有2个儿子的情况的时候,为什么是从右子树找出最小的节点而不是从左子树找出最大的节点呢?

天蓬老师
天蓬老师

欢迎选择我的课程,让我们一起见证您的进步~~

모든 응답 (2)
迷茫

都可以,二叉搜索树删除拥有左右子树节点的时候,既可以用左子树的最右节点来替代,也可以用右子树的最左节点来替代。书中的例子应该是刚好用到了其中的一种情况。

    左手右手慢动作

    其实当总是从寻找右子树的最左节点或者左子树的最右节点替代的时候,会引起二叉搜索树的退化,当退化成链表,二叉搜索树的查找优势就不存在了。可以尝试随机从左右子树的节点替代,也可以考虑更复杂但效果更好的treap,乃至非常复杂的红黑树平衡树

      최신 다운로드
      더>
      웹 효과
      웹사이트 소스 코드
      웹사이트 자료
      프론트엔드 템플릿
      회사 소개 부인 성명 Sitemap
      PHP 중국어 웹사이트:공공복지 온라인 PHP 교육,PHP 학습자의 빠른 성장을 도와주세요!