推 scwg:多一個 field 記 key 出現的次數或用 link list 存 kv pair? 06/13 19:05
※ 引述《Solars (學士後醫(內科?))》之銘言：
: 各位前輩、版友好，小弟最近在寫avl樹的作業，可是小弟的程式一直有個地方有問題
: ，老闆交代的是產生一堆亂數(例如5000個)，範圍在1~1000內，所以會有很多數值一樣的
: 亂數，我的AVL程式最後會計算這棵樹的高度，但是我的程式中只有判斷亂數值是否大於
: 或小於父節點的值，沒有判斷亂數值一樣時該做什麼的動作；所以如果產生100000個亂數
: ，由於一堆亂數值都會產生相同的，導致高度永遠會在一個值以內(因為範圍在1~1000)，
: 翻開坊間的書，AVL或BST的插入範例，也都沒有看到相同數值時的處理方法，所以我該怎
: 麼去處理相同的值呢?還是這題目本身有問題?AVL能插入相同數值的節點嗎?
: 麻煩各位大大賜教了，小弟想了非常久............
: 先謝謝各位大大了，感恩!!
普通來講，AVL算BST的一種額外條件，所以BST該有的條件AVL一樣有
BST本身並不能處理同key(就是你說的同數)
同樣的AVL也不行。所以我們在做BST的時候要注意鍵值(key index)的唯一性
這邊所謂的key index就是你說的亂數, 在BST裡面是必須唯一的
本題無解，除非你去改AVL的結構(不過這樣就不叫AVL了)
當然也不是沒有非常trick的處理法啦
(比方說碰到同值就+0.00001, 然後第二個就+0.00002)
不過普通來講AVL並不是拿來處理這種事情的
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.217.108.106
※ 編輯: Killercat 來自: 61.217.108.106 (06/13 08:39)