二叉树、二叉查找树、红黑树

二叉树

二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树 。

根节点：没有父节点的结点就是根节点（入度为0）

二叉查找树

二叉查找树.png

二叉查找树（BST：Binary Search Tree）是一种特殊的二叉树，它改善了二叉树节点查找的效率。二叉查找树有以下性质：对于任意一个节点 n，

• 其左子树（left subtree）下的每个后代节点（descendant node）的值都小于节点 n 的值；
• 其右子树（right subtree）下的每个后代节点的值都大于节点 n 的值。

这种排序的结构也是造成二叉查找树缺点的原因，如下：

二叉查找树-链表结构.png

好好地一棵查找树变成了瘸子。为了解决二叉查找树多次插入节点而导致的不平衡问题，便引入了红黑树。

红黑树

红黑树是一种自平衡的二叉查找树，除了二叉查找树的特性，还具有以下特性：

1. 每个结点不是红色就是黑色
2. 不可能有连在一起的红色结点
3. 根节点都是黑色 root

4. 每个红色结点的两个子节点都是黑色。叶子结点都是黑色：出度为0。满足了性质就可以近似的平衡了，不一定要红黑，可以为其他的。

   
   红黑树.png

左旋

将右子树的左子树链接到父亲节点的右孩子结点，父亲节点作为ptr结点的左孩子结点便完成了旋转。

左旋.gif

右旋

右单旋是左单旋的镜像旋转。
即将右子树的左子树连接到父亲结点的左子树，父亲结点作为ptr结点的右孩子结点便完成了旋转。
当前节点ptr，与父亲节点和当前节点的左孩子结点位于一条直线上时，使用右单旋进行平衡。

右旋.gif