【資料結構&算法】二叉排序樹

樹系列：

【資料結構&算法】樹的基本概念
【資料結構&算法】二叉樹的概念和多種周遊方式
【資料結構&算法】二叉排序樹

文章目錄

- 一、前言
- 二、定義
- 三、類結構
- 四、插入
- 五、查找
- 六、删除
- 七、全部代碼

一、前言

最近在深入了解MySQL索引，發現MySQL索引主要用B+樹實作的。本人對樹這種資料結構，一直以來掌握都是模棱兩可的狀态，現在希望通過寫一個關于樹的專題系列，來掌握樹這種資料結構，為深入了解MySQL索引打下基礎，做到心中有"樹"。

二、定義

二叉排序樹(Binary Sort(Search) Tree) 也叫二叉搜尋樹

若左子樹不空，則左子樹上所有結點的值均小于它的根結點的值
若右子樹不空，則右子樹上所有結點的值均大于它的根結點的值
左、右子樹也分别為二叉排序樹
二叉排序樹也可以是一個空樹

【資料結構&算法】二叉排序樹

三、類結構

public class BinarySortTree<K extends Comparable<? super K>, V> {
    private Node root;

    private class Node {
        private K key;
        private V value;
        private Node left;
        private Node right;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }

        @Override
        public String toString() {
            return "Node{" + "value=" + value + '}';
        }
    }
}

四、插入

思路:

若二叉樹為空，則首先單獨生成根結點。
首先執行查找算法，找出被插結點的父親結點。
判斷被插結點是其父親結點的左結點或者右結點，将被插結點作為葉子結點插入。

注意：新插入的結點總是葉子結點。

public void add(K key, V value) {
        Node node = new Node(key, value);
        if (this.root == null) {
            this.root = node;
            return;
        }
        this.add(this.root, node);
    }

    private void add(Node root, Node node) {
        if (node.key.compareTo(root.key) < 0) {
            if (root.left == null) {
                root.left = node;
            } else {
                add(root.left, node);
            }
        } else {
            if (root.right == null) {
                root.right = node;
            } else {
                add(root.right, node);
            }
        }
    }

五、查找

思路：

如果二叉排序樹為空，傳回null
如果根結點的鍵等于要查找的鍵，傳回根結點的值
否則，遞歸的在子樹中查找，如果要查找的鍵小于根結點的鍵在左子樹中查找，反之在右子樹中查找

效率:

查找效率和二叉樹的高度有關，最好的情況是，即由n個結點構成的高度為

⌊log2n⌋+1的二叉排序樹，效率為O(log2n)。

【資料結構&算法】二叉排序樹

最壞的情況是單向生長的二叉排序樹，即n個結點高度為n的二叉排序樹，其效率為O(n)

【資料結構&算法】二叉排序樹

public V get(K key) {
        if (this.root == null) {
            return null;
        }
        Node node = getNode(this.root, key);
        if (node == null) {
            return null;
        }
        return node.value;
    }
    private Node getNode(Node root, K key) {
        if (root == null) {
            return null;
        }
        if (root.key.compareTo(key) == 0) {
            return root;
        }
        if (root.key.compareTo(key) > 0) {
            return getNode(root.left, key);
        } else {
            return getNode(root.right, key);
        }
    }

六、删除

思路：

二叉排序樹的删除相對麻煩點，分為三種情況

删除的是葉子結點
删除的結點隻有左子樹/右子樹
删除結點左右子樹都存在

public boolean delete(K key) {
        if (this.root == null) {
            return false;
        }
        Node targetNode = getNode(this.root, key);
        if (targetNode == null) {
            return false;
        }
        Node parentNode = getParentNode(this.root, key);

        //删除的是葉子結點
        if (targetNode.left == null && targetNode.right == null) {
            //隻有根結點
            if (parentNode == null) {
                this.root = null;
                return true;
            }
            if (parentNode.left != null && parentNode.left.key.compareTo(targetNode.key) == 0) {
                parentNode.left = null;
                return true;
            }
            if (parentNode.right != null && parentNode.right.key.compareTo(targetNode.key) == 0) {
                parentNode.right = null;
                return true;
            }
        }
        //删除的結點隻有左子樹
        if (targetNode.left != null && targetNode.right == null) {
            if (parentNode == null) {
                this.root = targetNode.left;
                return true;
            }
            //删除結點是父結點的左結點
            if (parentNode.left != null && parentNode.left.key.compareTo(targetNode.key) == 0) {
                parentNode.left = targetNode.left;
                return true;
            }
            //删除結點是父結點的右結點
            if (parentNode.right != null && parentNode.right.key.compareTo(targetNode.key) == 0) {
                parentNode.right = targetNode.left;
                return true;
            }
        }
        //删除的結點隻有右子樹
        if (targetNode.right != null && targetNode.left == null) {
            if (parentNode == null) {
                this.root = targetNode.right;
                return true;
            }
            if (parentNode.left != null && parentNode.left.key.compareTo(targetNode.key) == 0) {
                parentNode.left = targetNode.right;
                return true;
            }
            if (parentNode.right != null && parentNode.right.key.compareTo(targetNode.key) == 0) {
                parentNode.right = targetNode.right;
                return true;
            }
        }
        //删除結點左右子樹都存在
        if (targetNode.right != null && targetNode.left != null) {
            //從右子樹早到最小的結點
            Node minNode = getMinNode(targetNode.right);
            //删除minNode
            delete(minNode.key);
            targetNode.key = minNode.key;
            targetNode.value = minNode.value;
        }
        return false;
    }
    
    //查找目前結點
   private Node getNode(Node root, K key) {
        if (root == null) {
            return null;
        }
        if (root.key.compareTo(key) == 0) {
            return root;
        }
        if (root.key.compareTo(key) > 0) {
            return getNode(root.left, key);
        } else {
            return getNode(root.right, key);
        }
    }
    
    //查找父結點
     private Node getParentNode(Node root, K key) {
        if (root == null) {
            return null;
        }
        if (root.left != null) {
            if (root.left.key.compareTo(key) == 0) {
                return root;
            }
            if (root.key.compareTo(key) > 0) {
                return getParentNode(root.left, key);
            }
        }
        if (root.right != null) {
            if (root.right.key.compareTo(key) == 0) {
                return root;
            }
            if (root.key.compareTo(key) < 0) {
                return getParentNode(root.right, key);
            }
        }
        return null;
    }
   //查找左子樹值最小的結點，也就是葉子結點
    private Node getMinNode(Node node) {
        Node targetNode = node;
        while (targetNode.left != null) {
            targetNode = targetNode.left;
        }
        return targetNode;
    }

七、全部代碼

public class BinarySortTree<K extends Comparable<? super K>, V> {
    private Node root;

    private class Node {
        private K key;
        private V value;
        private Node left;
        private Node right;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "key=" + key +
                    ", value=" + value +
                    '}';
        }
    }

    /**
     * 添加結點
     * @param key
     * @param value
     */
    public void add(K key, V value) {
        Node node = new Node(key, value);
        if (this.root == null) {
            this.root = node;
            return;
        }
        this.add(this.root, node);
    }

    private void add(Node root, Node node) {
        if (node.key.compareTo(root.key) < 0) {
            if (root.left == null) {
                root.left = node;
            } else {
                add(root.left, node);
            }
        } else {
            if (root.right == null) {
                root.right = node;
            } else {
                add(root.right, node);
            }
        }
    }

    /**
     * 擷取值
     * @param key
     * @return
     */
    public V get(K key) {
        if (this.root == null) {
            return null;
        }
        Node node = getNode(this.root, key);
        if (node == null) {
            return null;
        }
        return node.value;
    }

    /**
     * 擷取目前結點
     * @param root
     * @param key
     * @return
     */
    private Node getNode(Node root, K key) {
        if (root == null) {
            return null;
        }
        if (root.key.compareTo(key) == 0) {
            return root;
        }
        if (root.key.compareTo(key) > 0) {
            return getNode(root.left, key);
        } else {
            return getNode(root.right, key);
        }
    }

    /**
     * 擷取父結點
     * @param root
     * @param key
     * @return
     */
    private Node getParentNode(Node root, K key) {
        if (root == null) {
            return null;
        }
        if (root.left != null) {
            if (root.left.key.compareTo(key) == 0) {
                return root;
            }
            if (root.key.compareTo(key) > 0) {
                return getParentNode(root.left, key);
            }
        }
        if (root.right != null) {
            if (root.right.key.compareTo(key) == 0) {
                return root;
            }
            if (root.key.compareTo(key) < 0) {
                return getParentNode(root.right, key);
            }
        }
        return null;
    }

    /**
     * 查找左子樹值最小的結點，也就是葉子結點
     * @param node
     * @return
     */
    private Node getMinNode(Node node) {
        Node targetNode = node;
        while (targetNode.left != null) {
            targetNode = targetNode.left;
        }
        return targetNode;
    }

    /**
     * 删除結點
     * @param key
     * @return
     */
    public boolean delete(K key) {
        if (this.root == null) {
            return false;
        }
        Node targetNode = getNode(this.root, key);
        if (targetNode == null) {
            return false;
        }
        Node parentNode = getParentNode(this.root, key);

        //删除的是葉子結點
        if (targetNode.left == null && targetNode.right == null) {
            //隻有根結點
            if (parentNode == null) {
                this.root = null;
                return true;
            }
            if (parentNode.left != null && parentNode.left.key.compareTo(targetNode.key) == 0) {
                parentNode.left = null;
                return true;
            }
            if (parentNode.right != null && parentNode.right.key.compareTo(targetNode.key) == 0) {
                parentNode.right = null;
                return true;
            }
        }
        //删除的結點隻有左子樹
        if (targetNode.left != null && targetNode.right == null) {
            if (parentNode == null) {
                this.root = targetNode.left;
                return true;
            }
            //删除結點是父結點的左結點
            if (parentNode.left != null && parentNode.left.key.compareTo(targetNode.key) == 0) {
                parentNode.left = targetNode.left;
                return true;
            }
            //删除結點是父結點的右結點
            if (parentNode.right != null && parentNode.right.key.compareTo(targetNode.key) == 0) {
                parentNode.right = targetNode.left;
                return true;
            }
        }
        //删除的結點隻有右子樹
        if (targetNode.right != null && targetNode.left == null) {
            if (parentNode == null) {
                this.root = targetNode.right;
                return true;
            }
            if (parentNode.left != null && parentNode.left.key.compareTo(targetNode.key) == 0) {
                parentNode.left = targetNode.right;
                return true;
            }
            if (parentNode.right != null && parentNode.right.key.compareTo(targetNode.key) == 0) {
                parentNode.right = targetNode.right;
                return true;
            }
        }
        //删除結點左右子樹都存在
        if (targetNode.right != null && targetNode.left != null) {
            //從右子樹早到最小的結點
            Node minNode = getMinNode(targetNode.right);
            //删除minNode
            delete(minNode.key);
            targetNode.key = minNode.key;
            targetNode.value = minNode.value;
        }
        return false;
    }

    /**
     * 前序周遊
     */
    public void preOrder() {
        if (this.root == null) {
            return;
        }
        preOrder(this.root);
    }

    private void preOrder(Node node) {
        System.out.println(node);
        if (node.left != null) {
            preOrder(node.left);
        }
        if (node.right != null) {
            preOrder(node.right);
        }
    }
}

【資料結構&算法】二叉排序樹

文章目錄

一、前言

二、定義

三、類結構

四、插入

五、查找

六、删除

七、全部代碼

繼續閱讀

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

【資料結構】醫院選址

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

[轉]ISUP信令的IAM消息詳細内容

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器

hdu7108哈希

【資料結構&amp;算法】二叉排序樹

文章目錄

一、前言

二、定義

三、類結構

四、插入

五、查找

六、删除

七、全部代碼

繼續閱讀

【資料結構&算法】二叉排序樹