搜尋二叉樹（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樹，紅黑樹以及跳表。