源代码网站和模板做的区别,网站业务员好做吗,苏州网站建设新手,健康码哪家公司开发的目录 BST 的方法摘要查找节点四个引用#xff0c;都有妙用递归版非递归版 插入节点利用search的返回值更新高度的注意事项插入算法的完整代码 删除节点框架单分支#xff0c;直接替代双分支#xff0c;化繁为简代码 code BST 预告#xff1a;本文是后续实现各种各样平衡二叉… 目录 BST 的方法摘要查找节点四个引用都有妙用递归版非递归版 插入节点利用search的返回值更新高度的注意事项插入算法的完整代码 删除节点框架单分支直接替代双分支化繁为简代码 code BST 预告本文是后续实现各种各样平衡二叉搜索树的铺垫。 BST 的方法 方法 功能 参数 返回值 search 查找 T const val BinNode * insert 插入 T const val BinNode * remove 移除 T const val bool
摘要
虚函数方便派生类进行重写。全局静态模板函数适用于AVLSplayRedBlack等各种BST这里的remove一看就是对外的因为参数终于不是指针了而是值。需要我们先找位置。
查找节点
四个引用都有妙用
看到searchIn的声明居然全都是引用类型。
static BinNodeT * searchIn(BinNodeT * rt, BinNodeT * hot_node, T const val)列举这四个引用各自的功能——
返回值引用插入节点时这个引用相当于插入位置后续我们将新节点的指针赋给到这个返回值父节点的左右孩子之一就会连上新节点。
BinNodeT * rt如果这个不是引用返回值返回的就是一个仅在函数内部的局部变量即形参后续改写这个引用值时会发生错误。
BinNodeT * hot_node在递归中随深度不断更新这个记忆热点也是为了方便插入算法等到最后退出时hot存的是插入位置的父节点。
T const val传递引用变量可以提速为了不误改前面加上const做约束。
递归版 virtual BinNodeT * search(T const val){return searchIn(BinTreeT::root, hot, val);}static BinNodeT * searchIn(BinNodeT * rt, BinNodeT * hot_node, T const val){if (!rt || rt-data val) return rt; // 返回的是引用hot_node rt; //在递归中随深度不断更新if (val rt-data) return searchIn(rt-left, hot_node, val);else return searchIn(rt-right, hot_node, val);}非递归版
尾递归转迭代略。
插入节点
利用search的返回值
有了查找节点算法中“记忆热点”hot的设计经过search()的运行就可以得到插入位置的父节点。或许应该记得BinTree里写过的几个函数insertAsLeft()insertAsRight()我们只需要将val与hot-data做比较即可。在这里我们换一种写法——不浪费search的返回值。你知道查找一旦失败返回值就是NULL的引用利用它就无需在insert()中判断究竟应该插入到hot的左边还是右边。
先找到插入位置X的类型必须是引用后续我们将新节点的指针赋给到Xhot的左右孩子之一就会连上新节点。
BinNodeT * X search(val); 下面这一句话将 “父-子” “子-父” 相互关系都连接好了。
X new BinNode(val, hot); 更新高度的注意事项
更新高度由于之前做的优化检测到某处更新后与更新前高度一致则不会再上行更新所以高度更新要给父节点更新即updateHighAbove(hot)如果给了X更新那就不会继续下去。
插入算法的完整代码 virtual BinNodeT * insert(T const val){BinNodeT * X search(val); //为了找到插入位置if (!X){X new BinNode(val, hot); //这一句话将两个关系连接// 不要忘记BinTreeT::size;updateHighAbove(hot);}return X;}insert()的返回值是X但返回类型是BinNodeT *并不是引用这在语法中是允许的。所返回的东西仅仅在数值上与X相同但与X完全脱离了关系。
删除节点
框架 virtual bool remove(T const val){BinNodeT * X search(val);if (!X) //树里没有val{return false;}else{removeAt(X, hot);BinTreeT::size--;updateHighAbove(hot);return true;}}单分支直接替代 双分支化繁为简
还是想哪一个节点替代被删节点的位置。那一定是直接后继。求中序遍历下的直接后继。
代码 static void removeAt(BinNodeT * X, BinNodeT * hot_node){// hot_node指向要被删除的父亲BinNodeT * del_node; // 实际要被删除的节点BinNodeT * succ_node; // 实际要被删除的节点的接替者if (!X-left){del_node X;succ_node X-right}else if (!X-right){del_node X;succ_node X-left;}else // 双分支情况{ // 找到中序的直接后继del_node succ(X);succ-node del_node-right;swap(del_node-data, X-data);BinNodeT::fromParentTo(del_node) succ;}hot del_node-parent;if (succ_node) succ-parent hot;delete del_node;return succ;}code BST
# pragma once# include BinTree.htemplate typename T
class BST : public BinTreeT {public:virtual BinNodeT * search(T const val){return searchIn(BinTreeT::root, hot, val);}virtual BinNodeT * insert(T const val){BinNodeT * X search(val); //为了找到插入位置if (!X){X new BinNode(val, hot); //这一句话将两个关系连接// 不要忘记BinTreeT::size;updateHighAbove(hot);}return X;}virtual bool remove(T const val){BinNodeT * X search(val);if (!X) //树里没有val{return false;}else{removeAt(X, hot);BinTreeT::size--;updateHighAbove(hot);return true;}}static void removeAt(BinNodeT * X, BinNodeT * hot_node){// hot_node指向要被删除的父亲BinNodeT * del_node; // 实际要被删除的节点BinNodeT * succ_node; // 实际要被删除的节点的接替者if (!X-left){del_node X;succ_node X-right}else if (!X-right){del_node X;succ_node X-left;}else // 双分支情况{ // 找到中序的直接后继del_node succ(X);succ-node del_node-right;swap(del_node-data, X-data);BinNodeT::fromParentTo(del_node) succ;}hot del_node-parent;if (succ_node) succ-parent hot;delete del_node;return succ;}static BinNodeT * searchIn(BinNodeT * rt, BinNodeT * hot_node, T const val){if (!rt || rt-data val) return rt; // 返回的是引用hot_node rt; //在递归中随深度不断更新if (val rt-data) return searchIn(rt-left, hot_node, val);else return searchIn(rt-right, hot_node, val);}protected:BinNodeT * hot; // 命中节点的父亲};
