AlgorithmByJava

linear structure - one-to-one relationship

linear list - 线性表 - 逻辑结构

Sequence table - 顺序表

数组

数组是一种顺序表，但不能说顺序表是数组。数组是顺序表在实际编程中的一种实现方式。

Linked list - 链表

queue - 队列

stack - 栈

tree structure - one-to-many relationship

binary Tree - 二叉树

binary search tree / binary sort tree - 二叉搜索树/二叉查找树/二叉排序树

定义：或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

二叉搜索树的中序遍历是从小到大排列

self balanced tree 自平衡树

avl 树 - 自平衡二叉搜索树

也是一种高度平衡树，能够自主平衡高度差，使得搜索效率提升，搜索的时间复杂度为O(logN)

特性：

• 首先是一颗二叉搜索树(对所有节点来说，其左孩子节点比本身要小，右孩子节点比本少要大)
• 整棵树的每个结点的左右分支都是一颗AVL树
• 整棵树的所有结点的左右子树的高度之差（平衡因子balance factor）的绝对值不超过1(-1,0,1)

平衡操作

新增节点

删除节点

red-black tree - 红黑树

同AVL树类似，也是自平衡树的一种。但是其平衡调整的原理不仅相同。相比于红黑树来说，其子树的高度差会更大，但对于增加和删除节点，其调整平衡的效率会更高。 这里的效率更高并不是指时间复杂度的高低，而是指具体调整操作中可能涉及的调整方式的快慢（具体分析请点击这里）

特性：

• 首先是一颗二叉搜索树(对所有节点来说，其左孩子节点比本身要小，右孩子节点比本少要大)
• 所有的节点都只能为黑色或红色
• 红色节点的父节点和孩子节点都只能为黑色节点(两个红色节点不能直接相连)
• 根节点和叶子节点为黑色(这里说的叶子节点不是包含元素的叶子节点，包含元素的叶子节点还有两个黑色空节点作为真正的叶子节点)
• 所有节点到达能到的叶子节点的路径上所包含的黑色节点数量相同(叶子节点的定义同上)

根据这些特性可以得出结论

1. 红黑树不一定要含有红色节点，全部都是黑色节点的满二叉树为红黑树
2. 红黑树的根节点到叶子节点的最长路径长度最多为最短路径的两倍（因为到到叶子节点的路径经过的黑色节点相同，而每两个黑色节点之间最多只有一个红色节点）
3. 红色节点必须不可能只有左子树或右子树，必须同时拥有左右子树，或为叶子节点

平衡操作

新增节点

新增节点时，新增的都是红色节点。因为新增红色节点后对平衡性的影响更小

第一步与二叉搜索树的步骤相同，通过左小右大的原则找到需要插入的位置

下面通过一下几种情况来分析

1. 新增树的第一个节点，即根节点。

   因为根节点必须为黑色，因此将节点变黑即可。

2. 新增节点位置的父亲节点为黑色节点

   因为新增节点为红色节点，因此这种情况并不会破坏红黑树的特性和平衡，因此不需要做调整

3. 新增节点位置的父亲节点为红色节点

   因为不能有两个连续的红色节点，因此在红色节点后插入红色节点必定会破坏该性质

   该情况会涉及到旋转操作，红黑树新增节点后最多通过两次旋转即可恢复平衡，这是由红黑树的性质决定的。相对于AVL树，红黑树允许更大程度的不平衡(最长搜索路径可以达到最短搜索路径的两倍)

   分两种情况（看叔叔节点颜色）

   1. 叔叔节点为红色

                       |—— 叔叔节点变黑
      

      三变色 —|—— 父亲节点变红

                       |—— 爷爷节点变红
      

      因为此时爷爷节点变红，因此可能会导致爷爷节点成为连续的第二个红色节点 因此将爷爷节点作为新插入节点再向上遍历。

   2. 叔叔节点为黑色（空节点也为黑色）

      该情况可能会涉及到一次或两次旋转。

      根据插入节点（记为I），插入节点的父亲节点（记为P），插入节点的爷爷节点（记为G）的位置情况分为四类

      1. LL型：P为G的左子节点，I为P的左子节点
      2. RR型：P为G的右子节点，I为P的右子节点

      以上两种情况，I、P、G为三个节点连成直线，因此旋转一次即可 以P节点为轴，G节点绕P节点旋转，LL型右旋，RR型左旋。旋转完成后交换P、G颜色

      1. LR型：P为G的左子节点，I为P的右子节点
      2. RL型：P为G的右子节点，I为P的左子节点

      以上两种情况，I、P、G为三个节点不在一条直线上，因此旋转两次，最终I会成为P、G的父节点

      1. P绕I旋转，LR型左旋，RL型右旋，旋转完G直接连接I
      2. G绕I旋转，原LR型右旋，原RL型左旋
      3. 将G点变为红色，I点变黑，形成黑色节点连着两个红色节点的子结构

新增节点简化版

红插黑，直接插

红插红，看叔叔

叔为红，三变色(叔黑，爷父红)，再向上

叔位黑，看形状

LL、RR转一次

LR、RL转两次

删除节点

删除节点首先要区分删除节点有几个孩子节点。若删有两个孩子的的节点，首先要遵循二叉查找树的规则，即利用中序遍历的前驱或后继节点替换被删除节点。根据二叉查找树性质可知，前驱或后继至多有一个孩子节点。将被删除节点与前驱或后继节点替换后，交换其颜色，然后再进行删除操作。此时处理的就是删除只包含单边子树的节点或叶子节点的情况。

1. 删除含有两个叶子节点的节点（被删除节点称为D）

   1. 找到该节点的前驱或后继节点（前驱或后继节点成为S）
   2. 交换S和D的颜色
   3. 交换S和D的位置 注意：要交换S和D所有周围节点的指针关系

   以上两步完成后，即代表只交换两S和D的元素

   1. 替换后分以下几种情况

2. 删除只含有一个孩子节点(节点可连接子树)，且该节点为红色

3. 删除只含有一个孩子节点(节点可连接子树)，且该节点为黑色

4. 直接删除叶子节点

删除节点步骤简化版

comparison between AVL tree and red-black tree - 黑树与AVL树之间的对比

红黑树与AVL树之间的对比。红黑树和AVL树都是自平衡树，他们都有自我调节平衡的策略和方式，但是效率的侧重点略有不同

1. 查找效率5