国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

【樹結(jié)構(gòu)1】查找二叉樹

Jinkey / 1376人閱讀

摘要:自查找二叉樹起,可以說種族崛起了。編碼不善言辭,為敬首先代碼定義出查找二叉樹的結(jié)構(gòu)結(jié)構(gòu),存儲業(yè)務(wù)數(shù)據(jù)左節(jié)點右節(jié)點注意查找二叉樹的結(jié)構(gòu)可類比數(shù)據(jù)庫表結(jié)構(gòu)理解。

載一棵小樹苗,精心培育,總有一天會長成參天大樹
????????????????比如查找二叉、AVL、B + *、紅黑……
結(jié)構(gòu)

繼線性結(jié)構(gòu)之后,人們之所以又發(fā)明了樹形結(jié)構(gòu),是為了方便查找。普通樹隨便生長,看著就眼暈,除了和自然界的樹結(jié)構(gòu)相似對得起Tree這名號,沒太大價值,更別提方便查找了。

自查找二叉樹起,可以說種族崛起了。結(jié)構(gòu)上:從根節(jié)點起,小于父節(jié)點的在左,大于父節(jié)點的在右。如此結(jié)構(gòu),本身就是有序的,以中序遍歷(左->中->右)的方式走一遍,很方便把值從小到大排序。

以下給出這種樹的關(guān)鍵方法的邏輯,以及具體的編碼實現(xiàn)。

編碼

(不善言辭,coding為敬……)

首先代碼定義出查找二叉樹的結(jié)構(gòu):

// 結(jié)構(gòu)
public class BinaryNode {
    
    // key
    private Integer id;    
    // val,存儲業(yè)務(wù)數(shù)據(jù)
    private V val;
    // 左節(jié)點
    private BinaryNode leftNode;
    // 右節(jié)點
    private BinaryNode rightNode;
    
    public BinaryNode(Integer id, V val, BinaryNode leftNode, BinaryNode rightNode) {
        this.id = id;
        this.val = val;
        this.leftNode = leftNode;
        this.rightNode = rightNode;
    }
}
注意:
    查找二叉樹的結(jié)構(gòu)可類比數(shù)據(jù)庫表結(jié)構(gòu)理解。
    對于mysql中采用innodb引擎創(chuàng)建的表而言,以id為主鍵的表數(shù)據(jù)會自動加持索引。(實際上索引是B+ tree結(jié)構(gòu),可視作{{BANNED}}版的查找樹)
    這也是上面的代碼結(jié)構(gòu)定義中,key采用id命名的原因,val則可視為該數(shù)據(jù)庫表的其它字段。
新增節(jié)點

每次新增節(jié)點,會從根節(jié)點開始,根據(jù)值的大小,尋找自己的位置。

舉個例子,上圖的樹再增加一個節(jié)點35,會經(jīng)歷如下心路歷程:

與根節(jié)點50比較,新節(jié)點35較小,置左;很不幸,左邊已經(jīng)有節(jié)點30雄踞。

新節(jié)點35繼續(xù)與節(jié)點30比較。其實此時可以忽略根節(jié)點50,把左子樹視作一顆新樹,節(jié)點30視作新的根節(jié)點……沒錯,就是遞歸,直到最終找到一個空位置,方安身立命。

代碼實現(xiàn)如下:

//新增,先不考慮id重復(fù)的問題
//@param id:新增節(jié)點的key
//@param val:新增節(jié)點的值
BinaryNode add(Integer id,V val,BinaryNode tree){
    //該位置無節(jié)點,安身立命
    if(tree == null){
        tree = new BinaryNode<>(id,val,null,null);
    }

    //遞歸:新節(jié)點id大于當(dāng)前節(jié)點,新節(jié)點置右
    if(id>tree.id){
        tree.rightNode = add(id,val,tree.rightNode);
    }
    
    //遞歸:新節(jié)點id小于當(dāng)前節(jié)點,新節(jié)點置左
    if(id
范圍查找

正如之前提過的,查找二叉樹的優(yōu)勢就在于范圍查找。

怎么在一顆查找二叉樹中找到min>=且<=max的全部值?具體步驟如下:

當(dāng)前節(jié)點與min比較,如果大于min,則遞歸查看它的左節(jié)點;如果它沒有左節(jié)點,結(jié)束遞歸

當(dāng)前節(jié)點在min和max范圍內(nèi),放入結(jié)果集

當(dāng)前節(jié)點與max比較,如果小于max,則遞歸查看它的右節(jié)點;如果它沒有右節(jié)點,結(jié)束遞歸

Collection searchRange(Integer min, Integer max, Collection collection,BinaryNode tree){
    //當(dāng)前節(jié)點與min比較,如果大于min,遞歸查看當(dāng)前節(jié)點的左節(jié)點(如果有左節(jié)點的話)
    if(min=tree.getId()){
        collection.add(tree.getVal());
    }

    //當(dāng)前節(jié)點與max比較,如果小于max,遞歸查看當(dāng)前節(jié)點的右節(jié)點(如果有右節(jié)點的話)
    if(tree.getId()
刪除節(jié)點

刪除節(jié)點相對比較復(fù)雜,涉及到子樹銜接問題,分幾種情況:

無子:被刪節(jié)點沒有子節(jié)點(葉子節(jié)點),直接移除就好。

單子:直接頂替被刪除節(jié)點的位置。

雙子

BinaryNode remove(Integer id,BinaryNode tree){
    if(tree==null){
        return null;
    }

    if(id>tree.getId()){
        tree.rightNode = remove(id,tree.rightNode);
    }

    if(id min = findMin(tree.rightNode);    //找到最小節(jié)點
            tree.id = min.id;
            tree.val = min.val;

            tree.rightNode = remove(tree.id,tree.rightNode);
        }
        //無子
        else {
            tree = null;
        }
    }
    return tree;
}
注意:
    這里有個小訣竅。在做節(jié)點替換時(`32`替換`30`),可直接修改id和val,這樣就不需要修改引用了!
不足

試想一下這種情況,查找二叉樹在新增節(jié)點時,假如一直增加更小的節(jié)點,我們將得到一個只有左節(jié)點的查找二叉樹(雖然二叉不起來)。這樣的樹與鏈表又有什么區(qū)別呢?這種極端情況下,就失去了樹的優(yōu)勢了。


也就是說,在新增或刪除操作過程中,樹越不均衡(左傾或右傾),越影響查找效率!

如何彌補這種不足?需要保持樹的平衡,敬請期待AVL樹——平衡的查找二叉樹。

附錄

完整代碼實現(xiàn)見我的git練習(xí)項目com.evolution.tree包下,地址:evolution 暗夜君王的各種demo練習(xí)

啰嗦幾句,demo項目中查找二叉樹的實現(xiàn)com.evolution.tree.BinaryNodeBak,模擬了數(shù)據(jù)庫表,會多一些id的唯一性驗證。另外,還增加了中序遍歷實現(xiàn)sort()方法。

文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/72476.html

相關(guān)文章

  • 數(shù)據(jù)結(jié)構(gòu)與算法:二叉算法

    摘要:因此,根據(jù)題目給出的先序遍歷和中序遍歷,可以畫出二叉樹選參考數(shù)據(jù)結(jié)構(gòu)與算法描述實現(xiàn)二叉樹算法淺談數(shù)據(jù)結(jié)構(gòu)二叉樹慕課網(wǎng)實現(xiàn)二叉樹算法前端樹控件騰訊軟件開發(fā)面試題 內(nèi)容銜接上一章 數(shù)據(jù)結(jié)構(gòu)與算法:常見排序算法 內(nèi)容提要 什么是樹   - 為什么使用樹 二叉樹 二叉查找樹 紅黑樹 B、B+樹 堆 伸展樹 樹 可以點擊鏈接感受下筆者用d3.js畫的tree https://codepen...

    Little_XM 評論0 收藏0
  • js數(shù)據(jù)結(jié)構(gòu)和算法(三)二叉

    摘要:同樣結(jié)點樹的二叉樹,完全二叉樹的深度最小。二叉樹每個結(jié)點最多有兩個孩子,所以為它設(shè)計一個數(shù)據(jù)域和兩個指針域是比較自然的想法,我們稱這樣的鏈表叫做二叉鏈表。 二叉樹的概念 二叉樹(Binary Tree)是n(n>=0)個結(jié)點的有限集合,該集合或者為空集(空二叉樹),或者由一個根結(jié)點和兩棵互不相交的、分別稱為根結(jié)點的左子樹和右子樹的二叉樹組成。 showImg(https://seg...

    DesGemini 評論0 收藏0
  • js數(shù)據(jù)結(jié)構(gòu)-二叉二叉搜索

    摘要:前言可能有一部分人沒有讀過我上一篇寫的二叉堆,所以這里把二叉樹的基本概念復(fù)制過來了,如果讀過的人可以忽略前面針對二叉樹基本概念的介紹,另外如果對鏈表數(shù)據(jù)結(jié)構(gòu)不清楚的最好先看一下本人之前寫的數(shù)據(jù)結(jié)構(gòu)鏈表二叉樹二叉樹是一種樹形結(jié)構(gòu),它的特點是 前言 可能有一部分人沒有讀過我上一篇寫的二叉堆,所以這里把二叉樹的基本概念復(fù)制過來了,如果讀過的人可以忽略前面針對二叉樹基本概念的介紹,另外如果對鏈...

    codeKK 評論0 收藏0
  • 一文掌握關(guān)于Java數(shù)據(jù)結(jié)構(gòu)所有知識點(歡迎一起完善)

    摘要:是棧,它繼承于。滿二叉樹除了葉結(jié)點外每一個結(jié)點都有左右子葉且葉子結(jié)點都處在最底層的二叉樹。沒有鍵值相等的節(jié)點。這是數(shù)據(jù)庫選用樹的最主要原因。 在我們學(xué)習(xí)Java的時候,很多人會面臨我不知道繼續(xù)學(xué)什么或者面試會問什么的尷尬情況(我本人之前就很迷茫)。所以,我決定通過這個開源平臺來幫助一些有需要的人,通過下面的內(nèi)容,你會掌握系統(tǒng)的Java學(xué)習(xí)以及面試的相關(guān)知識。本來是想通過Gitbook的...

    keithxiaoy 評論0 收藏0
  • 數(shù)據(jù)結(jié)構(gòu)與算法——二叉(下)

    摘要:所以,如果中序遍歷二叉搜索樹,會得到一個有序的數(shù)據(jù),時間復(fù)雜度是,所以二叉搜索樹又叫做二叉排序樹。所以,我們需要一種方式來維持二叉樹的平衡,最好是將其維持為滿二叉樹或者完全二叉樹,這就是后面會說到的平衡二叉查找樹,常見的有樹,紅黑樹。 1. 概述 前面的文章說到了二叉樹,其實今天講的二叉搜索(查找)樹就是二叉樹最常用的一種形式,它支持高效的查找、插入、刪除操作,它的定義是這樣的:對于樹...

    Awbeci 評論0 收藏0

發(fā)表評論

0條評論

Jinkey

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<