1 of 35

ต้นไม้�Tree (3)

อาจารย์สุวิชยะ รัตตะรมย์

สำนักวิชาเทคโนโลยีสารสนเทศและการสื่อสาร

​

2 of 35

หัวข้อวันนี้

  • Binary Search Tree (BST)
    • นิยามของ BST
    • การจัดการ BST
      • การเพิ่ม , ลบโหนดออกจาก BST
  • AVL Tree
    • นิยามของ AVL Tree
    • การจัดการ AVL Tree
      • Balancing Tree (หลักการทำต้นไม้ให้สมดุล)
      • SLR (single left rotation), SRR (single right rotation), DLR (double left rotation), DRR (double right rotation)

2

3 of 35

binary search tree

  • เป็น binary tree ที่มีคุณสมบัติพิเศษ คือ
    • ทุก node ของ subtree ทางซ้ายมีค่าน้อยกว่า root
    • ทุก node ของ subtree ทางขวามีค่ามากกว่าหรือเท่ากับ root
    • ทุก ๆ subtree เป็น binary search tree

​

3

>

4 of 35

4

ตัวอย่าง Binary Search Tree ที่ถูกต้อง

5 of 35

5

ตัวอย่าง Binary Search Tree ที่ไม่ถูกต้อง

6 of 35

binary search (การค้นหาแบบขจัดครึ่ง)

  • เป็นวิธีในการค้นหาข้อมูลวิธีหนึ่ง
  • ใช้ค้นหาข้อมูลจากข้อมูลที่เรียงลำดับแล้ว เช่น

​

  • ถ้าต้องการค้นหาว่าค่า k อยู่ในอาร์เรย์นี้หรือไม่ ก็นำค่า k ไปเปรียบเทียบกับค่ากึ่งกลางของอาร์เรย์
  • ดังนั้น โดยอาศัยการเปรียบเทียบเพียงครั้งเดียว ก็สามารถขจัดข้อมูลได้ครึ่งหนึ่งของชุดข้อมูล
  • จากนั้นจึงนำค่า k ไปเปรียบเทียบกับข้อมูลที่เหลือโดยใช้ binary search ซ้ำจนพบค่า k หรือหมดข้อมูล

6

12

18

20

23

35

44

52

7 of 35

binary search tree

  • ดังนั้น binary search tree ก็คือ binary tree ที่สามารถค้นหาข้อมูลในแบบ binary search ได้นั่นเอง

7

8 of 35

สิ่งที่ควรทราบเพิ่มเติมเกี่ยวกับ binary search tree

  • ถ้าเป็น BST ที่ลูกทางด้านซ้ายมีค่าน้อยกว่าพ่อแม่ เราสามารถใช้ inorder traversal เพื่อหาข้อมูลที่เรียงลำดับกันได้
  • ถ้าต้องการหาข้อมูลที่มีค่าน้อยที่สุด สามารถหาได้ leaf ที่อยู่ทางด้านซ้ายสุดของทรี หรือจะเท่ากับ root ของ subtree ทางด้านซ้ายสุด ถ้ากรณี subtree นั้นไม่มีโหนดลูกทางด้านซ้าย
  • ในทำนองเดียวกัน เราก็สามารถหาข้อมูลที่มีค่ามากที่สุดได้เช่นเดียวกัน

8

9 of 35

operation ที่ต้องทำใน BST

  • BST มี operation ที่สำคัญอยู่ 2 operation คือ
    • การเพิ่มโหนด
    • การลบโหนด

การเพิ่มโหนด

  • เพิ่มที่ Leaf เพียงอย่างเดียวเท่านั้น
  • และเพิ่มในตำแหน่งที่ยังคงคุณสมบัติของ Binary Search Tree ไว้

9

10 of 35

10

ตัวอย่าง การเพิ่มข้อมูลใน Binary Search Tree

11 of 35

11

12 of 35

การลบโหนด ใน BST

ต้องพิจารณาว่า Node ที่จะลบนั้นตรงกับกรณี

1. ไม่มี Child

2. มีเฉพาะ Right Subtree

3. มีเฉพาะ Left Subtree

4. มีทั้ง Left และ Right Subtree

12

<== ลบได้เลย

<== ดึง Right Subtree ขึ้นมา

<== ดึง Left Subtree ขึ้นมา

นำค่าที่มากที่สุดของ Left Subtree มาแทน

13 of 35

13

ตัวอย่าง กรณีที่ 1 ไม่มีโหนดลูก

23

18

X

X

44

X

X

before delete 44

23

X

18

X

X

after delete 44

14 of 35

14

ตัวอย่าง กรณีที่ 2 มีเฉพาะ right subtreee

23

18

X

X

44

X

before delete 44

46

X

X

58

X

after delete 44

23

18

X

X

46

X

X

58

X

15 of 35

15

ตัวอย่าง กรณีที่ 3 มีเฉพาะ left subtreee

23

18

X

X

44

X

before delete 44

36

X

X

28

X

23

18

X

X

after delete 44

36

X

X

28

X

16 of 35

16

ตัวอย่าง กรณีที่ 4 มีโหนดลูกทั้ง 2 ข้าง

23

18

44

X

before delete 23

20

X

X

10

X

X

20

18

X

44

X

after delete 23

10

X

X

17 of 35

การสร้าง BST

  • สำหรับการสร้าง BST ก็คือการ insert ข้อมูลเข้าไปทีละ 1 โหนดนั่นเอง เช่น มีข้อมูล 10 15 8 14 13 12

17

10

X

X

insert 10

insert 15

10

X

15

X

X

insert 8

10

15

X

X

8

X

X

18 of 35

18

insert 14

10

15

X

8

X

X

14

X

X

insert 13

10

15

X

8

X

X

14

X

13

X

X

insert 12

10

15

X

8

X

X

14

X

13

X

12

X

X

19 of 35

  • เราจะพบว่า คุณภาพของโครงสร้างต้นไม้จะขึ้นอยู่กับลักษณะการกระจายค่าของข้อมูล
  • เช่น ถ้าเรามีข้อมูลที่เกือบเรียงหรือเรียงกันอยู่แล้ว เมื่อสร้างต้นไม้จะได้ต้นไม้ที่ไม่สมดุล เช่น BST ที่สร้างจากชุดข้อมูล 10 12 18 24 35 จะได้ต้นไม้ดังนี้

19

10

X

12

X

18

X

24

X

25

X

X

20 of 35

  • ซึ่งข้อเสียของ BST ที่มีลักษณะเช่นนี้คือ ความเร็วในการค้นหาข้อมูลจะแย่ (กรณีแย่ที่สุดคือต้องเปรียบเทียบ n ครั้ง)
  • ดังนั้น ในปี 1960 นักคณิตศาสตร์ชาวรัสเซียได้พัฒนาเทคนิคในการจัดรูปแบบของ BST ที่มีการปรับแต่งโหนดให้สมดุลหรือเกือบสมดุล เมื่อมีการเพิ่มหรือลบโหนดของต้นไม้นั้น โดยที่ยังคงคุณสมบัติของ BST อยู่ ซึ่งเรียกต้นไม้ชนิดนี้ว่า AVL tree หรือ ต้นไม้ความสูงสมดุล

20

21 of 35

AVL tree (Adel’son, Vel’skii and Landis)

  • เรียกอีกอย่างว่า (Height-balanced binary search tree) หรือ ต้นไม้ความสูงสมดุล
  • คือ BST ที่ทุก subtree มี balance factor (bf) แตกต่างกันไม่เกิน 1 [-1, 0, +1]
  • bf คือ ความสูงของ left subtree ลบด้วย ความสูงของ right subtree

bf = | HL - HR |

| bf | <= 1

21

22 of 35

22

0

-1

-2

-3

-4

-5

-6

-7

0

0

0

0

0

1

-1

1

23 of 35

23

AVL tree

unbalanced BST

24 of 35

Balancing Tree (หลักการทำต้นไม้ให้สมดุล)

  • คือการปรับต้นไม้ที่ไม่เป็น AVL tree ให้เป็น AVL tree �( | bf | <= 1 , | HL - HR | <= 1 )
  • จะเกิดขึ้นหลังการเพิ่มหรือลบโหนดใน AVL tree ซึ่งทำให้ต้นไม้ขาดคุณสมบัติไป หรือเกิดขึ้นในกรณีที่ต้องการปรับ BST ให้กลายเป็น AVL tree เพื่อเพิ่มประสิทธิภาพในการค้นหาข้อมูล
  • มีกรณีที่ต้องจำอยู่ 4 กรณี คือ

- SLR (single left rotation) - SRR (single right rotation)

- DLR (double left rotation) - DRR (double right rotation)

24

25 of 35

SLR (single left rotation)

  • ใช้ในกรณีที่โหนดล่างสุด ที่ไม่สมดุลมี bf = -2 (right subtree ของโหนดนี้สูงกว่า left subtree อยู่ 2) ดังนั้นจึงต้องมีการหมุนไปทางซ้าย
  • และโหนดลูกทางด้านขวาของโหนดข้างบนมี bf = -1 (right subtree ของโหนดนี้ก็ยังสูงกว่า left subtree อยู่ 1) ซึ่งหมายความว่าต้นไม้มีการเอียงไปทางด้านขวาตลอด ดังนั้นจึงหมุนไปทางซ้ายแค่ครั้งเดียว

25

26 of 35

26

SLR

27 of 35

SRR (single right rotation)

  • ใช้ในกรณีที่โหนดล่างสุดที่ไม่สมดุลมี bf = 2 (left subtree ของโหนดนี้สูงกว่า right subtree อยู่ 2) ดังนั้นจึงต้องมีการหมุนไปทางขวา
  • และโหนดลูกทางด้านซ้ายของโหนดนี้มี bf = 1 (left subtree ของโหนดนี้ก็ยังสูงกว่า right subtree อยู่ 1) ซึ่งหมายความว่าต้นไม้มีการเอียงไปทางด้านซ้ายตลอด ดังนั้นจึงหมุนไปทางขวาแค่ครั้งเดียว

27

28 of 35

28

SRR

29 of 35

DLR (double left rotation)

  • ใช้ในกรณีที่โหนดล่างสุด ที่ไม่สมดุลมี bf = -2 (right subtree ของโหนดนี้สูงกว่า left subtree อยู่ 2) ดังนั้นจึงต้องมีการหมุนไปทางซ้าย
  • แต่โหนดลูกทางด้านขวาของโหนดข้างบน มี bf = 1 (right subtree ของโหนดลูกกลับต่ำกว่า left subtree อยู่ 1) ซึ่งหมายความว่าต้นไม้มีการเอียงไปทางด้านขวาและด้านซ้าย ดังนั้นจึงหมุนไปทางซ้าย 2 ครั้ง

29

30 of 35

30

DLR

case ที่ 1

31 of 35

31

DLR

case ที่ 2

+

32 of 35

DRR (double right rotation)

  • ใช้ในกรณีที่โหนดล่างสุดที่ไม่สมดุลมี bf = 2 (left subtree ของโหนดนี้สูงกว่า right subtree อยู่ 2) ดังนั้นจึงต้องมีการหมุนไปทางขวา
  • แต่โหนดลูกทางด้านซ้ายของโหนดนี้ มี bf = -1 (left subtree ของโหนดนี้กลับต่ำกว่า right subtree อยู่ 1) ซึ่งหมายความว่าต้นไม้มีการเอียงไปทางด้านซ้ายและด้านขวา ดังนั้นจึงหมุนไปทางขวา 2 ครั้ง

32

33 of 35

33

0

DRR

case ที่ 1

34 of 35

34

DRR

case ที่ 2

35 of 35

1.จงสร้าง Binary Search Tree จากข้อมูลต่อไปนี้� 3 2 1 4 5 6 7 16 15 14 13 11

2.จงสร้าง AVL Tree จากข้อมูลในข้อที่ 1

35

การบ้าน