正文

请到「今天看啥」查看全文

二、红黑二叉树实现

此处还需要事先强调一下，红黑树再复杂也是一个基本的BST，所以和AVL自平衡二叉树一样，所有的插入和删除操作，也是先按照操作BST的基本方式进行插入、删除，然后再检查是否平衡而做出相应调整，RBTree的调整操作包括着色重绘和旋转操作。

2.1 节点数目

1
2
3
4
5
6
7
8
9

class RBNode {
private:
int data_;
SmartNodePtr left_;
SmartNodePtr right_;
SmartNodePtr parent_;
enum Color color_;
...
};

和之前的AVL平衡二叉树一样，节点所有指针域都使用了智能指针，这样在删除的时候只需要更改指针域，智能指针维护引用计数，并在必要的时候自动析构节点并释放内存。但和AVL Tree节点不同的是，这里多了一个parent_节点，因为在后面对RBTree做维护的时候，会有大量涉及到父亲、兄弟节点的操作，而这些亲戚节点的访问，以及当前处于左还是右子树的判断，都需要parent_域辅助完成。

2.2 插入操作

请到「今天看啥」查看全文