树，二叉树，二叉查找树以及红黑树

本文主讲二叉树系列

树的概念

链表通常可以提供比数组更大的灵活性，但由于链表是线性结构，所以很难使用它们来组织对象的分层表示。虽然队列反映了某些层次，但它们是一维的，为了避免这种限制，创建了一个新型数据类型，称为树，树由节点和弧组成。
树在计算机科学里，是一种十分基础的数据结构。几乎所有操作系统都将文件存放在树状结构里；几乎所有的编译器都需要实现一个表达式树；文件压缩所用的哈夫曼算法需要用到哈夫曼树；数据库所使用的B树，以及map,set等容器底层数据结构红黑树。

图1.png

图 1(A) 是使用树结构存储的集合 {A,B,C,D,E,F,G,H,I,J,K,L,M} 的示意图。对于数据 A 来说，和数据 B、C、D 有关系；对于数据 B 来说，和 E、F 有关系。这就是“一对多”的关系。

将具有“一对多”关系的集合中的数据元素按照图 1（A）的形式进行存储，整个存储形状在逻辑结构上看，类似于实际生活中倒着的树（图 1（B）倒过来），所以称这种存储结构为“树型”存储结构。

什么是二叉树

简单地理解，满足以下两个条件的树就是二叉树：
1.本身是有序树；
2.树中包含的各个节点的度不能超过 2，即只能是 0、1 或者 2；

图2.gif

经过前人的总结，二叉树具有以下几个性质：
1.二叉树中，第 i 层最多有 2^(i-1) 个结点。
2.如果二叉树的深度为 K，那么此二叉树最多有 2^K-1 个结点。
3.二叉树中，终端结点数（叶子结点数）为 n0，度为 2 的结点数为 n2，则 n0=n2+1。

性质 3 的计算方法为：对于一个二叉树来说，除了度为 0 的叶子结点和度为 2 的结点，剩下的就是度为 1 的结点（设为 n1），那么总结点 n=n0+n1+n2。
同时，对于每一个结点来说都是由其父结点分支表示的，假设树中分枝数为 B，那么总结点数 n=B+1。而分枝数是可以通过 n1 和 n2 表示的，即 B=n1+2 * n2。所以，n 用另外一种方式表示为 n=n1+2 * n2+1。
两种方式得到的 n 值组成一个方程组，就可以得出 n0=n2+1。
二叉树还可以继续分类，衍生出满二叉树和完全二叉树

满二叉树

如果二叉树中除了叶子结点，每个结点的度都为 2，则此二叉树称为满二叉树。

满二叉树.gif

如图所示就是一棵满二叉树。

满二叉树除了满足普通二叉树的性质，还具有以下性质：
1.)满二叉树中第 i 层的节点数为 2^（n-1）个。
2.)深度为 k 的满二叉树必有 2^k-1 个节点，叶子数为 2^(k-1)。
3.)满二叉树中不存在度为 1 的节点，每一个分支点中都两棵深度相同的子树，且叶子节点都在最底层。
4.)具有 n 个节点的满二叉树的深度为 log2(n+1)。

完全二叉树

如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。

完全二叉树.gif

如图 a) 所示是一棵完全二叉树，图 b) 由于最后一层的节点没有按照从左向右分布，因此只能算作是普通的二叉树。

对于任意一个完全二叉树来说，如果将含有的结点按照层次从左到右依次标号（如图 3a)）(从1开始标号，即根节点标号为1，若从0开始标号，则结论有所不同），对于任意一个结点 i ，完全二叉树还有以下几个结论成立：
1)当 i>0 时，父亲结点为结点 [i/2] 。（i=1 时，表示的是根结点，无父亲结点）
2)如果 2i>n（总结点的个数），则结点 i 肯定没有左孩子（为叶子结点）；否则其左孩子是结点 2i 。
3)如果 2i+1>n ，则结点 i 肯定没有右孩子；否则右孩子是结点 2i+1 。

二叉树的遍历

在这里给出二叉树的非递归遍历算法
以下图为例：

可在leetcode的探索中去刷关于树的遍历的题。（以下给出遍历代码皆在LeetCode中通过）

前序遍历

前序遍历结果：[1,2,4,5,3,6,7]
用栈来存储节点：
1）节点1，2，4依次入栈，节点4 的左孩子为空，停止入栈；[1,2,4]
2）节点4 出栈，其右孩子为空，则不操作接着节点2出栈，其右孩子不为空则进栈，节点5进栈，其左孩子为空停止进栈；[1,5]
3)节点5 出栈，右孩子为空；接着节点1（根节点）出栈，右孩子不为空则节点3进栈，节点6为其左孩子则继续进栈；[3,6]
4)节点6,3出栈，节点7进栈；[7]
5）最后节点7出栈，左右孩子皆为空，栈也为空，则遍历结束。
具体代码如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        if(root==nullptr) return result;
        stack<TreeNode*> s;
        TreeNode* p=root;
        while(!s.empty() || p!=nullptr) //当回到根节点，判断右节点，此时 栈是空的，因此加一个p不为空的判断n
        {
            while(p!=nullptr)
            {
                //前序遍历，先保存遍历结果
                result.push_back(p->val);
                s.push(p);
                p=p->left;
            }
            TreeNode* t=s.top();
            s.pop();
            if(t->right!=nullptr)
            {
                p=t->right;
            }
        }
        return result;
    }
};

中序遍历

中序遍历结果：[4,2,5,1,6,3,7]
步骤和前序遍历相同，不在赘述，只是打印结果位置不同，中序遍历在节点出栈时打印结果，前序遍历在节点进栈时打印结果。
具体代码如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        if(root==nullptr)
        {
            return result;
        }
        TreeNode* p=root;
        stack<TreeNode*> s;
        while(!s.empty() || p!=nullptr)
        {
            while(p!=nullptr)
            {
                s.push(p);
                p=p->left;
            }
            TreeNode* t=s.top();
            s.pop();
            //出栈时打印结果
            result.push_back(t->val);
            if(t->right!=nullptr) p=t->right;
        }
        return result;
    }
};

后序遍历

后序遍历结果：[4,5,2,6,7,3,1]
过程稍微有些不同，类似于中序遍历，左边的节点都是要第一个进行访问，在这里只是右节点和根节点的区别，同样采用一个栈来解决这个问题。
只是后序遍历在决定是否可以输出当前节点的值的时候，需要考虑其左右子树是否都已经遍历完成。
所以需要设置一个lastVisit游标。
若lastVisit等于当前考查节点的右子树，表示该节点的左右子树都已经遍历完成，则可以输出当前节点。
并把lastVisit节点设置成当前节点，将当前游标节点node设置为空，下一轮就可以访问栈顶元素
具体代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        if(root==nullptr)
        {
            return result;
        }
        TreeNode* p=root;
        TreeNode* lastvisit=nullptr;
        stack<TreeNode*> s;
        while(!s.empty() || p!=nullptr)
        {
            while(p!=nullptr)
            {
                s.push(p);
                p=p->left;
            }
            TreeNode* t=s.top();
            if(t->right!=nullptr && lastvisit!=t->right)
            {
                p=t->right;
            }
            else
            {
                result.push_back(t->val);
                lastvisit=t;
                s.pop();
            }
        }
        return result;
    }
};

层序遍历

层序遍历结果：[1,2,3,4,5,6,7]
层序遍历相对简单，用一个队列来完成，首先根节点入队列，当节点处队列的时候判断左右子节点是否为空，不为空则依次入队列，直到队列为空则遍历完毕。

class Solution {
    public:
        vector<int> levelOrder(TreeNode* root) 
        {
            vector<int> ret;
            queue<TreeNode*> q;
            if(root)
                q.push(root);
            while(!q.empty())
            {
                TreeNode* temp = q.front();
                ret.push_back(temp->val);
                q.pop();
                if(temp->left)
                    q.push(temp->left);
                if(temp->right)
                    q.push(temp->right);
            }
            return ret;
        }
    };

如果层序遍历按层打印结果：[ [1],[2,3],[4,5,6,7] ],则需要记录每层节点的数量，具体代码如下：

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if(root==nullptr) return result;
        vector<int> t;
        queue<TreeNode*> q;
        TreeNode* p=root;
        int levelcount=1;
        int nextlevelcount=0;//记录每层的节点数目
        q.push(root);
        while(!q.empty())
        {
            TreeNode* tmp=q.front();
            t.push_back(tmp->val);
            levelcount--;
            q.pop();
            if(tmp->left!=nullptr) 
            {
                q.push(tmp->left);
                nextlevelcount++;
            }
            if(tmp->right!=nullptr) 
            {
                q.push(tmp->right);
                nextlevelcount++;
            }
            if(levelcount==0)
            {
                result.push_back(t);
                t.clear();
                levelcount=nextlevelcount;
                nextlevelcount=0;
            }
        }
        return result;
    }
};

二叉搜索树

完整代码：https://github.com/songqiyuan/DataStruct/blob/master/Tree/searchTree.hpp
二叉搜索树（BST）是二叉树的一种特殊表示形式，它满足如下特性：

1.每个节点中的值必须大于（或等于）存储在其左侧子树中的任何值。
2每个节点中的值必须小于（或等于）存储在其右子树中的任何值。

二叉搜索树.png

二叉排序树的操作主要有：
1.查找：递归查找是否存在key。
2.插入：原树中不存在key，插入key返回true，否则返回false。
3.构造：循环的插入操作。
4.删除：（1）叶子节点：直接删除，不影响原树。
（2）仅仅有左或右子树的节点：节点删除后，将它的左子树或右子树整个移动到删除节点的位置就可以，子承父业。
（3）既有左又有右子树的节点：找到须要删除的节点p的直接前驱或者直接后继s（寻找前驱和后继节点），用s来替换节点p，然后再删除节点s

具体实现代码如下：

    void  _deleteNode(int y)
    {
        TreeNode* node = findKey(y);
        if (node == nullptr) return ;
    
        if (node->right == nullptr)
        {
            TransPlant( node, node->left); //情况1,情况2
        }
        else if (node->left == nullptr)
        {
                        //辅助函数
            TransPlant( node, node->right);//情况1,情况2
        }
        else
        {
                        //情况3
            //查找后继节点
            TreeNode* tmp=increment(node);
            if (tmp->parent != node)// && tmp->right!=nullptr)
            {
                TransPlant(tmp, tmp->right);
                tmp->right = node->right;
                tmp->right->parent = tmp;
            }
            TransPlant(node, tmp);
            tmp->left = node->left;
            tmp->left->parent = tmp;
        }
        resetNode(node);
    }

红黑树

完整代码：https://github.com/songqiyuan/DataStruct/blob/master/Tree/rbtree.hpp
在学习红黑树前先理解旋转的概念：
也许因为输入的值不够随机，也许因为经过某些插入删除操作二叉搜索树可能会失去平衡，搜索效率降低，如图：

平衡与不平衡.png

所谓平衡与否，并没有一个绝对的测量标准，“平衡”的大致意义是：没有任何一个节点深度过大，不同的平衡条件造就出不同的效率表现以及不同的实现复杂度。AVL-tree,RB-tree均可实现出平衡二叉树。
由于删除和添加操作对树做了修改，结果可能违反了红黑树的性质，为了维护这些性质，必须要修改树中某些节点的颜色以及指针结构。
指针结构的修改是通过旋转来完成的，这是能保持二叉搜索树性质的搜索树局部操作。如图的左旋和右旋：

左右旋转.png

当在某个节点x上做左旋时，假设它的右孩子为y而不是NULL(x可以为其右孩子节点不是NULL节点的树内任意节点），左旋以x到y的链为“支轴”进行。它使y成为树的新的根节点，x成为y的左孩子，y的左孩子成为x的右孩子，右旋转类似，具体代码如下：

//左旋和右旋
//左旋
void RotateLeft(TreeNode* node)
{
    TreeNode* y = node->right;
    node->right = y->left;
    if (y->left != nullptr)
    {
        y->left->parent = node;
    }
    y->parent = node->parent;
    if (node->parent == nullptr)
    {
        _root = y;
    }
    else if (node == node->parent->left)
    {
        node->parent->left = y;
    }
    else if (node == node->parent->right)
    {
        node->parent->right = y;
    }
    y->left = node;
    node->parent = y;
}
//右旋
void RotateRight(TreeNode* node)
{
    TreeNode* y = node->left;
    node->left = y->right;
    if (y->right != nullptr)
    {
        y->right->parent = node;
    }
    y->parent = node->parent;
    if (node->parent == nullptr)
    {
        _root = y;
    }
    else if (node == node->parent->left)
    {
        node->parent->left = y;
    }
    else if (node == node->parent->right)
    {
        node->parent->right = y;
    }
    y->right = node;
    node->parent = y;
}

红黑树的性质

1.每个节点是红色或者黑色；
2.根节点是黑色的；
3.每个叶节点是黑色的；
4.如果一个节点是红色的，则它的两个子节点都是黑色的；
5.对于每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑节点。

下面主要讲讲可能破坏红黑树性质的删除和插入操作。

红黑树的插入操作

红黑树的插入操作和二叉搜索树的插入过程是类似的，只是插入的最后有所改变：将插入的节点着为红色（为什么是红色，因为要保持红黑树的性质5，如果插入的颜色为黑色，则必然改变某条路径上的黑节点的个数，破坏红黑树的性质），然后调整红黑树（插入的节点为红色，可能违背性质1或4）。

为了理解RBInsertFixup()函数是如何工作的，首先，要确定当节点被插入并着色后，红黑树的性质哪些是被破坏的。当插入为根节点时性质2（根节点为黑色）被破坏，当插入节点的父节点为红色是性质4被破坏。下图是一个修正过程：

插入节点.png

情况1：z的叔父节点y是红色的（由性质4知，祖父节点为黑色）
情况2：z的叔父节点y是黑色的且z是一个右孩子
情况3：z的叔父节点y是黑色的且z是一个左孩子
代码如下：

//插入操作
void _Insert(int key)
{
    TreeNode* node = _root;
    TreeNode* pNode = nullptr;
    while (node != nullptr)
    {
        pNode = node;
        if (key > node->val)
        {
            node = node->right;
        }
        else
        {
            node = node->left;
        }
    }
    TreeNode* pInsertNode = new TreeNode(key);
    //根节点为空，此时无数据
    if (pNode == nullptr)
    {
        _root = pInsertNode;
    }
    else if (pNode->val < key)
    {
        pNode->right = pInsertNode;
        pInsertNode->parent = pNode;
    }
    else
    {
        pNode->left = pInsertNode;
        pInsertNode->parent = pNode;
    }
        //修正红黑树
    RBInsertFixup(pInsertNode);
}
    //修正插入红黑性质
void RBInsertFixup(TreeNode* node)
{
    //当前插入节点 ，其父节点为红色
    while (node->parent != nullptr && node->parent->color == RED)
    {
        if (node->parent->parent->left == node->parent)
        {
            TreeNode* uncle = node->parent->parent->right;
            if (uncle!=nullptr && uncle->color == RED)
            {
                //若父节点为红色或叔父节点为红色，则祖父节点一定为黑色
                node->parent->color = BLACK;
                uncle->color = BLACK;
                node->parent->parent->color = RED;
                node = node->parent->parent;
            }
            else
            {
                if (node->parent->right == node)
                {
                    node = node->parent;
                    RotateLeft(node);
                }
                node->parent->color = BLACK;
                node->parent->parent->color = RED;
                RotateRight(node->parent->parent);
            }
        }
        else if(node->parent->parent->right==node->parent)
        {
            TreeNode* uncle = node->parent->parent->left;
            if (uncle != nullptr && uncle->color == RED)
            {
                node->parent->color = BLACK;
                uncle->color = BLACK;
                node->parent->parent->color = RED;
                node = node->parent->parent;
            }
            else 
            {
                if (node == node->parent->left)
                {
                    node = node->parent;
                    RotateRight(node);
                }
                node->parent->color = BLACK;
                node->parent->parent->color = RED;
                RotateLeft(node->parent->parent);
            }
        }
    }
    _root->color = BLACK;
}

红黑树的删除

删除修正.png

下面所有情况都在真实删除的节点的颜色为黑的前提下，删除节点颜色为红色并不违反红黑树性质。
情况1：x的兄弟节点w是红色的
由于删除节点为黑色，而w为红色，则w必定有黑色子节点（性质4），所以可以改变w和x.p的颜色，并做一次左旋（如图中的(a)）,而不违反红黑树的任何性质。旋转后x的新兄弟节点为w的一个子节点，其颜色为黑色。这样就将情况转换为2,3或4处理。

情况2:x的兄弟节点w是黑色的，而且w的两个子节点都是黑色的
如图中(b)所示，将兄弟节点w着色为红色，这样以父节点为根的子树到叶节点的黑色节点是相同的，但比其他路径少一个黑色节点，因此将父节点设置为为新的x节点。此时父节点的颜色未知红色或黑色，当为红色时可以看出违背了性质4，不过此时我们只需将当前x节点设置为黑色就可以了，此时红黑树性质全部恢复。当为黑色节点时，转换为其他情况。

情况3：x的兄弟节点w是黑色，w的左孩子是红色，w的右孩子是黑色
如图中(c)，可以交换w和其左孩子的颜色，然后对w进行右旋而不违反红黑树的性质（不理解的话可以画图验证一下），现在x新的兄弟节点，w的左孩子。这样我们就把情况3转换为了情况4.

情况4：x的兄弟节点w是黑色的，且w的右孩子是红色的
如图中(d)所示，想办法用红色节点来来填补左子树（x.p.left）中减少的黑节点数,通过改变一些节点的颜色来实现：a.将w着色为其父节点的颜色；b.将w.right由红色改为黑色；c.将x.p的颜色改为黑色（用该节点来填补左子树中缺失的黑色节点数）；d.将x.p节点左旋，到此红黑树性质恢复，将x设置为根节点，结束修正。

代码实现：

    void  _deleteNode(int y)
    {
        TreeNode* node = findKey(y);
        if (node == nullptr) return;
        //记录删除节点的颜色
        int DeleteNodeColor = node->color;
        //需要调整的节点
        TreeNode* FixNode = nullptr;
        if (node->right == nullptr)
        {
            FixNode = node->left;
            TransPlant(node, node->left);
        }
        else if (node->left == nullptr)
        {
            FixNode = node->right;
            TransPlant(node, node->right);
        }
        else
        {
            //查找后继节点
            TreeNode* tmp = increment(node);
            DeleteNodeColor = tmp->color;
            FixNode = tmp->right;
            if (tmp->parent == node)
            {
                FixNode->parent = tmp;
            }
            if (tmp->parent != node)// && tmp->right!=nullptr)
            {
                TransPlant(tmp, tmp->right);
                tmp->right = node->right;
                tmp->right->parent = tmp;
            }
            TransPlant(node, tmp);
            tmp->left = node->left;
            tmp->left->parent = tmp;
            tmp->color = node->color;
        }
        if (DeleteNodeColor == BLACK)
        {
            //处理平衡
            RBDeleteFixUp(FixNode);
        }
        resetNode(node);
    }
    void RBDeleteFixUp(TreeNode* node)
    {
        while (node != nullptr && node->color == BLACK && node != _root)
        {
            if (node == node->parent->left)
            {
                TreeNode* bnode = node->parent->right;
                //如果node为黑色节点，怎为了保持红黑树性质怎，其兄弟节点必定存在，即bnode不为空
                if (bnode->color == RED)
                {
                    //此时父节点一定为黑色
                    bnode->color = BLACK;
                    node->parent->color = RED;
                    RotateLeft(node->parent);
                    bnode = node->parent->right;
                }
                if (bnode->left->color == BLACK && bnode->right->color == BLACK)
                {
                    bnode->color = RED;
                    node = node->parent;
                }
                else
                {
                    if (bnode->right->color == BLACK)
                    {
                        //根据上一个条件判断，则此时左节点必为红色,父节点必为黑色
                        bnode->left->color = BLACK;
                        bnode->parent->color = RED;
                        RotateRight(bnode);
                        bnode = node->parent->right;
                    }
                    //如果兄弟节点的右节点为红色
                    bnode->color = node->parent->color;
                    node->parent->color = BLACK;
                    bnode->right->color = BLACK;
                    RotateLeft(node->parent);
                    node = _root;//结束循环，达到平衡
                }
            }
            else if (node == node->parent->right)
            {
                TreeNode* bnode = node->parent->left;
                if (bnode->color == RED)
                {
                    bnode->color = BLACK;
                    node->parent->color = RED;
                    RotateRight(node->parent);
                    bnode = node->parent->left;
                }
                if (bnode->left->color == BLACK && bnode->right->color == BLACK)
                {
                    bnode->color = RED;
                    node = node->parent;
                }
                else
                {
                    if (bnode->left->color == BLACK)
                    {
                        bnode->color = RED;
                        bnode->right->color = BLACK;
                        RotateLeft(bnode);
                        bnode = node->parent->left;
                    }
                    bnode->color = node->parent->color;
                    node->parent->color = BLACK;
                    bnode->left->color = BLACK;
                    RotateLeft(node->parent);
                    node = _root;
                }
            }
        }
        if (node != nullptr)
        {
            node->color = BLACK;
        }
    }

红黑树测试结果：

红黑树测试结果.png