二叉搜索樹（Binary Search Tree）
定義：二叉搜索樹是二叉樹的一種，是應用非常廣泛的一種二叉樹，英文簡稱為 BST
性質：
- 任何一個節點的值都大于其左子樹所有節點的值
- 任意一個節點的值都小于其右子樹所有節點的值
- 它的左右子樹也是一棵二叉搜索樹
- 二叉搜索樹可以大大提高搜索資料的效率
- 二叉搜索樹存盤的元素必須具備可比較性
- 比如 int、double 等
- 如果是自定義型別，需要指定比較方式
- 不允許為 null
二叉搜索樹的介面設計
- 二叉樹沒有索引的概念
int size() // 元素的數量
boolean isEmpty() //是否為空
void clear() //清空所有元素
void add(E element) //添加元素
void remove(E element) //洗掉元素
boolean contains(E element)//是否包含某元素
介面的實作
添加節點
步驟：
- 找到父節點parent
- 創建新節點
- parent.left = node || parent.right = node
- 如果是相同值，覆寫舊的值
實作代碼：
//添加節點
public void add(E element){
elementNotNullCheck(element);
//添加第一個節點
if (root == null){
root = new Node<E>(element, null);
size++;
return;
}
//添加非第一個節點
//找到父節點
Node<E> parent = root;
Node<E> node = root;
int cmp = 0;
while(node != null){
cmp = compare(element, node.element);
parent = node;//保存新添加節點的父節點是誰
if(cmp > 0){
node = node.right;
} else if (cmp < 0){
node = node.left;
} else { //相等
node.element = element;//新元素覆寫老元素
return;
}
}
//添加到父節點的哪個位置
Node<E> newNode = new Node<E>(element, parent);
if(cmp > 0){
parent.right = newNode;
} else {
parent.left = newNode;
}
size++;
}
元素之間的比較設計
- 允許外界傳入一個Comparator自定義比較方案
- 如果沒有傳入Comparator，強制認為元素已經實作了Compareable介面
代碼：
//comparator欄位
private Comparator<E> comparator;
//二叉搜索樹的構造器
public BinarySearchTree(){
this(null);
}
public BinarySearchTree(Comparator<E> comparator){
this.comparator = comparator;
}
/**
* 節點值比較方法
* 回傳值等于0，e1 == e2；
* 回傳值大于0，e1大于e2；
* 回傳值小于0，e1小于e2.
*/
private int compare(E e1, E e2){
if (comparator != null){
return comparator.compare(e1,e2);
}
return ((Comparable<E>)e1).compareTo(e2);
}
根據元素內容獲取節點
//獲取元素對應的節點
private Node<E> node(E element){
Node<E> node = root;
while (node != null){
int cmp = compare(element, node.element);
if (cmp == 0) return node;
if (cmp > 0) {
node = node.right;
} else {
node = node.left;
}
}
return null;
}
洗掉節點
情況有四種：
- remove節點是葉子節點
直接洗掉
若 node = node.parent.left;
則 node.parent.left = null;
若 node = node.parent.right;
則 node.parent.right = null;
若 node.parent = null;
則 node.parent.left = null;
- remove節點是度為1的節點
用子節點替代原節點的位置
設child是node.left或者child是node.right
用child替代node的位置
- 如果node是左子節點
則 child.parent = node.parent
node.parent.left = child- 如果node是右子節點
則 child.parent = node.parent
node.parent.right = child- 如果node是根節點
則 root = child
child.parent = null
- remove節點是度為2的節點
用前驅或者后繼節點的值覆寫原節點的值
然后洗掉相應的前驅或者后繼節點
注意：如果一個節點的度為2，那它的前驅、后繼節點的度只可能是1 || 0
- remove節點是根節點
//移除節點
public void remove(E element){
remove(node(element));
}
private void remove(Node<E> node){
if (node == null) return;
size --;
//洗掉度為2的節點
if (node.hasTwoChildren()){
//找到node的后繼節點
Node<E> s = successor(node);
//將后繼節點的值賦值給node節點
node.element = s.element;
//洗掉后繼節點
node = s;
}
//洗掉度為1或者為0的節點
Node<E> replacement = node.left != null ? node.left : node.right;
if (replacement != null) {//node是度為1的節點
//更改parent
replacement.parent = node.parent;
//更改node的left||right指向
if (node.parent == null) {//node是度為1的節點并且是根節點
root = replacement;
} else if (node == node.parent.right){//node是父節點的右節點
node.parent.right = replacement;
} else {//node是父節點的左節點
node.parent.left = replacement;
}
} else if (node.parent == null) { //node是葉子節點并且是根節點
root = null;
} else { //node是葉子節點但不是根節點
if (node == node.parent.right){
node.parent.right = null;
} else {
node.parent.left = null;
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/63656.html
標籤：其他
上一篇：0-亂數去重