最近在手搓红黑树时遇到一个问题：类模板的派生类使用智能指针时的向下转换错误，总之，经过一番研究，智能指针无法实现类模板指针的向下转换，最终还是用裸指针手动管理内存更加灵活。
红黑树类型继承
我们知道红黑树是一种特殊的自平衡二叉排序树，所以我手撕红黑树的思路就是：
- 实现二叉排序树
- 实现自平衡二叉排序树（AVL树）
- 实现红黑树
那么很自然的，有二叉树节点类：
template<typename ValueType>
class BinaryTreeNode
{
public:
ValueType value;
std::shared_ptr<BinaryTreeNode<ValueType>> left;
std::shared_ptr<BinaryTreeNode<ValueType>> right;
public:
BinaryTreeNode(ValueType val);
BinaryTreeNode();
};
对于自平衡二叉排序树来说，其节点在普通二叉树节点上，增加一个depth属性：
template<typename ValueType>
class AVLTreeNode :public BinaryTreeNode<ValueType>
{
public:
int depth;
public:
AVLTreeNode(ValueType val, int dep);
};
当实现二叉排序树时，一切都还安好：
template<typename ValueType>
class BinarySearchTree
{
protected:
std::shared_ptr<BinaryTreeNode<ValueType>> rootNodePtr;
protected:
virtual std::shared_ptr<BinaryTreeNode<ValueType>> searchNodeInternal(ValueType val, BinaryTreeNode<ValueType>* current);
virtual void insertNodeInternal(ValueType val, std::shared_ptr<BinaryTreeNode<ValueType>>& current);
virtual void deleteNodeInternal(ValueType val, std::shared_ptr<BinaryTreeNode<ValueType>>& current, std::shared_ptr<BinaryTreeNode<ValueType>>& parent);
virtual void traverseInternal(std::shared_ptr<BinaryTreeNode<ValueType>> root);
public:
std::shared_ptr<BinaryTreeNode<ValueType>> searchNode(ValueType val);
virtual void insertNode(ValueType val);
virtual void deleteNode(ValueType val);
virtual void traverse();
BinarySearchTree();
};
但是，当我很自然地想要实现一个继承自BinarySearchTree的AVLTree的时候，问题出现了：
template<typename ValueType>
class AVLTree:public BinarySearchTree<ValueType>
{
private:
void updateDepth(std::shared_ptr<BinaryTreeNode<ValueType>> root);
protected:
void leftRotate(std::shared_ptr<BinaryTreeNode<ValueType>>& root);
void rightRotate(std::shared_ptr<BinaryTreeNode<ValueType>>& root);
void insertNodeInternal(ValueType val, std::shared_ptr<BinaryTreeNode<ValueType>>& current) override;
void deleteNodeInternal(ValueType val, std::shared_ptr<BinaryTreeNode<ValueType>>& current, std::shared_ptr<BinaryTreeNode<ValueType>>& parent) override;
public:
void insertNode(ValueType val) override;
void deleteNode(ValueType val) override;;
AVLTree();
};
AVL树在插入删除时需要进行左旋和右旋来保证树的平衡性，所以我们覆盖了基类的insertNode和deleteNode，为了实现多态，这里用的都是std::shared_ptr<BinaryTreeNode<ValueType>>类型的指针以使派生类跟基类的声明一致，但是当我们需要用到AVLTreeNode自身特有的属性depth的时候，问题出现了，如下代码是不合法的：
std::shared_ptr<AVLTreeNode<ValueType>> avlRoot =
std::dynamic_pointer_cast<AVLTreeNode<ValueType>>(rootNodePtr);
这会导致编译错误：BinaryTreeNode<ValueType>不是多态类型。
即使BinaryTreeNode的函数使用了virtual声明，但是因为它是个类模板，当ValueType不确定时，它并没有被实例化成具体的类型，所以这里的dynamic_pointer_cast不合法，只有ValueType被确定时，代码才是合法的：
std::shared_ptr<AVLTreeNode<int>> avlRoot =
std::dynamic_pointer_cast<AVLTreeNode<int>>(rootNodePtr);
那么问题来了，要么我为每一个具体类型实现一个对应的AVLTree，要么我的AVLTree和将来的RedBlackTree不继承BinarySearchTree，不使用多态实现，前者无疑不具有可行性，后者会导致每一个新的Tree类型都需要重复实现一些基础功能，两害相权，我还是选择了后者。
智能指针的交换问题
但是智能指针依然导致了一个问题：指针交换的不方便。因为AVL树需要实现左右旋的操作：
template<typename ValueType>
inline void AVLTree<ValueType>::rightRotate(std::shared_ptr<AVLTreeNode<ValueType>>& root)
{
auto pivot = root->left;
...
}
这里是rightRotate，所以，pivot指向root的左子树，并且在旋转以后，root指向的内存需要变更为pivot指向的内存，同时由于root作为其父节点的子树，需要确实改变root本身指向的内存，而非内存指向的内容，所以需要引用传递实参，如果我们使用类似裸指针的方式：
auto tmp = root;
root = pivot;
这会导致tmp指向的内存也变成pivot指向的内存，而非我们期望的root，所以我们不得不使用swap来进行内存交换：
std::shared_ptr<AVLTreeNode<ValueType>> tmp;
root.swap(tmp);
root = pivot;
最终，rightRotate需要如下实现：
template<typename ValueType>
inline void AVLTree<ValueType>::rightRotate(std::shared_ptr<AVLTreeNode<ValueType>>& root)
{
if (root.get() == nullptr)
{
return;
}
auto pivot = root->left;
if (pivot.get() == nullptr)
{
return;
}
std::shared_ptr<AVLTreeNode<ValueType>> pivotRight;
std::shared_ptr<AVLTreeNode<ValueType>> tmpPivot;
std::shared_ptr<AVLTreeNode<ValueType>> tmpRoot;
pivot->right.swap(pivotRight);
pivot.swap(tmpPivot);
root->left = pivotRight;
root.swap(tmpRoot);
root = tmpPivot;
root->right = tmpRoot;
}
这无疑比裸指针更加繁琐且可读性较差，最终，还是采用了裸指针进行实现：
template<typename ValueType>
inline void AVLTree<ValueType>::rightRotate(AVLTreeNode<ValueType>** rootPtr)
{
auto root = *rootPtr;
if (root == nullptr)
{
return;
}
auto pivot = root->left;
if (pivot == nullptr)
{
return;
}
AVLTreeNode<ValueType>* tmpRoot;
tmpRoot = root;
*rootPtr = (AVLTreeNode<ValueType>*)pivot;
tmpRoot->left = pivot->right;
pivot->right = tmpRoot;
}
这样清晰简洁多了。
github项目地址
