数据结构表示如下:
class Node<T>{ public T value; public Node<T> parent; public boolean isRed; public Node<T> left; public Node<T> right;}RBTree在理论上还是一棵BST树,但是它在对BST的插入和删除操作时会维持树的平衡,即保证树的高度在[logN,logN+1](理论上,极端的情况下可以出现RBTree的高度达到2*logN,但实际上很难遇到)。这样RBTree的查找时间复杂度始终保持在O(logN)从而接近于理想的BST。RBTree的删除和插入操作的时间复杂度也是O(logN)。RBTree的查找操作就是BST的查找操作。
RBTree的旋转操作 旋转操作(Rotate)的目的是使节点颜色符合定义,让RBTree的高度达到平衡。
Rotate分为left-rotate(左旋)和right-rotate(右旋),区分左旋和右旋的方法是:待旋转的节点从左边上升到父节点就是右旋,待旋转的节点从右边上升到父节点就是左旋。
RBTree的查找操作RBTree的查找操作和BST的查找操作是一样的。请参考BST的查找操作代码。
RBTree的插入操作RBTree的插入与BST的插入方式是一致的,只不过是在插入过后,可能会导致树的不平衡,这时就需要对树进行旋转操作和颜色修复(在这里简称插入修复),使得它符合RBTree的定义。
新插入的节点是红色的,插入修复操作如果遇到父节点的颜色为黑则修复操作结束。也就是说,只有在父节点为红色节点的时候是需要插入修复操作的。
插入修复操作分为以下的三种情况,而且新插入的节点的父节点都是红色的:
叔叔节点也为红色。
叔叔节点为空,且祖父节点、父节点和新节点处于一条斜线上。
叔叔节点为空,且祖父节点、父节点和新节点不处于一条斜线上。
插入操作-case 1 case 1的操作是将父节点和叔叔节点与祖父节点的颜色互换,这样就符合了RBTRee的定义。即维持了高度的平衡,修复后颜色也符合RBTree定义的第三条和第四条。下图中,操作完成后A节点变成了新的节点。如果A节点的父节点不是黑色的话,则继续做修复操作。