搜索二叉树（BinarySearchTree）
每一颗子树，左边比我小，右边比我大
搜索二叉树一定要说明以什么标准来排序
经典的搜索二叉树，树上没有重复的用来排序的key值
如果有重复节点的需求，可以在一个节点内部增加数据项
搜索二叉树查询key(查询某个key存在还是不存在)
- 如果当前节点的value==key，返回true
- 如果当前节点的value<key，当前节点向左移动
- 如果当前节点的value>key，当前节点向右移动
- 如果当前节点变成null，返回false
------------------------> 下面说一下搜索二叉树的增删查，采用Ignas Lelys作者的源代码。
节点结构：
public static class Node {
public Node(Integer value, Node parent, Node left, Node right) {
super();
this.value = value;
this.parent = parent;
this.left = left;
this.right = right;
}
public Integer value;
public Node parent;
public Node left;
public Node right;
} 查询节点代码：
/**
* Finds a node with concrete value. If it is not found then null is
* returned.
*
* @param element
* Element value.
* @return Node with value provided, or null if not found.
*/
public Node search(int element) {
Node node = root;
while (node != null && node.value != null && node.value != element) {
if (element < node.value) {
node = node.left;
} else {
node = node.right;
}
}
return node;
} 增加节点代码：
/**
* Insert new element to tree.
*
* @param element
* Element to insert.
*/
public Node insert(int element) {
if (root == null) {
root = createNode(element, null, null, null);
size++;
return root;
}
Node insertParentNode = null;
Node searchTempNode = root;
//找到要挂的新节点的父节点
while (searchTempNode != null && searchTempNode.value != null) {
insertParentNode = searchTempNode;
if (element < searchTempNode.value) {
searchTempNode = searchTempNode.left;
} else {
searchTempNode = searchTempNode.right;
}
}
//建立新节点，确定挂在新节点的父节点的左边还是右边
Node newNode = createNode(element, insertParentNode, null, null);
if (insertParentNode.value > newNode.value) {
insertParentNode.left = newNode;
} else {
insertParentNode.right = newNode;
}
size++;
return newNode;
} 删除节点图解：
删除节点代码：
public Node delete(int element) {
Node deleteNode = search(element);
if (deleteNode != null) {
return delete(deleteNode);
} else {
return null;
}
}
//返回谁接替了被删掉节点的环境
protected Node delete(Node deleteNode) {
if (deleteNode != null) {
Node nodeToReturn = null;
if (deleteNode != null) {
if (deleteNode.left == null) {
// transplant(a,b) b去替换a的环境，a断连掉，把b返回
nodeToReturn = transplant(deleteNode, deleteNode.right);
} else if (deleteNode.right == null) {
nodeToReturn = transplant(deleteNode, deleteNode.left);
} else {
//有左孩子跟右孩子的情况
//getMinimum(deleteNode.right)右树上找到最小的节点
Node successorNode = getMinimum(deleteNode.right);
if (successorNode.parent != deleteNode) {
//如图，T替换b
transplant(successorNode, successorNode.right);
//b的右指针等于d的右指针
successorNode.right = deleteNode.right;
//b的右孩子r的父节点等于b自己
successorNode.right.parent = successorNode;
}
//a->b->c->d 全是右孩子的情况，删除a，用b替换a
transplant(deleteNode, successorNode);
successorNode.left = deleteNode.left;
successorNode.left.parent = successorNode;
nodeToReturn = successorNode;
}
size--;
}
return nodeToReturn;
}
return null;
}
//用newNode替换nodeToReplace
private Node transplant(Node nodeToReplace, Node newNode) {
if (nodeToReplace.parent == null) {
this.root = newNode;
} else if (nodeToReplace == nodeToReplace.parent.left) {
nodeToReplace.parent.left = newNode;
} else {
nodeToReplace.parent.right = newNode;
}
if (newNode != null) {
newNode.parent = nodeToReplace.parent;
}
return newNode;
}
protected Node getMinimum(Node node) {
while (node.left != null) {
node = node.left;
}
return node;
} 整体搜索二叉树实现代码
//搜索二叉树实现代码
/**
* Not implemented by zuochengyun
*
* Abstract binary search tree implementation. Its basically fully implemented
* binary search tree, just template method is provided for creating Node (other
* trees can have slightly different nodes with more info). This way some code
* from standart binary search tree can be reused for other kinds of binary
* trees.
*
* @author Ignas Lelys
* @created Jun 29, 2011
*
*/
public class AbstractBinarySearchTree {//搜索二叉树
/** Root node where whole tree starts. */
public Node root;
/** Tree size. */
protected int size;
/**
* Because this is abstract class and various trees have different
* additional information on different nodes subclasses uses this abstract
* method to create nodes (maybe of class {@link Node} or maybe some
* different node sub class).
*
* @param value
* Value that node will have.
* @param parent
* Node's parent.
* @param left
* Node's left child.
* @param right
* Node's right child.
* @return Created node instance.
*/
protected Node createNode(int value, Node parent, Node left, Node right) {
return new Node(value, parent, left, right);
}
/**
* Finds a node with concrete value. If it is not found then null is
* returned.
*
* @param element
* Element value.
* @return Node with value provided, or null if not found.
*/
public Node search(int element) {
Node node = root;
while (node != null && node.value != null && node.value != element) {
if (element < node.value) {
node = node.left;
} else {
node = node.right;
}
}
return node;
}
/**
* Insert new element to tree.
*
* @param element
* Element to insert.
*/
public Node insert(int element) {
if (root == null) {
root = createNode(element, null, null, null);
size++;
return root;
}
//查找插入的父节点，找到不能再找
Node insertParentNode = null;
Node searchTempNode = root;
while (searchTempNode != null && searchTempNode.value != null) {
insertParentNode = searchTempNode;
if (element < searchTempNode.value) {
searchTempNode = searchTempNode.left;
} else {
searchTempNode = searchTempNode.right;
}
}
Node newNode = createNode(element, insertParentNode, null, null);
if (insertParentNode.value > newNode.value) {
insertParentNode.left = newNode;
} else {
insertParentNode.right = newNode;
}
size++;
return newNode;
}
/**
* Removes element if node with such value exists.
*
* @param element
* Element value to remove.
*
* @return New node that is in place of deleted node. Or null if element for
* delete was not found.
*/
public Node delete(int element) {
Node deleteNode = search(element);
if (deleteNode != null) {
return delete(deleteNode);
} else {
return null;
}
}
/**
* Delete logic when node is already found.
*
* @param deleteNode
* Node that needs to be deleted.
*
* @return New node that is in place of deleted node. Or null if element for
* delete was not found.
*/
protected Node delete(Node deleteNode) {
if (deleteNode != null) {
Node nodeToReturn = null;
if (deleteNode != null) {
if (deleteNode.left == null) {
nodeToReturn = transplant(deleteNode, deleteNode.right);
} else if (deleteNode.right == null) {
nodeToReturn = transplant(deleteNode, deleteNode.left);
} else {
Node successorNode = getMinimum(deleteNode.right);
if (successorNode.parent != deleteNode) {
transplant(successorNode, successorNode.right);
successorNode.right = deleteNode.right;
successorNode.right.parent = successorNode;
}
transplant(deleteNode, successorNode);
successorNode.left = deleteNode.left;
successorNode.left.parent = successorNode;
nodeToReturn = successorNode;
}
size--;
}
return nodeToReturn;
}
return null;
}
/**
* Put one node from tree (newNode) to the place of another (nodeToReplace).
*
* @param nodeToReplace
* Node which is replaced by newNode and removed from tree.
* @param newNode
* New node.
*
* @return New replaced node.
*/
//相应的环境移交给newNode
private Node transplant(Node nodeToReplace, Node newNode) {
if (nodeToReplace.parent == null) {
this.root = newNode;
} else if (nodeToReplace == nodeToReplace.parent.left) {
nodeToReplace.parent.left = newNode;
} else {
nodeToReplace.parent.right = newNode;
}
if (newNode != null) {
newNode.parent = nodeToReplace.parent;
}
return newNode;
}
/**
* @param element
* @return true if tree contains element.
*/
public boolean contains(int element) {
return search(element) != null;
}
/**
* @return Minimum element in tree.
*/
public int getMinimum() {
return getMinimum(root).value;
}
/**
* @return Maximum element in tree.
*/
public int getMaximum() {
return getMaximum(root).value;
}
/**
* Get next element element who is bigger than provided element.
*
* @param element
* Element for whom descendand element is searched
* @return Successor value.
*/
// TODO Predecessor
public int getSuccessor(int element) {
return getSuccessor(search(element)).value;
}
/**
* @return Number of elements in the tree.
*/
public int getSize() {
return size;
}
/**
* Tree traversal with printing element values. In order method.
*/
public void printTreeInOrder() {
printTreeInOrder(root);
}
/**
* Tree traversal with printing element values. Pre order method.
*/
public void printTreePreOrder() {
printTreePreOrder(root);
}
/**
* Tree traversal with printing element values. Post order method.
*/
public void printTreePostOrder() {
printTreePostOrder(root);
}
/*-------------------PRIVATE HELPER METHODS-------------------*/
private void printTreeInOrder(Node entry) {
if (entry != null) {
printTreeInOrder(entry.left);
if (entry.value != null) {
System.out.println(entry.value);
}
printTreeInOrder(entry.right);
}
}
private void printTreePreOrder(Node entry) {
if (entry != null) {
if (entry.value != null) {
System.out.println(entry.value);
}
printTreeInOrder(entry.left);
printTreeInOrder(entry.right);
}
}
private void printTreePostOrder(Node entry) {
if (entry != null) {
printTreeInOrder(entry.left);
printTreeInOrder(entry.right);
if (entry.value != null) {
System.out.println(entry.value);
}
}
}
protected Node getMinimum(Node node) {
while (node.left != null) {
node = node.left;
}
return node;
}
protected Node getMaximum(Node node) {
while (node.right != null) {
node = node.right;
}
return node;
}
protected Node getSuccessor(Node node) {
// if there is right branch, then successor is leftmost node of that
// subtree
if (node.right != null) {
return getMinimum(node.right);
} else { // otherwise it is a lowest ancestor whose left child is also
// ancestor of node
Node currentNode = node;
Node parentNode = node.parent;
while (parentNode != null && currentNode == parentNode.right) {
// go up until we find parent that currentNode is not in right
// subtree.
currentNode = parentNode;
parentNode = parentNode.parent;
}
return parentNode;
}
}
// -------------------------------- TREE PRINTING
// ------------------------------------
public void printTree() {
printSubtree(root);
}
public void printSubtree(Node node) {
if (node.right != null) {
printTree(node.right, true, "");
}
printNodeValue(node);
if (node.left != null) {
printTree(node.left, false, "");
}
}
private void printNodeValue(Node node) {
if (node.value == null) {
System.out.print("<null>");
} else {
System.out.print(node.value.toString());
}
System.out.println();
}
private void printTree(Node node, boolean isRight, String indent) {
if (node.right != null) {
printTree(node.right, true, indent + (isRight ? " " : " | "));
}
System.out.print(indent);
if (isRight) {
System.out.print(" /");
} else {
System.out.print(" \\");
}
System.out.print("----- ");
printNodeValue(node);
if (node.left != null) {
printTree(node.left, false, indent + (isRight ? " | " : " "));
}
}
public static class Node {
public Node(Integer value, Node parent, Node left, Node right) {
super();
this.value = value;
this.parent = parent;
this.left = left;
this.right = right;
}
public Integer value;
public Node parent;
public Node left;
public Node right;
public boolean isLeaf() {
return left == null && right == null;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((value == null) ? 0 : value.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Node other = (Node) obj;
if (value == null) {
if (other.value != null)
return false;
} else if (!value.equals(other.value))
return false;
return true;
}
}
} 搜索二叉树存在的问题
- 输入状况决定性能
- 平衡搜索二叉树有很多，例如红黑树
搜索二叉树特别不讲究
- 基础的搜索二叉树，添加，删除时候不照顾平衡性
- 数据状况很差时，性能就很差
平衡搜索二叉树的调整元动作：左旋，右旋。平衡搜索二叉树的调整都是自下而上的，只要最下面的子树平衡，那么上面的树也平衡。通过这俩个动作我们可以将一个不平衡的搜索二叉树调整成平衡搜索二叉树
平衡搜索二叉树
平衡搜索二叉树就是把不平衡的搜索二叉树，通过左旋和右旋操作，变平衡。平衡操作的基本操作就是左旋和右旋。
加入自调整方法的二叉搜索树代码：
//加入自调整方法的二叉搜索树
/**
* Not implemented by zuochengyun
*
* Abstract class for self balancing binary search trees. Contains some methods
* that is used for self balancing trees.
*
* @author Ignas Lelys
* @created Jul 24, 2011
*
*/
public abstract class AbstractSelfBalancingBinarySearchTree extends AbstractBinarySearchTree {
/**
* Rotate to the left.
*
* @param node Node on which to rotate.
* @return Node that is in place of provided node after rotation.
*/
protected Node rotateLeft(Node node) {
Node temp = node.right;
temp.parent = node.parent;
node.right = temp.left;
if (node.right != null) {
node.right.parent = node;
}
temp.left = node;
node.parent = temp;
// temp took over node's place so now its parent should point to temp
if (temp.parent != null) {
if (node == temp.parent.left) {
temp.parent.left = temp;
} else {
temp.parent.right = temp;
}
} else {
root = temp;
}
return temp;
}
/**
* Rotate to the right.
*
* @param node Node on which to rotate.
* @return Node that is in place of provided node after rotation.
*/
protected Node rotateRight(Node node) {
Node temp = node.left;
temp.parent = node.parent;
node.left = temp.right;
if (node.left != null) {
node.left.parent = node;
}
temp.right = node;
node.parent = temp;
// temp took over node's place so now its parent should point to temp
if (temp.parent != null) {
if (node == temp.parent.left) {
temp.parent.left = temp;
} else {
temp.parent.right = temp;
}
} else {
root = temp;
}
return temp;
}
} 有序表
是一个接口名，key要按序组织，增删改查时间复杂度logN，只要满足就叫有序表。
有序表的有所操作效率为O(logN)，实现有序表的结构包括红黑树，AVL树，SizeBalance树简称SB树，跳表skiplist。
在时间复杂度层面，上面四种结构是一样的。其中，红黑树、AVL树、SB树属于同一个系列，那就是平衡搜索二叉树系列。
AVL树
拥有最严格的平衡性能，任何节点 |左树高度-右树高度|<2
SB树(SizeBalance树)
任何一个叔节点所拥有的节点数不少于任何一个侄子节点
红黑树
1.每个节点不是红就是黑
2.头节点是黑，叶节点是黑
3.红节点的子一定是黑节点
4.任何一个节点到它的每一个子，所有路径上黑节点的数量一样多(平衡性)
不管是AVL树，SB树，红黑树为了保证自己的平衡性，会分别有自己的调整策略，但底层只会使用到左旋右旋这俩个基本动作
AVL树，SB树，红黑树本质都是搜索二叉树，而且平衡性是自我约束的，无论是增删查跟搜索二叉树没有差别，差别在于这些动作之后怎么再进行额外的平衡动作，在增删查动作之前跟正常的搜索二叉树没有任何区别。
AVL树,SB树，红黑树如何查哪些节点需要调平衡？
只是具体到一个节点发现不平衡的动作不一样，受影响的节点是哪些都一样，都是从受影响的节点开始往上一个节点一个节点的查，
平衡定义：
任意一个节点的左右子树的高度差不能超过1，因此，AVL树的不平衡状态，就包括四种情况：
LL型：左孩子的左树过长，导致不平衡，右旋即可恢复平衡
RR型：右孩子的右树过长，导致不平衡，左旋即可恢复平衡
LR型：左孩子的右树过长，导致不平衡，就让左孩子的右孩子转到头节点，也就是要经过一次左旋后，再右旋一次
RL型：右孩子的左树过长，导致不平衡，就让右孩子的左孩子转到头节点，也就是要经过一次右旋后，再左旋一次
四种平衡调整：LL，LR，RL，RR
LL型解决办法
RR型同理解决办法是基于X做一个左旋
LR型解决办法
AVL树实现代码：
/**
* Not implemented by zuochengyun
*
* AVL tree implementation.
*
* In computer science, an AVL tree is a self-balancing binary search tree, and
* it was the first such data structure to be invented.[1] In an AVL tree, the
* heights of the two child subtrees of any node differ by at most one. Lookup,
* insertion, and deletion all take O(log n) time in both the average and worst
* cases, where n is the number of nodes in the tree prior to the operation.
* Insertions and deletions may require the tree to be rebalanced by one or more
* tree rotations.
*
* @author Ignas Lelys
* @created Jun 28, 2011
*
*/
// AVL树实现代码
public class AVLTree extends AbstractSelfBalancingBinarySearchTree {
/**
* @see trees.AbstractBinarySearchTree#insert(int)
*
* AVL tree insert method also balances tree if needed. Additional
* height parameter on node is used to track if one subtree is higher
* than other by more than one, if so AVL tree rotations is performed
* to regain balance of the tree.
*/
@Override
public Node insert(int element) {
Node newNode = super.insert(element);
rebalance((AVLNode)newNode);
return newNode;
}
/**
* @see trees.AbstractBinarySearchTree#delete(int)
*/
//返回谁接替了被删除节点的环境
@Override
public Node delete(int element) {
Node deleteNode = super.search(element);
if (deleteNode != null) {
Node successorNode = super.delete(deleteNode);
if (successorNode != null) {
// if replaced from getMinimum(deleteNode.right) then come back there and update heights
AVLNode minimum = successorNode.right != null ? (AVLNode)getMinimum(successorNode.right) : (AVLNode)successorNode;
recomputeHeight(minimum);
rebalance((AVLNode)minimum);
} else {//并没有任何节点替代被删除节点的位置，被删除节点是孤零零被删除的
recomputeHeight((AVLNode)deleteNode.parent);
rebalance((AVLNode)deleteNode.parent);
}
return successorNode;
}
return null;
}
/**
* @see trees.AbstractBinarySearchTree#createNode(int, trees.AbstractBinarySearchTree.Node, trees.AbstractBinarySearchTree.Node, trees.AbstractBinarySearchTree.Node)
*/
@Override
protected Node createNode(int value, Node parent, Node left, Node right) {
return new AVLNode(value, parent, left, right);
}
/**
* Go up from inserted node, and update height and balance informations if needed.
* If some node balance reaches 2 or -2 that means that subtree must be rebalanced.
*
* @param node Inserted Node.
*/
//检查平衡性，一个一个往上查
private void rebalance(AVLNode node) {
while (node != null) {
Node parent = node.parent;
int leftHeight = (node.left == null) ? -1 : ((AVLNode) node.left).height;
int rightHeight = (node.right == null) ? -1 : ((AVLNode) node.right).height;
int nodeBalance = rightHeight - leftHeight;
// rebalance (-2 means left subtree outgrow, 2 means right subtree)
if (nodeBalance == 2) {
if (node.right.right != null) {
node = (AVLNode)avlRotateLeft(node);
break;
} else {
node = (AVLNode)doubleRotateRightLeft(node);
break;
}
} else if (nodeBalance == -2) {//左树超了
if (node.left.left != null) {
node = (AVLNode)avlRotateRight(node);
break;
} else {
node = (AVLNode)doubleRotateLeftRight(node);
break;
}
} else {
updateHeight(node);
}
node = (AVLNode)parent;
}
}
/**
* Rotates to left side.
*/
private Node avlRotateLeft(Node node) {
Node temp = super.rotateLeft(node);
updateHeight((AVLNode)temp.left);
updateHeight((AVLNode)temp);
return temp;
}
/**
* Rotates to right side.
*/
private Node avlRotateRight(Node node) {
Node temp = super.rotateRight(node);
updateHeight((AVLNode)temp.right);
updateHeight((AVLNode)temp);
return temp;
}
/**
* Take right child and rotate it to the right side first and then rotate
* node to the left side.
*/
protected Node doubleRotateRightLeft(Node node) {
node.right = avlRotateRight(node.right);
return avlRotateLeft(node);
}
/**
* Take right child and rotate it to the right side first and then rotate
* node to the left side.
*/
protected Node doubleRotateLeftRight(Node node) {
node.left = avlRotateLeft(node.left);
return avlRotateRight(node);
}
/**
* Recomputes height information from the node and up for all of parents. It needs to be done after delete.
*/
//重新计算高度
private void recomputeHeight(AVLNode node) {
while (node != null) {
node.height = maxHeight((AVLNode)node.left, (AVLNode)node.right) + 1;
node = (AVLNode)node.parent;
}
}
/**
* Returns higher height of 2 nodes.
*/
private int maxHeight(AVLNode node1, AVLNode node2) {
if (node1 != null && node2 != null) {
return node1.height > node2.height ? node1.height : node2.height;
} else if (node1 == null) {
return node2 != null ? node2.height : -1;
} else if (node2 == null) {
return node1 != null ? node1.height : -1;
}
return -1;
}
/**
* Updates height and balance of the node.
*
* @param node Node for which height and balance must be updated.
*/
//
private static final void updateHeight(AVLNode node) {
int leftHeight = (node.left == null) ? -1 : ((AVLNode) node.left).height;
int rightHeight = (node.right == null) ? -1 : ((AVLNode) node.right).height;
node.height = 1 + Math.max(leftHeight, rightHeight);
}
/**
* Node of AVL tree has height and balance additional properties. If balance
* equals 2 (or -2) that node needs to be re balanced. (Height is height of
* the subtree starting with this node, and balance is difference between
* left and right nodes heights).
*
* @author Ignas Lelys
* @created Jun 30, 2011
*
*/
//height以当前节点为头，整棵树的高度
protected static class AVLNode extends Node {
public int height;
public AVLNode(int value, Node parent, Node left, Node right) {
super(value, parent, left, right);
}
}
} 总结
本章首先介绍了什么是搜索二叉树以及搜索二叉树存在的问题(输入状况决定性能，数据状况很差时，性能就很差)，所以为了解决这一问题我们引入了平衡搜索二叉树，利用左旋右旋这俩个元动作，将一个不平衡的搜索二叉树调整成平衡搜索二叉树。有序表是一个接口的名字，实现有序表的数据结构有红黑树，AVL树，SizeBalance树简称SB树，跳表skiplist。然后我们重点介绍了AVL树是如何调整平衡性的，共有四种平衡调整：LL，LR，RL，RR，以及每种情况是如何利用左旋右旋进行调整的。下一章介绍SB树，红黑树以及跳表。