一颗AVL树是其每个节点的左子树和右子树的高度最多相差1的二叉查找树
	
懒惰删除：当一个元素要被删除时，它仍留在树中，而只时被标记为删除
	
红黑树遍历时间复杂度O(log n)

1、定义：
（1）树、二叉树


 

 
（2）二叉查找树




 

 
（3）DFS（Deep First Search）深度优先遍历和 BFS（Breath First Search）宽度（广度）优先搜索
二叉树的遍历:


BFS：A   B C D  E F  G  H I

DFS:  A B  C E  F  D G H  I
 
二叉树的深度优先遍历种类：前序、中序、后序遍历
 

 
图的遍历： 
 

从A出发
BFS：A  B  C  D  E  F （其中一种）
DFS：A  B  D  F  E  C （其中一种）

 
（4）BFS和DFS的实现
BFS： 队列（先进先出）
 

步骤：
    1、首先A入队列，

    2、A出队列时，A的邻接结点B，C相应进入队列 

    3、B出队列时，B的邻接结点A，C，D中未进过队列的D进入队列

    4、C出队列时，C的邻接结点A，B，D，E中未进过队列的E进入队列

    5、D出队列时，D的邻接结点B，C，E，F中未进过队列的F进入队列

    6、E出队列，没有结点可再进队列

    7、F出队列

 

实例1：

用BFS（Breath First Search）的方法求二叉树的最大深度：
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        queue<TreeNode*> Q;
        Q.push(root);
        int ans = 0;
        while (!Q.empty()) {
            int sz = Q.size();
            while (sz > 0) {
                TreeNode* node = Q.front();Q.pop();
                if (node->left) Q.push(node->left);
                if (node->right) Q.push(node->right);
                sz -= 1;
            }
            ans += 1;
        } 
        return ans;
    }
};

实例2：
接下来我们再来介绍二叉树的另一种遍历方式：层序遍历。
层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。
需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而是用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。
而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        vector<vector<int>> result;
        while (!que.empty()) {
            int size = que.size();
            vector<int> vec;
            // 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            result.push_back(vec);
        }
        return result;
    }
};

 

 
DFS：栈（先进后出）


步骤：
1、首先A入栈，

2、A出栈时，A的邻接结点B，C相应入栈  （这里假设C在下，B在上）

3、B出栈时，B的邻接结点A，C，D中未进过栈的D入栈

4、D出栈时，D的邻接结点B，C，E，F中未进过栈的E、F入栈（假设E在下，F在上）

5、F出栈时，F没有邻接结点可入栈

6、E出栈，E的邻接结点C，D已入过栈

7、C出栈

 

 

 
参考：
BFS和DFS

1.B树的所有外部结点都处于最底层，且深度完全一致，所以B树肯定是满树
2.考研考的比较多的是B树的深度h，B树的阶数m，B树的关键码个数N

1）B树的高度的范围：


2）B树各个结点所含关键码的3个要求：

i.根节点至少含有1个关键码

ii.每个结点至多含m-1个关键码

iii.除了根节点，其它分支结点至少包含$\lceil{m/2}\rceil$-1个结点
3.B树和其它普通树不同的地方在于，计算树的高度时需要把外部节点考虑进去（即使外部节点是并不包含关键码的结点）
以上3个点可以通过这道题来考察以下：

解析：最多：4×（1+5+5×5）=124；1+2×2+2×3×2=17
关于最少存放的情况：



黑色圆圈是关键码，红色框框是外部节点，即非关键码

1、如何判断这个树是不是完全二叉树？
首先从完全二叉树的定义来入手，对于一个完全树，要么他是一个叶结点，要么他一定有左孩子，我们可以遍历每一个点，如果它左孩子的深度小于右孩子，或者左孩子深度等于右孩子但是在遍历他的左孩子时发现左右不等，均可以判断出它不是一个完全二叉树